Inductive proof on a sequence

I had a quiz today with an inductive proof that gave me some trouble.
Given a sequence $a_n=\begin{cases}1,n=1\\3,n=2\\a_{n-2}+2a_{n-1},n\ge3
\end{cases}$
prove that all the values are odd.

So I was confused if I should use mathematical induction or strong induction.
I started with M.I. and made it this far, but I'm stuck and do not see where I have to go.

PF,

(Base Case) when $n=3$

$a_3=a_1+2a_2=1+2(3)=7$ So our base case holds.

(Inductive Hypothesis)

Assume True for $n=k$, $a_k=a_{k-2}+2a_{k-1}$, for $k \ge 3$

(Inductive Step)

Show for $n=k+1$, $a_{k+1}=a_{(k+1)-2} +2a_{(k+1)-1}$

$a_{k+1}=a_{k-1} +2a_{k}$

$a_{k+1}=a_{k-1} +2(a_{k-2}+2a_{k-1})$ By our inductive hypothesis

This is where I get confused. I'm not sure what step to take next, or if I am using the wrong form of induction all together. I tried to multiply it out and combine the terms, but I am still lost. Any help or insight would be greatly appreciated. Thank you!

Answer

You can use strong induction. First, note that the first two terms $a_1$ and $a_2$ are odd. Then, for $n\geq 3$, assume you know that $a_1, \ldots, a_{n-1}$ are all odd (this is the strong part of the induction).

• By definition, $a_{n} = a_{n-2} + 2a_{n-1}$.


• By the inductive hypothesis, $a_{n-1}$ and $a_{n-2}$ are both odd.


• If we know that $2\times \mathsf{odd} = \mathsf{even}$, then we can additionally know that $2a_{n-1}$ is even.


• If we know that $\mathsf{odd} + \mathsf{even} = \mathsf{odd}$, then we can additionally know that $a_{n-2}+2a_{n-1}$ is odd.


• Hence $a_{n} = a_{n-2} + 2a_{n-1}$ is odd, which completes the induction.

---

P.S. Here's a thinking tool: The reason I thought strong induction would be the right approach is that the formula for $a_n$ not only refers to the element right before ($a_{n-1}$), but two elements before $(a_{n-2})$, and so it seemed easier if I could assume that all earlier elements had the inductive property.