0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ $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... $\endgroup$
    – Doctor Dan
    Sep 10 '13 at 22:14
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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