Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is there a general formula for $U_k$ defined by


where the $a_i$ are in arithmetic progression and $U_0=1$? Do there always exist $c,d$ such that $U_k\to cd^k$ as $k\to\infty$?

If $a_n=n+1$,

$U_k=F_{2k}$ where $F_n$ is the $n^{th}$ Fibonacci number.

If $a_n=bn-1 \ \land \ b>1$,

$U_k=b^2(b+1)^{k-2} \ \forall \ k\geq2$

share|cite|improve this question
up vote 5 down vote accepted

The recurrence equation is written as $$ U_k = \sum_{m=0}^{k-1} a_{k-1-m} U_m \tag{1} $$ Let's form the generating function $f(x) = \sum_{k=0}^\infty x^k U_k$. Then, summing eq. 1, multiplied on both sides with $x^k$, from $k=1$ to $\infty$: $$ f(x) - 1 = x \cdot f(x) \cdot \sum_{k=0}^\infty a_k x^k = x f(x) g(x) $$ Since $a_k = a_0 + (a_1-a_0) k$, $g(x) = \sum_{k=0}^\infty a_k x^k = a_0 \frac{1-2x}{(1-x)^2} + a_1 \frac{x}{(1-x)^2}$. Hence

$$ f(x) = \frac{1}{1-x g(x)} = \frac{(1-x)^2}{(1-x)^2 - a_0 x + x^2 (2a_0 - a_1)} $$

The case of $a_n = n+1$, that corresponds to $a_0=1$ and $a_1 = 2$, we recover the generating function of $F_{2k}$: $$ f(x) = \frac{(1-x)^2}{1-3 x + x^2} = 1 + x + 3 x^2 + 8 x^3 + \mathcal{o}(x^3) $$

The case of $a_n = b n -1$ maps to $a_0 =-1$ and $a_1 = b-1$ and generating function: $$ f(x) = \frac{(1-x)^2}{1-x- b x^2} $$ The above generating function does not correspond to $U_k = b^2 (b+1)^{k-2}$ for $k \geqslant 2$.

In[44]:= u[0] = 1;

In[45]:= u[k_Integer?Positive] := 
 u[k] = Expand[Sum[a[k - 1 - m] u[m], {m, 0, k - 1}]]

In[49]:= (Sum[u[k] x^k, {k, 0, 12}] /. {a[m_] :> b m - 1}) - 
 Series[-((-1 + x)^2/(-1 + x + b x^2)), {x, 0, 12}]

Out[49]= SeriesData[x, 0, {}, 13, 13, 1]

The asymptotic growth of $U_k$ is determined by poles of $f(x)$.

share|cite|improve this answer

Suppose that



$$V(x)-1=\sum_{k=1}^\infty U_kx^k=\sum_{k=1}^\infty \left(\sum_{l=0}^{k-1}\big(a(k-l)+b\big)U_l\right)x^k $$

$$=\sum_{l=0}^\infty \left(\sum_{k>l}^\infty \big(a(k-l)+b\big)x^k\right)U_l=\sum_{l=0}^\infty\left(\sum_{\delta=1}^\infty (a\delta+b)x^\delta\right)x^lU_l=\left(\frac{ax}{(1-x)^2}+\frac{bx}{1-x}\right)V(x)$$



As a rational function, its coefficients will be a linear combination of powers of the zeros of the denominator above. Assuming a non-degenerate case, one power will dominate the other and we will indeed have $U_k\sim c d^k$ for some $c,d$, as desired.

share|cite|improve this answer

Very much some generating functions stuff...

Consider the series $A(x)=\sum\limits_{k=0}^{+\infty}a_kx^k$ and $U(x)=\sum\limits_{k=0}^{+\infty}U_kx^k$ and assume that $a_k=bk+2c$ for some fixed $b$ and $c$. The recursion formula for $(U_k)_{k\geqslant0}$ yields $$ U(x)=1+x\sum\limits_{k=1}^{+\infty}\sum\limits_{i=0}^{k-1}a_iU_{k-1-i}x^{k-1}=1+xA(x)U(x), $$ hence $U(x)=\frac1{1-xA(x)}$. On the other hand, $$ A(x)=bx\sum\limits_{k=0}^{+\infty}kx^{k-1}+2c\sum\limits_{k=0}^{+\infty}x^k=\frac{bx}{(1-x)^2}+\frac{2c}{1-x}. $$ Putting these two expressions together, one gets $U(x)=(1-x)^2/V(x)$ with $V(x)=(1-vx)(1-wx)$, where $$ v=1+c+\sqrt{c^2+b},\ w=1+c-\sqrt{c^2+b}. $$ Using this and the decomposition $$ \frac1{V(x)}=\frac1{v-w}\left(\frac{v}{1-vx}-\frac{w}{1-wx}\right), $$ the asymptotic behaviour of $(U_k)_k$ follows, since $$ U_k=\frac{(v^2-1)v^{k-1}-(w^2-1)w^{k-1}}{v-w}. $$ If $1+c\gt0$ and $c^2+b\gt0$, $U_k=uv^k(1+o(1))$ with $u=(v^2-1)/(v(v-w))$. The other cases are similar, some of them involving complex roots of the quadratic $V(x)$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.