Finding a closed form solution for a recurrence

Question

You open an account at a bank that pays 5% interest yearly, and deposit $a_0$ dollars in it. Every year you withdraw 10 times the number of years you have had the account. For example, if you started with 1000, then in the first year you would earn 50 in interest and withdraw 10, leaving 1040, and in the second year would earn 52 and withdraw 20, leaving 1072, and so forth.

(a) Find a recurrence for $a_n$, the balance in the account after n years.

(b) Solve the recurrence to find a closed form for $a_n$.

For (a) I got $a_n = 1.05a_{n-1}-10n$. I have no idea how to find a closed form for it though.

Answer 1

Set $b_n=1.05^{-n}*a_n$

Then $b_n=1.05^{-n}(1.05a_{n-1} -10n) = b_{n-1} - 10n*1.05^{-n}$

That is $b_n = a_0 - 10 \sum_{k=1}^n \frac{k}{1.05^k}$

Now set the general sum $F_n(x)=\sum_{k=1}^n k*x^k = x * \frac{d}{dx} \sum_{k=1}^n x^k = x * \frac{d}{dx} \frac{x^{n+1}-x}{x-1} = x * \frac{((n+1)x^n-1)(x-1) - (x^{n+1}-x)}{(x-1)^2} = \frac{nx^{n+2}-(n+1)x^{n+1} + x}{(x-1)^2} $

Now you have $b_n=a_0-10*F_n(\frac{1}{1.05})$ $a_n = 1.05^n \times (a_0 - 10 \times F_n(\frac{1}{1.05}))$ where $F_n(x)=\frac{nx^{n+2}-(n+1)x^{n+1} +x}{(x-1)^2} $.

This is a closed form expression, now I might have made mistakes, but you have the general method.

Answer 2

A solution of recurrences of the form:

$\begin{align} x_{n + 1} - a_n x_n = f_n \end{align}$

is to divide by the summing factor $s_n = a_0 a_1 \dotsm a_n$:

$\begin{align} \frac{x_{n + 1}}{s_n} - \frac{x_n}{s_{n - 1}} = \frac{f_n}{s_n} \end{align}$

Summing up the last equation gives the (usually messy) solution. In your case, $s_n = 1.05^{n + 1}$.