# Behavior of sequence: $a_n=ka_{n-1}-n$

Just a simple problem that has gotten me curious. For fixed $k > 1$, consider the sequences defined by:

$a_n=ka_{n-1}-n$

For high values of $a_0$, the sequence diverges to $+\infty$. For low values of $a_0$, it diverges to $-\infty$. At what point does this change happen? And at that value of $a_0$, what value does the sequence converge to, if any? If it's easier to answer for only some specific $k$, feel free.

• $a_n = k^n a_0 - \sum_{i=1}^n i k^{n-i} = C => a_0 = \frac{C+\sum_{i=1}^n i k^{n-i}}{k^n}$. If such $a_0$ exists, then the sequence will converge. How to find it is another story... Sep 10 '13 at 22:14

If you expand the recurrence a few steps, you find that

$$a_n = k^n a_0 - \sum_{j=1}^n j\cdot k^{n-j}.$$

The second summand looks vaguely familiar, we can rewrite it a bit:

\begin{align} a_n &= k^n a_0 - k^{n-1}\sum_{j=1}^\infty j\cdot k^{1-j} + k^{n-1}\sum_{j=n+1}^\infty j\cdot k^{1-j}\\ &= k^n\left(a_0 - \frac{k}{(k-1)^2}\right) + k^{n-1}\sum_{j=n+1}^\infty j\cdot k^{1-j}\\ &= k^n\left(a_0 - \frac{k}{(k-1)^2}\right) + \frac{(n+1)k-n}{(k-1)^2}\\ &= k^n\left(a_0 - \frac{k}{(k-1)^2}\right) + \frac{n}{k-1} + \frac{k}{(k-1)^2}. \end{align}

The last summand is a constant. The second summand grows to infinity, linear in $n$. The first summand is $0$ for $a_0 = \frac{k}{(k-1)^2}$, and converges exponentially to $+\infty$ or $-\infty$ if $a_0$ is larger resp. smaller than the threshold.

So $a_n$ converges for no value of $a_0$, and it diverges exponentially except for one value, where it diverges linearly.