# Solve recursion $a_{n}=ba_{n-1}+cd^{n-1}$

Let $b,c,d\in\mathbb{R}$ be constants with $b\neq d$. Let $$\begin{eqnarray} a_{n} &=& ba_{n-1}+cd^{n-1} \end{eqnarray}$$ be a sequence for $n \geq 1$ with $a_{0}=0$. I want to find a closed formula for this recursion. (I only know the german term geschlossene Formel and translated it that way I felt it could be right. So if I got that wrong, please correct me)

First I wrote down some of the chains and I got $$\begin{eqnarray} a_{n} &=& ba_{n-1}+cd^{n-1}\\ &=& b\left(ba_{n-2}+cd^{n-2}\right)+cd^{n-1}\\ &=& b\left(b\left(ba_{n-3}+cd^{n-3}\right)+cd^{n-2}\right)+cd^{n-1}\\ &=& b\left(b\left(b\left(ba_{n-4}+cd^{n-4}\right)+cd^{n-3}\right)+cd^{n-2}\right)+cd^{n-1}\\ &=& \dots\\ &=& \sum_{k=0}^{n}b^{k}cd^{n-k-1}\\ &=& \sum_{k=0}^{n}b^{k}cd^{n-\left(k+1\right)} \end{eqnarray}$$

So I catched the structure in a serie. Now I am asking myself how to proceed. I took the liberty to have a little peek at what WolframAlpha wood say to this serie. I hoped for inspiration and I got

$$\sum_{k=0}^{n-1}b^{k} c d^{n-(k+1)} = (c (b^n-d^n))/(b-d)$$

How did this came to be? And more important: Is my approach useful? Thank you in advance for any advice!

## Edit: My final Solution (recalculated)

$$\begin{eqnarray} a_{n} &=& ba_{n-1}+cd^{n-1}\\ &=& b\left(ba_{n-2}+cd^{n-2}\right)+cd^{n-1}\\ &=& b\left(b\left(ba_{n-3}+cd^{n-3}\right)+cd^{n-2}\right)+cd^{n-1}\\ &=& b\left(b\left(b\left(ba_{n-4}+cd^{n-4}\right)+cd^{n-3}\right)+cd^{n-2}\right)+cd^{n-1}\\ &=& b^{4}a_{n-4}+b^{3}cd^{n-4}+b^{2}cd^{n-3}+bcd^{n-2}+cd^{n-1}\\ &=& b^{5}a_{n-5}+b^{4}cd^{n-5}+b^{3}cd^{n-4}+b^{2}cd^{n-3}+bcd^{n-2}+cd^{n-1}\\ &=& b^{n}a_{0}+b^{n-1}c+\dots+b^{4}cd^{n-5}+b^{3}cd^{n-4}+b^{2}cd^{n-3}+cbd^{n-2}+cd^{n-1}\\ &=& \dots\\ &=& 0+b^{n-1}c+\dots+b^{4}cd^{n-5}+b^{3}cd^{n-4}+b^{2}cd^{n-3}+cbd^{n-2}+cd^{n-1}\\ &=& \sum_{k=0}^{n-1}b^{k}cd^{n-1-k}\\ &=& cd^{n-1}\sum_{k=0}^{n-1}b^{k}d^{-k}\\ &=& cd^{n-1}\sum_{k=0}^{n-1}\left(\frac{b}{d}\right)^{k}\\ &=& cd^{n-1}\frac{1-\left(\frac{b}{d}\right)^{n}}{1-\left(\frac{b}{d}\right)}\\ &=& cd^{n-1}\frac{1-\frac{b^{n}}{d^{n}}}{1-\frac{b}{d}}\\ &=& cd^{n-1}\frac{\frac{d^{n}-b^{n}}{d^{n}}}{\frac{d-b}{d}}\\ &=& cd^{n-1}\frac{d^{n}-b^{n}}{d^{n}}\cdot\frac{d}{d-b}\\ &=& \frac{c\left(d^{n}-b^{n}\right)}{d-b} \end{eqnarray}$$

