# Strong Induction: Prove provided recurrence relation $a_n$ is odd.

I'm not sure if we're allowed to post pictures but I thought it would be easier to read and I didn't see anything in the rules about it. It's question 1. Section 5.4

This question:

1. Suppose $$a_{1}, a_{2}, a_{3}, \ldots$$ is a sequence defined as follows: $$a_{1}=1, a_{2}=3$$ $$a_{k}=a_{k-2}+2 a_{k-1} \quad$$ for all integers $$k \geq 3$$ Prove that $$a_{n}$$ is odd for all integers $$n \geq 1$$

Here is the answer:

1. Proof (by strong mathematical induction):

Let the property $$P(n)$$ be the sentence " $$a_{n}$$ is odd."

Show that $$P(1)$$ and $$P(2)$$ are true:

Observe that $$a_{1}=1$$ and $$a_{2}=3$$ and both 1 and 3 are odd. Thus $$P(1)$$ and $$P(2)$$ are true.

Show that for any integer $$k \geq 2,$$ if $$P(i)$$ is true for all inte- gers i with $$1 \leq i \leq k,$$ then $$P(k+1)$$ is true:

Let $$k \geq 2$$ be any integer, and suppose $$a_{i}$$ is odd for all integers $$i$$ with $$1 \leq i \leq k$$. This is the inductive hypothe- sis.

1 We must show that $$a_{k+1}$$ is odd.

We know that $$a_{k+1}=$$ $$a_{k-1}+2 a_{k}$$ by definition of $$a_{1}, a_{2}, a_{3}, \ldots .$$ Moreover, $$k-1$$ is less than $$k+1$$ and is greater than or equal to 1 (because $$k \geq 2) .$$ Thus, by inductive hypothesis, $$a_{k-1}$$ is odd.

Also, every term of the sequence is an integer (being a sum of products of integers), and so $$2 a_{k}$$ is even by definition of even. Hence $$a_{k+1}$$ is the sum of an odd integer and an even integer and hence is odd (by exercise $$19,$$ in Section 4.1 ). This is what was to be shown.

In the proof where it says "Let $$K\geq 2$$ be any integer, and suppose...."

I don't see where or why they are using the value 2. If you want to try explaining the rest of the proof that would be great but really I can't even get past this first part.

Please explain in very detailed terms what is going on here. I'm what one might call mathematically challenged.

## 2 Answers

You’re confusing two different things. The sequence is defined by setting $a_1=1$, $a_2=3$, and then defining $a_k$ for $k>2$ (i.e., for $k\ge 3)$ by the recurrence $a_k=a_{k-2}+2a_{k-1}$. The recurrence obviously makes no sense for $k<3$: if $k<3$, then $k-2<1$, and $a_1$ is the first term of the sequence, so there is no $a_{k-2}$.

The proof starts by checking the statements $P(1)$ ($a_1$ is odd), and $P(2)$ ($a_2$ is odd) directly; that gets the induction started. The induction step is then to prove the following statement:

Induction Step: If $P(1),P(2),\dots,P(k)$ are all true, then $P(k+1)$ is also true.

The induction hypothesis is that $P(1),P(2),\dots,P(k)$ are all true, and we try to use that to prove that $P(k+1)$ is true. What’s the first $P(n)$ whose truth we’ve not yet checked? $P(3)$. And we do know that $P(1)$ and $P(2)$ are true. In other words, the first case of the induction step that needs to be proved is the $k=2$ case:

If $P(1),P(2)$ are true, then $P(2+1)=P(3)$ is also true.

Thus, we must carry out the induction step for all $k$ starting with $k=2$, i.e., for all $k\ge 2$.

Perhaps it will help to realize that we could just as well have stated the induction step like this:

Induction Step: If $P(1),P(2),\dots,P(k-1)$ are all true, then so is $P(k)$.

Now the induction hypothesis is that $P(1),P(2),\dots,P(k-1)$ are all true, and we try to prove that $P(k)$ is true. It’s exactly the same thing: we’ve just used $k$ to label the index of the proposition that we’re trying to prove, instead of the last one that we’re assuming as part of the induction hypothesis. Had the author of your book expressed it that way, he’d have started the proof a little differently:

Let $k\ge 3$ be any integer, and suppose $a_i$ is odd for all integers $i$ with $1\le i<k$. [This is the inductive hypothesis.]

This is the inductive step. The first part shows it works for the base case, Now they are showing how it works for the arbitrary case. Since we have already shown it for the base case so now we assume an arbitrary $k>=2$ and seek to show it for $k+1$. Thus if our arbitrary value of k is 2, we must show $P(3)$ is true. if $k = 97$, we will show $P(98)$ is true

• But why 2 when before the question was talking about k >=3 – Crimson.King Mar 25 '13 at 0:27
• its because the first two values of a are concretely assigned, while the next ones are recursively defined. the recursive formula only holds for values bigger than or equal to 3 since $a_1,a_2$ are concrete givens. – still_learning Mar 25 '13 at 1:05