3
$\begingroup$

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).

$\endgroup$
  • 6
    $\begingroup$ The Fibonacci numbers modulo 2 are $0, 1, 1, 0, 1, 1, 0, 1, 1, \dots$. Just prove that the pattern $0,1,1$ is periodic. $\endgroup$ – steven gregory Aug 8 '17 at 15:19
  • 1
    $\begingroup$ More interestingly, if you number with $F_1=1, F_2=1, F_3=2 \dots$ it is possible to prove that $F_r$ is a factor of $F_{kr}$ - your example is $F_3=2$ $\endgroup$ – Mark Bennet Aug 8 '17 at 15:46
  • 3
    $\begingroup$ $\forall m, n \in \mathbb{Z}_{> 2}: \gcd \left\{{F_m, F_n}\right\} = F_{\gcd \left\{{m, n}\right\}}$ this is more general. $\endgroup$ – adityaguharoy Aug 8 '17 at 16:44
  • 3
    $\begingroup$ $F_{n}=F_{n-1}+F_{n-2}=(F_{n-2}+F_{n-3})+F_{n-2}=2 F_{n-2} + F_{n-3}\,$, so $F_n$ and $F_{n-3}$ have the same parity. $\endgroup$ – dxiv Aug 8 '17 at 20:29
  • 1
    $\begingroup$ The proof of this fact is also addressed in math.stackexchange.com/questions/386988/… (with ordinary induction) and math.stackexchange.com/questions/488518/… (with strong induction). $\endgroup$ – David K Aug 8 '17 at 21:18
3
$\begingroup$

The Fibonacci numbers are $a_0=0$, $a_1=1$, $a_{n+2}=a_{n+1}+a_n$ for $n\ge0$. We have $$\begin{align}a_0 &= 0\quad\text{(even)} \\ a_1 &= 1\quad\text{(odd)} \\ a_2 &= a_1+a_0=1\quad\text{(odd)} \\ a_3 &= a_2+a_1=2\quad\text{(even)} \\ a_4 &= a_3+a_2=3\quad\text{(odd)} \\ a_5 &= a_4+a_3=5\quad\text{(odd)} \end{align}$$ It is straightforward from here to prove by induction that $a_k$ is even and $a_{3k+1}$ and $a_{3k+2}$ are odd for all $k\ge0$.

$\endgroup$
10
$\begingroup$

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”}$.

$\endgroup$
2
$\begingroup$

Formally, for $n\in \mathbb N\cup \{0\}$ let $P(n)$ be the statement $$\exists m_1,m_2,m_3\in \mathbb N\cup \{0\}\;(\;F(3n)=2m_1\land F(3n+1)=2m_2+1\land F(3n+2)=2m_3+1\;)$$ where $F(x)$ is the $x$-th Fibonacci number.

(i). Prove $P(0).$

(ii). Prove $$\forall n\in \mathbb N\cup \{0\}\;(P(n)\implies P(n+1)\;).$$ For example, for part of this, $F(3n+3)=F(3n+2)+F(3n+1)=(2m_3+1)+(2m_2+1)=2m'_1$ where $m'_1=m_3+m_2+1.$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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