Inductive proof on a sequence

Question

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 1

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.

Answer 2

Use strong induction. Suppose that $a_n$ is odd for all $n\leq k$. To see that the claim is true for $k+1$ note that the equation $$ a_{k+1}=a_{k-1} +2(a_{k-2}+2a_{k-1}) $$ implies that $a_{k+1}$ is odd as you have an odd number, $a_{k-1}$ by the inductive hypothesis, plus an even number on the RHS.

Answer 3

I would say use "strong induction"

That is when you state the inductive hypothesis. Say

Assume for all $k\le n, a_k$ is odd.

It is true in the base cases $k=1, 2$ by definition.

And show that $a_{n+1} = 2a_{n} + a_{n-1}$ must be odd.

Sine $a_n, a_{n-1}$ are odd based on the inductive hypothesis we can say:

$a_{n} = 2i + 1, a_{n-1} = 2j + 1$ for some $i,j$

$a_{n+1} = (4i + 2j + 2) + 1$

Answer 4

I personally dislike the insistence of distinguishing between "normal" and strong induction. If you prove something sequentially then you have necessarily proven it over previous cases. Once you internalize this fact, you won't ever have to wonder which version you need (you can always use strong induction, and if at the end you have only used the $k=n$ case then you just call it "normal" induction).

After you finish your base cases, consider $n+1$: If the statement is true for all less than or equal to $n$ then there are integers $b$ and $c$ so that $a_{n-1} = 2b+1$ and $a_n = 2c+1$, then $$a_{n+1} = a_{n-1} + 2a_n = (2b+1) + 2(2c+1) = 2(b+2c+1)+1 $$ which is odd.