Use Induction to prove recurrence

Solution 1:

Here's a useful "trick".

If $a_n =ua_{n-1}+v^n $ then (here comes the trick), dividing by $u^n$, $\dfrac{a_n}{u^n} =\dfrac{ua_{n-1}}{u^n}+\dfrac{v^n}{u^n} =\dfrac{a_{n-1}}{u^{n-1}}+(v/u)^n $.

Let $b_n = \dfrac{a_n}{u^n}$. Then $b_n =b_{n-1}+r^n $ where $r = v/u$ or $b_n-b_{n-1} =r^n $.

This becomes a telescoping sum, so

$\begin{array}\\ b_m-b_0 &=\sum_{n=1}^m (b_n-b_{n-1})\\ &=\sum_{n=1}^m r^n\\ &=\dfrac{r-r^{m+1}}{1-r} \qquad\text{(if } r \ne 1. \text{ If }r=1, \text{the sum is }m.)\\ &=\dfrac{\frac{v}{u}-(\frac{v}{u})^{m+1}}{1-\frac{v}{u}}\\ &=\dfrac{v-\frac{v^{m+1}}{u^m}}{u-v}\\ \text{so}\\ \dfrac{a_m}{u^m}-a_0 &=\dfrac{v-\frac{v^{m+1}}{u^m}}{u-v}\\ \text{or}\\ a_m &=u^ma_0+\dfrac{vu^m-v^{m+1}}{u-v}\\ &=u^ma_0+\dfrac{v(u^m-v^{m})}{u-v}\\ \end{array} $

Note that, if the $a$s start at $k$ instead of $0$, we can do

$\begin{array}\\ b_m-b_k &=\sum_{n=k+1}^m (b_n-b_{n-1})\\ &=\sum_{n=k+1}^m r^n\\ &=\dfrac{r^{k+1}-r^{m+1}}{1-r} \qquad\text{(if } r \ne 1. \text{ If }r=1, \text{the sum is }m-k.)\\ &=\dfrac{(\frac{v}{u})^{k+1}-(\frac{v}{u})^{m+1}}{1-\frac{v}{u}}\\ &=\dfrac{\frac{v^{k+1}}{u^k}-\frac{v^{m+1}}{u^m}}{u-v}\\ \text{so}\\ \dfrac{a_m}{u^m}-\dfrac{a_k}{u^k} &=\dfrac{\frac{v^{k+1}}{u^k}-\frac{v^{m+1}}{u^m}}{u-v}\\ \text{or}\\ a_m &=u^{m-k}a_k+\dfrac{v^{k+1}u^{m-k}-v^{m+1}}{u-v}\\ &=u^{m-k}a_k+\dfrac{v^{k+1}(u^{m-k}-v^{m-k})}{u-v}\\ \end{array} $

If this is for $k=1$, this becomes $a_m =u^{m-1}a_1+\dfrac{v^{2}(u^{m-1}-v^{m-1})}{u-v} $.