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.

How would you solve $a_{n+1}-2a_{n}=6\cdot 5^n$ for $n\geq 1$ ?

I don't understand the text in my textbook. I Would like somebody to explain it to me.

share|improve this question
1  
Here is the technique. –  Mhenni Benghorbal Nov 23 '12 at 23:57
    
In short: use generatingfunctionology. –  Did Nov 24 '12 at 1:40

4 Answers 4

up vote 6 down vote accepted

Our recurrence is linear. The theory of linear recurrences tells us that the general solution of our recurrence has shape $a_n=G(n)+P(n)$, where $G(n)$ is the general solution of the homogeneous recurrence $a_{n+1}-2a_n=0$, and $P(n)$ is some fixed particular solution of our given recurrence.

The homogeneos recurrence $a_{n+1}-2a_n$ is simple to handle. Rewrite it as $a_{n+1}=2a_n$. This says that $a_n$ doubles we increment $n$ by $1$.

Thus $G(n)=(C)(2^n)$ for some constant $C$.

A particular solution $P(n)$ can be a bit harder to find. Let's look for a solution of the shape $P(n)=(k)(5^n)$. Substituting in our original equation, we get $$(k)(5^{n+1})-(2k)(5^n)=(6)(5^n).\tag{$1$}$$ Note that $(k)(5^{n+1})=(5a)(5^n)$. Substitute in $(1)$, and cancel the $5^n$. We get $3k=6$ and therefore $k=2$. Thus $(2)(5^n)$ is a particular solution of our recurrence.

So the general solution of our original recurrence is $$a_n=(C)(2^n)+(2)(5^n),$$ where $C$ is an arbitrary constant. If in addition we are told what $a_1$ is, we can find $C$.

share|improve this answer
    
Thank you, you helped me very much. –  user50222 Nov 26 '12 at 20:01

Using Generating Functions: Let $\displaystyle A(x)=\sum_{n\geq0}a_nx^n$. Then multiply your recurrence relation by $x^n$ and then take the sum it for $n\geq0$ to get $$ \sum_{n\geq0}a_{n+1}x^n-\sum_{n\geq0}2a_nx^n=\sum_{n\geq0}6\cdot5^nx^n $$ Now $$ \begin{align} \sum_{n\geq0}a_{n+1}x^n&=\frac{1}{x}\sum_{n\geq0}a_{n+1}x^{n+1}\\ &=\frac{1}{x}\sum_{n\geq1}a_{n}x^n\\ &=\frac{1}{x}\left(\sum_{n\geq0}a_{n}x^n-a_0\right)\\ &=\frac{1}{x}A(x)-\frac{a_0}{x} \end{align} $$ It is easy to see that $$ \sum_{n\geq0}2a_nx^n=2A(x) $$ and $$ \sum_{n\geq0}6\cdot5^nx^n=6\sum_{n\geq0}(5x)^n=\frac{6}{1-5x} $$

So you have $$ \frac{1}{x}A(x)-\frac{a_0}{x}-2A(x)=\frac{6}{1-5x} $$ If you solve this for $A(x)$, you get $$ A(x)=\frac{6x}{(1-5x)(1-2x)}+\frac{a_0}{1-2x} $$

Now observe that $$ \begin{align} \frac{6x}{(1-5x)(1-2x)}&=-\frac{2}{1-2x}+\frac{2}{1-5x}\\ &=-2\sum_{n\geq0}(2x)^n+2\sum_{\geq0}(5x)^n\\ &=\sum_{n\geq0}\left(-2^{n+1}+2\cdot5^n\right)x^n \end{align} $$

Also it is easy to see that $$ \frac{a_0}{1-2x}=\sum_{n\geq0}a_02^nx^n $$ Combining these, we have $$ A(x)=\sum_{n\geq0}\left(-2^{n+1}+2\cdot5^n+a_02^n\right)x^n $$ Therefore $$ a_n=(a_0-2)2^n+2\cdot5^n $$

share|improve this answer
    
One of my favorite methods! +1 –  robjohn Nov 24 '12 at 2:43

