# Find $a_{n+2}+3a_{n+1}+2a_n=3^n$ if $a_0=0$ and $a_1=1$, and prove

Find $$a_{n+2}+3a_{n+1}+2a_n=3^n$$ if $$a_0=0$$ and $$a_1=1$$, and prove the result.

What I have done:

First we have to find the homogeneous recurrence relation solution, so $$a_{n+2}+3a_{n+1}+2a_n=0\implies x^2+3x+2=0\implies x=-1\vee x=-2,$$ thus $$a_n^H=A(-1)^n+B(-2)^n,\quad A,B\in\Bbb R.$$ Then, we have to propose a particular solution, namely $$a_n^P=K3^n,\quad K\in\Bbb R,$$ since it is linearly independent with the term independent of the original recurrence relation. So if we plug it into the equation, we have \begin{align*}3^n&=K3^{n+2}+3K3^{n+1}+2K3^n\\&=9K3^n+9K3^n+2K3^n\\&=(20K)3^n,\end{align*} so $$20K=1$$, thus $$K=1/20$$. Hence, $$a_n^P=(1/20)3^n$$. Hence, the general solution is $$a_n=a_n^H+a_n^P=A(-1)^n+B(-2)^n+\frac1{20}3^n.$$ To find the particular solution we will use the initial conditions: $$\begin{cases}a_0=0\\a_1=1\end{cases}\equiv\begin{cases}A+B+1/20=0\\-A-2B+3/20=1\end{cases}\implies A=\frac34\wedge B=-\frac45.$$ Therefore, the particular solution (the full answer) is $$\boxed{a_n=\frac34(-1)^n-\frac45(-2)^n+\frac1{20}3^n}.$$ In order to prove this solution, we will use complete induction.

The base step is $$a_0=3/4-4/5+1/20=0$$ and $$a_1=-3/4+8/5+3/20=1$$, hence it is true.

$$\color{blue}{\text{The inductive step is as follows. Assume it is true for n. Then}}$$ \require{cancel}\xcancel{\begin{align*} a_{n+2}+3a_{n+1}+2a_n&=\left(\frac34(-1)^{n+2}-\frac45(-2)^{n+2}+\frac1{20}3^{n+2}\right)+3\left(\frac34(-1)^{n+1}-\frac45(-2)^{n+1}+\frac1{20}3^{n+1}\right)+2\left(\frac34(-1)^n-\frac45(-2)^n+\frac1{20}3^n\right)\\ &=\frac34(-1)^n-\frac{16}5(-2)^n+\frac9{20}3^n-\frac94(-1)^n+\frac{24}5(-2)^n+\frac9{20}3^n+\frac32(-1)^n-\frac85(-2)^n+\frac1{10}3^n\\ &=\left(\frac34-\frac94+\frac32\right)(-1)^n+\left(-\frac{16}5+\frac{24}5-\frac85\right)(-2)^n+\left(\frac9{20}+\frac9{20}+\frac1{10}\right)3^n\\ &=3^n, \end{align*}} \color{blue}{\begin{align*} a_{(n+1)+2}+3a_{(n+1)+1}+2a_{n+1}&=\left(\frac34(-1)^{n+3}-\frac45(-2)^{n+3}+\frac1{20}3^{n+3}\right)+3\left(\frac34(-1)^{n+2}-\frac45(-2)^{n+2}+\frac1{20}3^{n+2}\right)+2\left(\frac34(-1)^{n+1}-\frac45(-2)^{n+1}+\frac1{20}3^{n+1}\right)\\ &=-\frac34(-1)^n+\frac{32}5(-2)^n+\frac{27}{20}3^n+\frac94(-1)^n-\frac{48}5(-2)^n+\frac{27}{20}3^n-\frac64(-1)^n+\frac{16}(-2)^n +\frac3{10}3^n\\ &=\left(-\frac34+\frac94-\frac32\right)(-1)^n+\left(\frac{32}5-\frac{48}5+\frac{16}5\right)(-2)^n+\left(\frac{27}{20}+\frac{27}{20}+\frac3{10}\right)3^n\\ &=(3)3^n\\ &=3^{n+1}, \end{align*}} hence it is true for $$n+1$$.

Is it correct? I do not think so, since I am not able to see how to apply the inductive step i.e. $$n+1$$, since there is $$a_{\color{red}{n+2}}$$, $$a_{\color{red}{n+1}}$$ and $$a_{\color{red}n}$$.

$$\color{red}{\text{ADDED.}}$$ Another question. If we have to prove that our solution satisfies the recurrence relation, do we ALWAYS have to replace the particular solution (if initial conditions are given) and repace the general solution if there are not initial conditions?

Thanks!!

$$\color{blue}{\text{Added.}}$$

That is not how to do proof by induction in this case. First we assume that the formula is true for some $$k$$ and $$k+1$$ where $$k \in\mathbb{N}$$. Then we have from the formula found: $$a_k=\frac34(-1)^k-\frac45(-2)^k+\frac1{20}3^k$$ $$a_{k+1}=\frac34(-1)^{k+1}-\frac45(-2)^{k+1}+\frac1{20}3^{k+1}$$ By using the original recurrence relation we can get $$a_{k+2}$$; $$a_{k+2}=3^{k}-3a_{k+1}-2a_k$$ $$=3^{k}-3(\frac34(-1)^{k+1}-\frac45(-2)^{k+1}+\frac1{20}3^{k+1})-2(\frac34(-1)^k-\frac45(-2)^k+\frac1{20}3^k)$$ $$=3^k(1-\frac{9}{20}-\frac{2}{20})+(-2)^k(-\frac{24}{5}+\frac{8}{5})+(-1)^k(\frac{9}{4}-\frac{6}{4})$$ $$=3^k(\frac{9}{20})+(-2)^k(-\frac{16}{5})+(-1)^k(\frac{3}{4})$$ $$=3^{k+2}(\frac{1}{20})-(-2)^{k+2}(\frac{4}{5})+(-1)^{k+2}(\frac{3}{4})$$ $$=\frac34(-1)^{k+2}-\frac45(-2)^{k+2}+\frac1{20}3^{k+2}$$ Thus, if it is true for some $$k$$ and $$k+1$$ where $$k \in \mathbb{N}$$, it is also true for $$k+2$$. As you have proven it is true for $$k=0$$ and $$k+1=1$$, it must be true for all positive integers by induction.
• Thank you!! Could you check the $\color{blue}{\text{blue}}$ edit, please? Now is it correct? – manooooh Feb 17 at 19:44
• And, if possible, could you answer the $\color{red}{\text{red}}$ edit, please? – manooooh Feb 17 at 19:47
• That still does not use proof by induction, it simply proves that the formula satisfies the original recurrence relation. For example, we could do the exact same working but using $\frac{1}{20}\cdot 3^n$ instead. – Peter Foreman Feb 17 at 19:49
• But a proof by induction for a second order recurrence relation requires that it is assumed to be true for some $k$ and some $k+1$. One cannot prove this by induction with a single assumption. – Peter Foreman Feb 17 at 19:58