# How would you solve this recurrence equation: $a_{n+1}-2a_{n}=6\cdot 5^n$ for $n\geq 1$

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.

-
Here is the technique. – Mhenni Benghorbal Nov 23 '12 at 23:57
In short: use generatingfunctionology. – Did Nov 24 '12 at 1:40

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

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

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

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

-