\begin{align} a_{n+1} & = 6 \cdot 5^n + 2 a_n\\ & = 6 \cdot 5^n + 2 (6 \cdot 5^{n-1} + 2a_{n-1})\\ & = 6 \cdot 5^n + 2 \cdot 6 \cdot 5^{n-1} + 2^2a_{n-1}\\ & = 6 \cdot 5^n + 2 \cdot 6 \cdot 5^{n-1} + 2^2 (6 \cdot 5^{n-2} + 2a_{n-2})\\ & = 6 \cdot 5^n + 2 \cdot 6 \cdot 5^{n-1} + 2^2 \cdot 6 \cdot 5^{n-2} + 2^3a_{n-2}\\ & = 6 \cdot 5^n + 2 \cdot 6 \cdot 5^{n-1} + 2^2 \cdot 6 \cdot 5^{n-2} + 2^3(6 \cdot 5^{n-3} + 2 a_{n-3})\\ & = 6 \cdot 5^n + 2 \cdot 6 \cdot 5^{n-1} + 2^2 \cdot 6 \cdot 5^{n-2} + 2^3 \cdot 6 \cdot 5^{n-3} + 2^4 \cdot a_{n-3} \end{align} Hence, in general (you need to prove the claim below using induction) $$a_{n+1} = 2^{j+1}a_{n-j} + 6 \left( \sum_{k=0}^{j} 2^k 5^{n-k} \right)$$ Setting $j=n$, we get that \begin{align} a_{n+1} & = 2^{n+1}a_0 + 6 \left( \sum_{k=0}^{n} 2^k 5^{n-k} \right) = 2^{n+1}a_0 + 6 \cdot 5^n \left( \sum_{k=0}^{n} \left(\dfrac25 \right)^k \right)\\ & = 2^{n+1}a_0 + 6 \cdot 5^n \cdot \dfrac{1-(2/5)^{n+1}}{1-2/5}\\ & = 2^{n+1}a_0 + 6 \cdot \dfrac{5^{n+1} -2^{n+1}}3\\ & = 2^{n+1}a_0 + 2 \cdot (5^{n+1} -2^{n+1}) \end{align}

EDIT

You can verify if it is true by plugging the value for $a_n$ and $a_{n+1}$ and computing $a_{n+1} - 2a_n$. $$a_n = 2^{n}a_0 + 2 \cdot (5^{n} -2^{n})$$ Hence, $$2a_n = 2^{n+1}a_0 + 4 \cdot (5^{n} -2^{n})$$ Hence, \begin{align} a_{n+1} - 2a_n & = 2^{n+1}a_0 + 2 \cdot (5^{n+1} -2^{n+1}) - \left( 2^{n+1}a_0 + 4 \cdot (5^{n} -2^{n})\right)\\ & = 2 \cdot (5^{n+1} -2^{n+1}) - 4 \cdot (5^n - 2^n)\\ & = 2 \cdot 5^{n+1} -2^{n+2} - 4 \cdot 5^n + 4 \cdot 2^n\\ & = 10 \cdot 5^{n} - 4 \cdot 5^n\\ & = 6 \cdot 5^n \end{align}

share|improve this answer
    
@WillJagy I verified it and I think what I have is correct unless I have made some error in the verification process. –  user17762 Nov 23 '12 at 23:51
    
The answer is right. I was about to post a similar answer when yours popped up. I now have to try a different approach :-) –  robjohn Nov 23 '12 at 23:52
    
Thanks for your answer! It prompted me to give two other methods :-) –  robjohn Nov 24 '12 at 9:22
    
@robjohn Your second method is elegant. –  user17762 Nov 24 '12 at 9:30

A Functional Calculus Approach

Let $S$ be the shift operator; i.e. $S(f(n))=f(n+1)$. $$ (S-2)a(n)=6\cdot5^n $$ Formally, the inverse of $S-2$ is $$ -\frac12(1+S/2+S^2/4+S^3/8+\dots) $$ Unfortunately, this does not converge for the given sequence, so let's consider $1-2S^{-1}$: $$ (1-2S^{-1})a(n)=6\cdot5^{n-1} $$ Formally, the inverse of $1-2S^{-1}$ is $$ 1+2S^{-1}+4S^{-2}+8S^{-3}+\dots $$ Applying this gives a particular solution $$ \begin{align} a(n) &=6\cdot5^{n-1}+2\cdot6\cdot5^{n-2}+4\cdot6\cdot5^{n-3}+8\cdot6\cdot5^{n-3}+\dots\\ &=6\cdot5^{n-1}\left(1+\frac25+\frac4{25}+\frac8{125}+\dots\right)\\ &=6\cdot5^{n-1}\frac1{1-2/5}\\ &=2\cdot5^n \end{align} $$ We also have the homogeneous solution of $C\,2^n$ for $(S-2)a(n)=0$, so the general solution is $$ a_n=2\cdot5^n+C\,2^n $$


A Geometric Series Approach

Let $a_n=2^n\,b_n$. Then the recurrence becomes $$ 2^{n+1}b_{n+1}-2^{n+1}b_n=6\cdot5^{n} $$ That is $$ b_{n+1}-b_n=3\cdot(5/2)^n $$ Using the formula for the sum of a geometric series, we get that $$ b_{n+1}-b_0=\frac{3\cdot(5/2)^{n+1}-3}{5/2-1} $$ which gives $$ b_n=2\cdot(5/2)^n+C $$ and reverting to $a_n$: $$ a_n=2\cdot5^n+C\,2^n $$

share|improve this answer

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.