Prove by induction that $d_n=2^n+3^n$, where $d_n = 5d_{n-1}-6d_{n-2}$

Question

I have one more induction question. $d_0 =2 $ $d_1=5$

let $d_n=5d_{n-1} - 6d_{n-2}$

Prove that $d_n=2^n+3^n$

Answer 1

Assuming $d_0=2$ and $d_1=5$ (which also starts the induction, incidentally): let $n \geq 2$, and suppose the property holds for all $0\leq k< n$. Then $$ \begin{align*} d_{n} &= 5d_{n-1} - 6d_{n-2} \\ &= 5\left(2^{n-1}+3^{n-1}\right) - 6\left(2^{n-2}+3^{n-2}\right) \qquad\qquad\text{(induction hypothesis)} \\ &= 5\cdot 2^{n-1}+5\cdot 3^{n-1} - 3\cdot 2^{n-1}- 2\cdot 3^{n-1} \\ &= 2\cdot 2^{n-1}+3\cdot 3^{n-1} \\ &= 2^{n}+3^{n} \end{align*} $$ so by induction, the property holds for all $n\in\mathbb{N}$.