1. The problem statement, all variables and given/known data The Fibonacci numbers are defined by f(1)=1, f(2)=1 and for n>2, by f(n) = f(n-2) + f(n-1). Prove by mathematical induction that f(3n) is even for all natural numbers n. Proof: Base case: (n=1) f(3) = f(2)+f(1) =1+1 =2 is even Induction hypothesis: (suppose the statement is true for n=k, k≥1) Suppose f(3k) is even. So f(3k) = 2m for some integer m. Now we must show that the statement is true for n=k+1, i.e. f[3(k+1)] is even. f[3(k+1)] = f(3k+3) = f(3k+2) +f(3k+1) = f(3k+1) + f(3k) + f(3k+1) = 2f(3k+1) + f(3k) = 2(f(3k+1) + m ) which is even since f(3k+1) is an integer. Thus, the statment is true for all natural numbers n. ========================================= I think there may have some flaws in this proof because this is what I found from other book on the section about mathematical induction: "The Fibonacci sequence is defined recursively and depends on the previous TWO terms, so to prove statements regarding the Fibonacci sequence (e.g. f(n)≤2n for all natural numbers n), we must prove by STRONG(complete) induction and we need TWO base cases. And this is exactly what I thought too. To prove statements about Fibonacci sequence by induction, we MUST use strong induction and need to verify two base cases since the sequence depends on the previous TWO terms. If we only verified ONE base case, it should be impossible to go on. So is this proof correct or not? In particular, here are my concerns: 1) Do we need strong induction? Why or why not? 2) Do we need two base cases? Why or why not? 2. Relevant equations N/A 3. The attempt at a solution As shown above. Any help is much appreciated!