# Induction Question Sequences

Suppose a1, a2, a3, . . . is a sequence defined as follows: $a_1 = 1, a_2 = 3, a_k = a_{k−2} + 2a_{k−1}$ for all integers k ≥ 3. Prove that an is odd for all integers n ≥ 1.

So I've started with the base case: $k=3$ To show that:

$a_3=a_{3-2} + 2a_{3-1} = a_{1} + 2a_{2} = 1 + 2(3) = 7$ . Result is odd so base case is true.

I'm having trouble with what to do with the induction step. Based on inductions involving summations, am I supposed to show that $a_{k+1} = a_{k+1−2} + 2a_{k+1−1}$ is equal to something?

## 1 Answer

By the inductive hypothesis, you know that $a_{k+1-1}$ is odd, so $2a_{k+1-1}$ is even. You also know, by the inductive hypothesis, that $a_{k+1-2}$ is odd. What can you say about the sum of an odd and an even number?

• Just to clarify: Since it's established that a_k is equal to an odd number, by induction a_{k+1} is odd as well. And the reason a_{k+1} is odd is because a_{k+1-2} is odd (based on induction hypothesis) and 2a_{k+1-1} is even because 2*x is always even. Therefore even + odd = odd. Is this correct? – Extreme112 Nov 3 '14 at 3:39
• @Extreme112 Since $a_k$ is odd by the inductive hypothesis, so is every term with a lower index, and even+odd = odd. – user141592 Nov 3 '14 at 3:40