# Proving n-th term in a recurrence relation is odd for all values of n >2 using mathematical induction

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.

$a_2=2a_1+a_0=7$

$a_3=5a_1+2a_0=17$

$a_4=12a_1+5a_0=41$

$a_5=29a_1+12a_0=99$

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

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

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.