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?

  • 1
    $\begingroup$ Do you mean $$a_{n+1}=a_n+2a_{n-1}+3$$? $\endgroup$ – Dr. Sonnhard Graubner Feb 24 at 19:42
  • $\begingroup$ Hi, welcome. Please don't put the question in the title but in the content of the question :) $\endgroup$ – Stan Tendijck Feb 24 at 19:57
  • $\begingroup$ and please use MathJax $\endgroup$ – 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.$

  • $\begingroup$ How can we assume that $a_(n-1)$ is divisible by 3? $\endgroup$ – beepbeepboop123123 Feb 25 at 0:10
  • $\begingroup$ Our base case has two consecutive terms divisible by 3. For the inductive step we assume two consecutive terms are divisible by 3 and show the next pair is. Since the later term of the previous pair is the earlier term of the next pair, it’s given that it’s a multiple of 3 $\endgroup$ – J. W. Tanner Feb 25 at 1:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.