Recursive definition proof

Question

I'm having trouble proving the following:

$a_0 = a_1 = 1$ and $a_n = a_{n-1} + 2a_{n-2}$ for $n \ge 2$. Prove that all the terms $a_n$ are odd integers. It makes sense since an odd number is of the form $2k + 1$ and we have $2a +a$. Can I just factor out an $a_{n-1}$?

Thank you guys for the help. Based on your suggestions, I'm working on a proof by induction. Here's what I have:

Basis: $n = 2$. $a_2 = a_1 + 2a_0 = 1 + 2 = 3$

Assume the theorem is true for all $n \le k$.

Prove: $a_{k+1} = a_k + 2a_{k-1}$ is odd.

$a_k + 2a_{k-1} = a_{k-1} + 2a_{k-2} + 2a_{k-1} = 3a_{k-1} + 2a_{k-2}$ from the induction hypothesis.

I'm having some trouble getting down to a $2k + 1$ form. Am I on the right track?

Answer 1

By the inductive hypothesis, $a_k$ is odd for $k\ge2$, so $a_k=2r+1$ for some integer $r$. Then $$ a_{k+1}=a_k+2a_{k-1}=2r+1+2a_{k-1} $$ Can you see it, now?

Answer 2

$2a_{n-2}+a_{n-1}$ and $a_{n-1}$ have the same parity, it now follows directly by induction.