Prove by induction that $y_n = (n-4)2^{n-1}+4$?

Question

A sequence $y_1$$y_2$$y_3, \ldots$ is defined by $y_1=1, y_2=0, y_3=0$ and $y_{m}=5y_{m-1}-8y_{m-2}+4y_{m-3}$ for $m\geq4$. Prove by induction that $y_n = (n-4)2^{n-1}+4$ for all natural numbers $n$.

How would induction be like? to make P(1) true?

Answer 1

The base case is easy:

$$n=4\implies y_4=5y_3-8y_2+4y_1=0-0+4=(4-4)2^3+4\;\;\;\color{green}\checkmark$$

Assume for all indexes up to $\;n\;$ and let us try to prove for $\;n+1\;$ :

$$y_{n+1}:=5y_n-8y_{n-1}+4y_{n-2}\stackrel{\text{Ind. Hyp.}}=$$

$$=5\left((n-4)2^{n-1}+4\right)-8\left(((n-1)-4)2^{n-2}+4\right)+4\left((n-2)-4)2^{n-3}+4\right)=$$

$$2^{n-3}\left[4(5n-20)-2(8n-40)+(4n-24)\right]+20-32+16=$$

$$2^{n-3}\left[8n-24\right]+4=2^n(n-3)+4=((n+1)-4)2^n+4\;\;\;\color{green}\checkmark$$