The Fibonacci sequence is defined by the following recurrence: F_1 = 1, F_2 = 1, and F_n = F_{n-1} + F_{n-2} for n >= 3. Prove by induction that every third element of the Fibonacci sequence (i.e., F_3, F_6, F_9, ...) is even.

GATE 1996 · Discrete Mathematics · Recurrence Relation · medium

Answer: By mathematical induction, F_{3k} is even for every positive integer k. The parity pattern (odd, odd, even) repeats with period 3, and the third element of each period is always odd + odd = even.

1. Base case: k = 1: F_3 = 2, which is even. Also F_1 = 1 (odd) and F_2 = 1 (odd). The parity triple is (odd, odd, even). Base case established.
2. Inductive hypothesis: Assume for some k >= 1 that F_{3k} is even and F_{3k-1}, F_{3k-2} are both odd.
3. Derive parity of F_{3k+1}: F_{3k} = even, F_{3k-1} = odd. even + odd = odd. So F_{3k+1} is odd.
4. Derive parity of F_{3k+2}: F_{3k+1} = odd, F_{3k} = even. odd + even = odd. So F_{3k+2} is odd.
5. Derive parity of F_{3(k+1)} = F_{3k+3}: F_{3k+2} = odd, F_{3k+1} = odd. odd + odd = even. So F_{3(k+1)} is even.
6. Conclusion: Base case k=1 verified (F_3=2). Inductive step shows P(k) => P(k+1). Therefore every third Fibonacci number is even.