Q9

The Fibonacci sequence $\{f_1, f_2, f_3 \ldots f_n\}$ is defined by the following recurrence:

$$f_{n+2} = f_{n+1} + f_n, n \geq 1; f_2 =1:f_1=1$$

Prove by induction that every third element of the sequence is even.