Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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}$$

share|improve this question
    
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
add comment

4 Answers

up vote 8 down vote accepted

$\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.

share|improve this answer
    
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
add comment

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}$$

share|improve this answer
add comment

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....

share|improve this answer
    
Nice one. I like the fact that its quick. –  Patrick Da Silva Jun 3 '11 at 5:00
add comment

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$. $$ $$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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