<s>[INST] Prove by induction that $d_n=2^n+3^n$, where $d_n = 5d_{n-1}-6d_{n-2}$ 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$
 [/INST] 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}$.
</s>