Let $a_0, a_1, a_2,$ ... be the sequence of natural numbers defined by the recurrence relation

$a_0 = 1; a_1 = 3; a_n = 2 a_{n-1} + a_{n-2}$ for all $n > 2$

Show that $a_n$ is odd for all n > 0.

So far, I've computed the recurrence relation for the first few terms but I'm unable to determine the n-th term of relation.





I think that there should be a formula relating n and the coefficients of $a_1$ and $a_0$.

Thanks for your help!

  • $\begingroup$ you can get an explicit formula for yor recurrence equation $\endgroup$ – Dr. Sonnhard Graubner Aug 21 '17 at 13:33
  • $\begingroup$ That's what I've been trying to do. But to no avail. $\endgroup$ – kevinbobbkoh Aug 21 '17 at 13:36
  • $\begingroup$ set $$a_n=q^n$$ and compute $q$ $\endgroup$ – Dr. Sonnhard Graubner Aug 21 '17 at 13:37
  • $\begingroup$ For additional info, $$a_n=\frac 12 \bigg[\big(1+\sqrt2\big)^{n+1}+\big(1-\sqrt 2\big)^{n+1}\bigg]$$ $\endgroup$ – hypergeometric Aug 21 '17 at 15:42

The base of the induction is obvious (it's just given).

Let $a_n$, $a_{n-1}$ be odds.

Thus, $a_{n+1}=2a_{n}+a_{n-1}$ is odd and we are done!


$a_0$ and $a_1$ are obviously odd.

Suppose $a_n$ is odd for some $n\geq 2$:

Then $a_{n+1}=2a_n+a_{n-1}$ is odd, since $2a_n$ is even and $a_{n-1}$ is odd.


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.