-
I think you made a mistake somewhere. Mathematica finds me RSolve[{a[n] == b a[n \[Minus] 1] + c d^(n - 1), a[0] == 0}, a[n], n] ==> {{a[n] -> (c (b^n - d^n))/(b - d)}} –  Sjoerd C. de Vries May 11 '11 at 21:07
@Sjoerd: Thanks for posting the solition of mathematica. I recalculated and got $(c\left(d^{n}-b^{n}\right))/(d-b)$. It is nearly the same, but I can't see where I miscalculated. –  Aufwind May 12 '11 at 8:42
@Sjoerd: I see now, that it is actually the same. Just multiplyed it with (-1)/-1)... ^^" –  Aufwind May 12 '11 at 8:51

$\sum_{k=0}^{n}b^{k}cd^{n-(k+1)} = c d^{n-1}\sum_{k=0}^{n}b^{k}d^{-k}$. This the partial sum of a geometric series of ratio $b/d$, for which you probably know the formula. Now simplify.

-
Oh dear Loard, I was so blind. Of course it is the Geometric progression which is well known to every math student in the first semester. ^^ Thank you for pointing that out! I posted my solution under my question. Would you say it is right? I am worried, because my result differs from WolframAlpha. –  Aufwind May 11 '11 at 20:50
@Aufwind You had an upper summation limit of $n$ at the first try that you fed into Wolfram Alpha. Change it to $n-1$ so that Wolfram Alpha has a chance. –  Phira May 12 '11 at 8:55
@user9325: I see. I corrected it to $\sum_{k=0}^{n-1}b^{k} c d^{n-(k+1)} = (c (b^n-d^n))/(b-d)$. Thanks for pointing that out! –  Aufwind May 12 '11 at 13:01

If $b=0$, then $a_n = cd^{n-1}$.

Now assume $b\neq 0$. You can first divide both sides of the equation by $b^n$, then you get $$\frac{a_n}{b^n} = \frac{a_{n-1}}{b^{n-1}} + \frac{cd^{n-1}}{b^n}$$ Let $x_n = \frac{a_n}{b^n}$ and $q = \frac{d}{b}$, then $x_0 = a_0/b = 0$, $q\neq 1$, and we have $$x_n = x_{n-1} + (c/b)q^{n-1} \mbox{ or } x_n - x_{n-1} = (c/b)q^{n-1}$$ Then we can apply the telescoping sum method, $$\begin{eqnarray} x_n & = & x_0 + \sum_{i=1}^n (x_i - x_{i-1})\\ & = & (c/b)\sum_{i=1}^n q^{i-1}\\ & = & (\frac{c}{b})(\frac{1-q^n}{1-q}) \end{eqnarray}$$ So $$a_n = x_n b^n = (\frac{c}{b})(\frac{1-\frac{d^n}{b^n}}{1-\frac{d}{b}})b^n = \frac{c(b^n - d^n)}{b - d}$$

-

If you know how to solve linear recurences, this would simplify your computations:

\begin{eqnarray} a_{n} &=& ba_{n-1}+cd^{n-1} \end{eqnarray}

\begin{eqnarray} da_{n-1} &=& dba_{n-2}+cd^{n-1} \end{eqnarray}

and subtract....

-
Nice one. I like the fact that its quick. –  Patrick Da Silva Jun 3 '11 at 5:00
Argh... use Wilf's techniques from "generatingfunctionology". Start defining: $$A(z) = \sum_{n \ge 0} a_n z^n$$ Also write: $$a_{n + 1} = b a_n + c d^n$$ Multiply by $z^n$, add over $n \ge 0$: $$\frac{A(z) - a_0}{z} = b A(z) + c \frac{1}{1 - d z}$$ Solve for $A(z)$, express as partial fractions. The resulting terms are of the forms: $$(1 - \alpha z)^{-m} = \sum_{n \ge 0} \binom{-m}{n} (- \alpha)^n z^n = \sum_{n \ge 0} \binom{n + m - 1}{m - 1} \alpha^n z^n$$ Note that: $$\binom{n + m - 1}{m - 1} = \frac{(n + m - 1) (n + m - 2) \ldots (n + 1)}{(m - 1)!}$$ This is a polynomial in $n$ of degree $m - 1$.