Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The Fibonacci numbers are defined as follows: $f_0=0$, $f_1=1$, and $f_n=f_{n−1}+f_{n−2}$ for $n≥2$. Prove each of the following three claims:

(i) For each $n≥0$, $f_{3n}$ is even.

(ii) For each $n≥0$, $f_{3n+1}$ is odd.

(iii) For each $n≥0$, $f_{3n+2}$ is odd.

Solution

(i) Base case: $n=0$, $f_{3(0)}=f_0=0$ (it is even)

(ii) Base case: $n=0$, $f_{3(0)+1}=f_1=1$ (it is odd)

(iii) Base case: $n=0$, $f_{3(0)+2}= f_1+f_0 = 1+0 =1$ (it is odd)

As you can see, I can only answer the base case. I don't even know where to start for the inductive step. For example, for (i), will I start the inductive step by showing it is true for $f_{3n-1}$ and show it is true for $f_{3n}$. And if so, how do I do that?

share|improve this question
1  
I have edited your question with MathJax. Please use MathJax for formatting Math next time. –  shaurya gupta Feb 9 at 12:05
add comment

1 Answer 1

up vote 1 down vote accepted

Hint: odd+odd=even; odd+even=odd. You never get two evens in a row. Do induction on $n$ so that there are three cases for each $n$, and you have the base case. Assume the three cases for $n$, and show that they together imply the three cases for $n+1$.

share|improve this answer
    
Like this: (i) Assume f(3n) is true, proof f(3n+1) should be true...if I do this, I get f(3n-1). I do not know how to work with that value. –  Manuel Feb 9 at 12:16
    
Assume that $f(3n)$ is even, $f(3n+1)$ is odd, $f(3n+2)$ is odd. Then check the parity of $f(3(n+1))=f(3n+3)$, $f(3(n+1)+1)=f(3n+4)$ and $f(3(n+1)+2)=f(3n+5)$. –  Mark Bennet Feb 9 at 12:20
    
Oh yeah! I got it. Thanks! –  Manuel Feb 9 at 12:24
    
@Manuel If you got it then upvote it and, eventually, accept it. –  DonAntonio Feb 9 at 12:31
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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