Consider this list of Fibonacci numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811
Looking at this again to find the even numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811
This seems like a trivial proof by induction and case analysis. Basically, there are 3 cases:
- "Index" is divisible by 1: odd + odd
- "Index" is divisible by 2: odd + even
- "Index is divisible by 3: even + odd
I assume that I can use $f(4) = f(2) + f(3) = 1 + 1 = 2$, $f(5) = f(3) + f(4) = 1 + 2 = 3$, and $f(6) = f(4) + f(5) = 2 + 3 = 5$ as the base case. I'm struggling with how to formulate the inductive case at that point, though; can someone help me do that? (I'm trying to formalize what I said above).
Best Answer
Try formulating the induction step like this:
$$ \begin{align}\Phi(n) = & \text{$f(3n)$ is even ${\bf and}$}\\ & \text{$f(3n + 1)$ is odd ${\bf and}$}\\ & \text{$f(3n+2)$ is odd. } \end{align}$$
Then use induction to prove that $\Phi(n)$ is true for all $n$. The base case $\Phi(0)$ is as easy as usual; it's just $\text{“$0$ is even and $1$ is odd and $1$ is odd”}$.