4
$\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$
8
  • 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$ Aug 8, 2017 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$ Aug 8, 2017 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$ Aug 8, 2017 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, 2017 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, 2017 at 21:18

4 Answers 4

12
$\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$
4
$\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$
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$
1
$\begingroup$

F(n)=F(n-1)+F(n-2)=F(n-2)+F(n-3)+F(n-2)=2f(n-2)+F(n-3).so now we can deduce that F(n-3) and F(n) have the same parity because 2F(n-2) is definitely even.

$\endgroup$
1

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.