The recurrences tag has no wiki summary.

**-2**

votes

**0**answers

31 views

### What is this formula Name? Can anybody teach me guide me to understand this? [on hold]

Formula
If XT(t) at any time t relative to Timeframe T, then almost surely, there exists positive integers h and k such that every price belonging to the set [XT(t) – k , XT(t)+ k] is h(T) recurrent.
...

**1**

vote

**1**answer

57 views

### recursive equation to solve( similar to combinatorics)

I have this recursive equation:
$$\begin{align*} F(m,n)=F&=F(m,n-1)+F(m-1,n)-F(m-1,n-1-m) \\\\ F(m,0)&=F\left(m,m(m+1)/2\right)=1\\ F(m,i)=0&=0\text{ if i<0, i> }i<0\text{ or ...

**3**

votes

**0**answers

100 views

### ``Occasional'' Laurent phenomenon

This question is motivated by Richard Stanley's A question on the Laurent phenomenon (motivated by his answer to the question what is the probability that a scissor became the champion?).
He asked ...

**0**

votes

**0**answers

19 views

### Closed Form Solutions To Simple Iterated Polynomial Building Blocks [migrated]

I've been doing some work on fractals and simple iterated polynomials lately. I admit, I've only taken classes up through Calc 2, although I've done a decent bit of reading on many topics over the ...

**5**

votes

**0**answers

120 views

### Degenerate linear recurrence sequences

Let $(u_n)_{n \geq 0}$ be a linear recurrence given by
$$u_n = a_1 u_{n-1} + \cdots + a_k u_{n-k} \quad \forall n \geq k ,$$
where $u_0, \ldots, u_{k-1}, a_1, \ldots, a_k \in \mathbb{Z}$. We recall ...

**0**

votes

**1**answer

55 views

### Stationary distribution of random walk alias solving uncountably many linear equations [closed]

Let us have interval $I = (i_1,i_2)$, function $f_1 : I \mapsto I$, function $f_2 : I \mapsto I$.
Let $x_0$, $x_1$, $x_2$, ... be series of random variables from interval $I$ denoting random walk. ...

**1**

vote

**0**answers

58 views

### Number of digits in $n$-th term of generalized Fibonacci/Narayana sequence

Let $d$ be a nonnegative integer, and let the sequence ${F_d(n)}$ be defined as follows:
$F_d(n) = 1$ for $n = 0, 1, \ldots, d$
$F_d(n) = F_d(n-1) + F_d(n-1-d)$ for $n>d$
For $d=0$ the sequence ...

**1**

vote

**2**answers

95 views

### Transforming a recurrence to the product of two other recurrences

This question deals with sequence:
$$a_0 = 0,\ a_1 = 7, \quad a_{n+2} = 14a_{n+1} - a_n + 6$$
The question is about establishing that $a_n$ is a composite number (except some finite cases).
In one ...

**0**

votes

**0**answers

43 views

### Finding a stochastic differential equation as limit of a discrete stochastic equation

I'm dealing with the following problem:
Choose $Z_0 \in [0,1]$ and define a process governed by the following discrete stochastic equation:
$Z_{k+1}-Z_k=P_k(1-2Z_k)$
where $P_k=0$ with probability ...

**0**

votes

**0**answers

90 views

### Help solving a recurrence relation

For solving a related probability problem, I need to solve the following recurrence relation:-
$q(r,b,L)=\frac{b}{r+b}q(r,b-1,L)+\sum_{k=1}^{L}\frac{r}{r+b}\times\cdots \times ...

**6**

votes

**1**answer

255 views

### Polynomial recurrence relation covering the integers (and then Gaussian integers)

Say that a polynomial recurrence relation (my terminology)
for $f_i$ is:
$k$ initial conditions setting $f_1,\ldots,f_k$ to integers ($\in \mathbb{Z})$.
A recurrence equation of the form $f_i =$ a ...

**1**

vote

**0**answers

83 views

### Definition of primitive divisor of a Lucas sequence

If $\{a_n\}_{n=1}^\infty$ is a sequence of integers, then the definition of primitive divisor of one of its terms is quite natural:
Def. 1. A prime number $p$ is a primitive divisor of $a_n$ if $p ...

**0**

votes

**0**answers

61 views

### For which recurrence relations is it decidable whether a formal power series has a maximal zero coefficient?

In this MSE question, I asked whether one can prove that a generating function has infinitely many coefficients equal to zero. The answer given (and accepted) to that rather broad question was “No”.
...

**10**

votes

**3**answers

269 views

### Limiting probabilities for two-player game drawing random uniform numbers

Consider this simple 2-person game I just made up:
Player A goes gets to draw a uniform U[0,1] number up to X times. At any time, he may either keep his number, or draw a brand new uniform number. ...

**4**

votes

**2**answers

228 views

### Strong divisibility of Lucas sequences

Let $a$ and $b$ be relatively prime integers and let $u_n$ be their associate Lucas sequence, i.e., the second order linear recurrence sequence satisfying $u_0 = 0$, $u_1 = 1$ and $u_{n+2} = au_{n+1} ...

**0**

votes

**0**answers

43 views

### A question on bivariate recurrence

Is there a way to get a closed form of this recurrence (albeit approximate):
$$A(n ,k ) = {1 \over {d^k}}A(n-1, k-1) + (1 - {1 \over {d^k}})A(n-1,k)$$
Where, $n,k \ge 0$ and $d \ge 2$ are integers. ...

**9**

votes

**2**answers

279 views

### Faster formula to compute sum over partitions

Let $f$ be a function from the positive integers to the real numbers (or some ring...). Let
$$(\star) \quad F(n) = \sum_{n_1 \leq \cdots \leq n_j\atop n_1 + \cdots + n_j = n} f(n_1) \cdots f(n_j), $$
...

**1**

vote

**0**answers

125 views

### Solving a recurrence (with the form of a convolution) involving binomial coefficients

While dealing with a problem related to intersection of hyperplanes I have come across the following recurrence to obtain the values of $K_{j}$
\begin{array}{cccccccccc}
1 & = & ...

**4**

votes

**2**answers

280 views

### Asymptotic growth of recurrence relation $x_n=\min\limits_{n_1+n_2=n}(a(x_{n_1}+x_{n_2})+2n_1n_2)$

Suppose $a>0$ . Define
$$x_n=\min_{n_1+n_2=n}(a(x_{n_1}+x_{n_2})+2n_1n_2) \text{ with } x_1=0.$$
Can we find $r>0$ such that there exists two positive constant $c_1,c_2$ such that
...

**3**

votes

**0**answers

178 views

### Arithmetical properties of certain recurrence relations

Consider the following recurrence relation:
$$(4i+6j+1)(2i+3j)a_{i,j}=3j a_{i+1,j-1}-2i a_{i-1,j}+32i(i-1) a_{i-2,j+1}, i\ge0, j\ge0,$$
$$a_{0,0}=1.$$
This equation appeared in the article ...

**1**

vote

**0**answers

74 views

### Convergence and summation of power towers or Ackermann functions

I deleted this at StackExchange as it seems advanced or not very relevant for there and I want to ask here.
Let z be a complex number, $Im(z)\neq 0$ or $Re(z)<4$, m be a natural number, let ...

**0**

votes

**0**answers

71 views

### Bessel function stable recurrence relation

I want to compute hypergeometric 1f1 function using
I can't use direct computation of Bessel functions due to complexity. I want to use BesselJ recurrence relation:
But forward recursion is ...

**2**

votes

**1**answer

116 views

### General four-term recurrence relations

I was perusing through this paper and I was wondering if there is any literature on general four term recurrence relations. Specifically, say a recurrence of the form
...

**8**

votes

**1**answer

485 views

### Hamming weight of Fibonacci numbers

The Hamming weight $w(n)$ is the number of 1s in $n$ when written in binary. Is there some effective bound on Fibonacci numbers $F_n$ with $w(F_n)\le x$ for a given $x$?
Clearly only $F_0=0$ has ...

**16**

votes

**3**answers

593 views

### A question on the Laurent phenomenon

This question is motivated by my answer to 109955. It gives a
recurrence relation satisfied by a function $P(n)$ whose terms a
priori are rational functions (of three variables) with complicated
...

**1**

vote

**1**answer

201 views

### Infinitely many sufficiently large powers in linear recurrences

Edit Aaron solved the original question with the
fourth order $$ a(n)=n2^n+\frac{(-1)^n-1^n}{2} $$
trying to make the question harder.
Let $a(n)$ be a linear recurrence with constant coefficients,
of ...

**10**

votes

**3**answers

539 views

### Relating the roots of polynomials to the solution sets of certain functional equations

Consider a functional equation of the following form:
$$\sum_{k=0}^n a_k\,\underbrace{f(f(\cdots f}_{k}(x)\cdots )=0\quad \big(f:\,\mathbb{R}\to\mathbb{R},\;a_i\in ...

**22**

votes

**4**answers

994 views

### Multiplying by irrational numbers in combinatorial problems

This is getting no attention on stackexchange.
Everybody knows that the number of derangements of a set of size $n$ is the nearest integer to $n!/e$.
It had escaped my attention until last week, ...

**0**

votes

**0**answers

100 views

### Bound a sum of a serie defined by a recursive integer function

I'm using a recursive function $f: \mathbb{N} \rightarrow \mathbb{N}$, that is defined as
\begin{equation}
f(n)=\lceil \log(f(n-1)) \rceil +f(n-1)
\end{equation}
where $f(1)=F\in \mathbb{N}$, and ...

**1**

vote

**1**answer

227 views

### Does there exist a recurrence relation which cannot be written in a closed form? [closed]

I'm looking for an example of a recurrence relation where it provably does not have a closed form.
Does such a thing exist?
For example, I believe $S(n, k)$, or the Stirling numbers of the second ...

**0**

votes

**1**answer

134 views

### Solving a two dimensional non-homogenous linear recurrence

How one can solve the following recurrence:
\begin{align}
X[i,0] &=0 \quad \forall i =1,\ldots, m\\
X[m,n] &= a_n X[m,n-1]+b_n \sum_{i=k_m}^{m-1}X[i,i] +c_n
\end{align}
Where $a_i\ge 1 ,~ 0 ...

**-1**

votes

**1**answer

100 views

### Recursion equation convergence to sqrt [closed]

I'm new here. I have a recursion equation
$$
a[n] = \frac{n \cdot a[n-1]}{n+a[n-1]} + k
$$
$$
a[1] = 1
$$
$$
k \in \mathbb{R}, k > 0
$$
and from computing and ploting graphs I found that it can ...

**1**

vote

**1**answer

194 views

### On bounding the average cost of top-down merge sort

Let $A_n$ be the average number of comparisons to sort $n$ keys by merging them in a top-down fashion (see any algorithm textbook). It can he shown that
$$
A_0 = A_1 = 0;\quad A_n = ...

**7**

votes

**1**answer

1k views

### Beyond Collatz: A $5n+1$ conjecture? [closed]

Let
$$x_{n+1} = \begin{cases} x_n/2 &;\text{if } x_n \equiv 0 \pmod{2}\\ k\,x_n+1 &; \text{if } x_n\equiv 1 \pmod{2} \end{cases}$$
and $k=3$ and $x_n\in\Bbb N$. Collatz conjectured for this ...

**0**

votes

**1**answer

227 views

### Giving a general term of a recursive function, and upper bound for it

Let a constant $B \ge 1$, and let $l_1 = 0$, $b_1 = 0$ be the values of $l$ and $b$ (respectively) at time $t = 1$.
Let $l_{t+1} = l_t + 1$ if $b_i < B$, and $l_{t+1} = l_t$ otherwise
Let ...

**5**

votes

**0**answers

144 views

### Non-crystallographic cluster algebras

Background
Fomin and Zelevinsky have introduced cluster algebras in an influential article. To define a cluster algebra, Fomin and Zelevinsky have defined a mutation of seeds. Here, a seed ...

**0**

votes

**0**answers

73 views

### Approximate closed-form solution for a recurrence

Find an (approximate) closed-form solution for $S(m, b)$.
$$S(m,b)=\sum_{i=0}^{\lfloor (e-1)/2\rfloor}{e \choose i}S(m-1, b-i) \quad +
\sum_{i=\lfloor (e-1)/2\rfloor+1}^{\min(b,e)}{e\choose ...

**1**

vote

**1**answer

204 views

### Closed form solution to an iterative equation.

$f(n+1) = f(n) + f(n)^{a}$ where $a \in (0,1)$ and $n \ge 1$ with $f(1) = m$.
If $a=0$, we see $f(n) = m + n - 1$ and if $a=1$, we see $f(n) = 2^{n-1}m$. So the recursion seems to interpolate ...

**6**

votes

**3**answers

720 views

### References on techniques for solving equations with discontinuous functions such as floor and ceiling?

Here I describe the sort of reference I'm after with a motivating example. I am not seeking solutions to my equations on this forum; I'm quite happy to do that myself. Rather, I'm asking for some good ...

**2**

votes

**0**answers

152 views

### Master theorem for probabilistically inspired recurrences

Is there a general solution for multi-variable recurrences of the following form which come from Markov chain analysis?
$f(i,j,k) = p_1 f(i-1, j,k) + p_2 f(i, j-1,k) + p_3 f(i,j,k-1) + p_4 ...

**4**

votes

**3**answers

864 views

### Linear Recurrence Relations in 2 Variables with Variable Coefficients

Consider the following recurrence relation:
$$-2a_{n,m} +a_{n-1,m}+a_{n,m-1}=0,$$
where $a_{n,m} \in \mathbb{C}.$I would like a purely combinatorial way to understand the subspace of solutions to this ...

**2**

votes

**2**answers

660 views

### Methods for solving two variable recurrence

I have a recurrence
$$f(i,j) = 1+ \frac{N-i}{N} f(i,j-1) + \frac{i}{N} f(i-1, j)$$
$$f(i,0) = 0$$
$$f(0,j) = j$$
I would like to compute $f(N,M)$ in terms of N and M. The system is defined for ...

**3**

votes

**1**answer

275 views

### Books request on nonlinear recurrence relations.

Hi, do you have some sort of a bibliography on advanced techniques in recurrence equations, such as nonlinear ones and others?
As I see it recurrence equations are quite similar to differential ...

**1**

vote

**2**answers

104 views

### A recursive Double sequence related to uniform Cardinal B-spline

Given a sequence $A_n(k)$ defined as follows:
$A_0(0)=1$, $A_0(k)=0$ for all nonzero integers $k$ and
$$A_{n}(k)=(n+1-k)^2A_{n-1}(k-1)+2(n(n+1)-k^2)A_{n-1}(k)+(n+1+k)^2A_{n-1}(k+1)$$
for all positive ...

**2**

votes

**1**answer

605 views

### Three term recurrence relation.

For given $n,\ell\in\mathbb N_0$, I am interested in studying the following recursion relation for some $\mu\in\mathbb R$:
$$\sqrt{-1} \tfrac{j(\ell-j+1)(n-j+1)(n+j+1)}{2(2j-1)(2j+1)} a_{j-1} - ...

**1**

vote

**0**answers

99 views

### Trying to get an idea of the maths I could use for this optimization problem

Firstly, apologies if some of the notation or terminology is odd, or if I am defining functions that have standard notation associated with them already - I am not familiar with the concepts in this ...

**2**

votes

**0**answers

92 views

### Perturbation analysis for three term recurrences

Jacobi polynomials, denoted by $J^{(\alpha,\beta)}_n$, on $[-1,1]$ satisfy a three term recurrence
$$ J_{n+1}^{(\alpha,\beta)}(x) = (A_n+B_nx)J^{(\alpha,\beta)}_n + C_nJ_{n-1}^{(\alpha,\beta)}(x), ...

**0**

votes

**0**answers

107 views

### Recursive relation using successor function

What is the recursive relation for
H(m)=2^(m^2)
using successor function
recursive relation for multiplication:
mult(x,0)=0;
mult(x,S(y))=add(x,mult(x,y))
recursive relation for addition:
add(x,0)=x;
...

**2**

votes

**0**answers

159 views

### Partitions of central sets via dynamical systems

In the book "Recurrence in Ergodic Theory and Combinatorial Number Theory", 1981, Furstenberg introduced the notion of central sets.
He proved in Theorem 8.8 that in each finite partition of ...

**6**

votes

**5**answers

471 views

### Uniqueness of values in recurrence relations

Given an integer $k > 1$, define the sequences $X(k,n), Y(k,n)$ as follows:
$a=4k-2,$ $y_0 = 1,$ $y_1 = a + 1,y_n = ay_{n-1} - y_{n-2}$
$b = 4k + 2,$ $ x_0 = 1,$ $x_1 = b - 1,$ $x_n = ...