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