# 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?

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?
• @Extreme112 Since $a_k$ is odd by the inductive hypothesis, so is every term with a lower index, and even+odd = odd. – Johanna Nov 3 '14 at 3:40