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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.