# sequence $U_k=a_0U_{k-1}+a_1U_{k-2}+\cdots+a_{k-1}U_0$

Is there a general formula for $U_k$ defined by

$$U_k=a_0U_{k-1}+a_1U_{k-2}+\cdots+a_{k-1}U_0$$

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$

-

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)$.

-

Suppose that

$$U_k=\sum_{l=0}^{k-1}\big(a(k-l)+b\big)U_l$$

Then

$$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)$$

whence

$$V(x)=\left(1-\frac{ax}{(1-x)^2}-\frac{bx}{1-x}\right)^{-1}=\frac{(1-x)^2}{1-(a+b+2)x+(b+1)x^2}.$$

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.

-

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)$.

-