Define a sequence ($a_i$) i∈ Natural Numbers, recursively by $a_1 = 3, a_2 = −6$, and, for all $ n ≥ 2,\; a_{n+1} = a_n + 2a_{n−1} + 3.$ Prove $3$|$a_n$ for all $n ∈ \mathbb N$.
I have tried this problem, but I can't get past the inductive step, where I need to prove $2a_{n-1}$ is divisible by $3$. Is there a way to finish the proof?
We can prove $3|a_i$ and $3|a_{i+1}$ by induction.
Clearly $3|a_1=3$ and $3|a_2=-6$.
If $3|a_{n-1}$ and $3|a_n,$ then, because a linear combination of integers divisible by $3$ is divisible by $3,$
$3|a_{n+1}=a_n+2a_{n-1}+3$ and $3|a_n$.
Note that we didn't have to calculate $a_n.$