# Recursive Induction Problem

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?

• Do you mean $$a_{n+1}=a_n+2a_{n-1}+3$$? – Dr. Sonnhard Graubner Feb 24 at 19:42
• Hi, welcome. Please don't put the question in the title but in the content of the question :) – Stan Tendijck Feb 24 at 19:57
• and please use MathJax – J. W. Tanner Feb 24 at 20:02

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.$$
• How can we assume that $a_(n-1)$ is divisible by 3? – beepbeepboop123123 Feb 25 at 0:10