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.}}$
Best Answer
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.