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