1
$\begingroup$

(a) Determine which Fibonacci numbers are even. Use a form of mathematical induction to prove your conjecture.
(b) Determine which Fibonacci numbers are divisible by 3. Use a form of mathematical induction to prove your conjecture

I understand that for part a that all multiples of 3 of n are even. So F(0),F(3),F(6)... I just don't understand how to prove it.

For part B it is the same thing except multiples of 4

Please help, thank you!

$\endgroup$
1
$\begingroup$

Part A:

Base case: $F(0) = 0$, 0 is even. $F(3) = 2$, 2 is even.

Inductive Hypothesis: Assume $F(k)$ is even for some arbitrary positive integer $k$ that is divisible by 3.

Want to prove: That $F(k+3)$ is even given the inductive hypothesis.

\begin{align*} F(k+3) &= F(k+2) + F(k+1)\\ &= F(k+1) + F(k) + F(k+1)\\ &= F(k) + 2 F(k+1) \end{align*}

We know by our hypothesis that $F(k)$ is even. We also know that $F(k+1)$ is an integer, so $2 F(k+1)$ is necessarily even by properties of integers. And because the sum of two even integers is also even, it follows that $F(k+3)$ is even. This holds for any arbitrary positive integer $k$ that is divisible by 3, hence we've proved that $F(m)$ is even for all positive integers $m$ divisible by 3.

Part B:

Base case: $F(0) = 0$, 0 is a multiple of 3. $F(4) = 3$, 3 is a multiple of 3.

Inductive Hypothesis: Assume $F(k)$ is a multiple of 3 for some arbitrary positive integer $k$ that is divisible by 4.

Want to prove: That $F(k+4)$ is a multiple of 3 given the inductive hypothesis.

\begin{align*} F(k+4) &= F(k+3) + F(k+2)\\ &= F(k+2) + F(k+1) + F(k+1) + F(k)\\ &= F(k+1) + F(k) + F(k+1) + F(k+1) + F(k)\\ &= 2 F(k) + 3 F(k + 1) \end{align*}

By our hypothesis, $F(k)$ is a multiple of 3, so $2 F(k)$ must also be a multiple of 3. Furthermore, we know that $F(k+1)$ is some integer, so $3 F(k+1)$ must also be multiple of 3. Hence their sum, $F(k+4)$ must also be a multiple of 3.

$\endgroup$
  • 1
    $\begingroup$ How come you use k+4 and not K+1? Isn't induction always k+1? $\endgroup$ – Yamen May 30 '14 at 19:00
  • $\begingroup$ If you prefer, you can have the inductive hypothesis be for $F(k_i)$ where $k_i$ is the $i^\text{th}$ integer that is a multiple of 4. Then you would prove that it holds for $F(k_{i+1})$. Maybe this looks closer to the form you're used to. But note that $k_{i+1} = k_i + 4$, so the proof would be the same. $\endgroup$ – tomocafe May 30 '14 at 19:08
  • $\begingroup$ Oh, I see. That makes sense, thank you :) $\endgroup$ – Yamen May 30 '14 at 20:26
5
$\begingroup$

Hint: You can look at the first few terms of the sequence modulo $n$, and then conclude a pattern (because each term is based upon the previous two). The first few terms of the Fibonacci sequence modulo $2$ are

$1,1,0,1,1,0,1,1,0,1,1,0,\ldots$

The first few terms of the Fibonacci sequence modulo $3$ are

$1,1,2,0,2,2,1,0,1,1,2,0,\ldots$

Now how can you formalize this argument using induction?

Another hint: you may want multiple base cases.

$\endgroup$
0
$\begingroup$

Instead of trying to write proofs of three things --- that it's even when the index is a multiple of $3$, odd when it's $1$ more than that, and odd when it's two more than that --- write just one proof that covers all three.

Modulo $2$ you start with $1,1,0$. You've added the two $1$s to get $0$.

Then add $1$ and $0$ to get $1$: ${}\qquad 1,1,0,1$.

Then add $0$ and $1$ to get $1$: ${}\qquad 1,1,0,1,1$,

Then add those last two $1$s to get $0$: ${}\qquad 1,1,0,1,1,0$.

So if a sequence of three consecutive terms is $1,1,0$, then the next sequence of three consecutive terms is $1,1,0$.

$\endgroup$
-1
$\begingroup$

1,1,2,3,5,8 . . . an even number and an odd number added together is odd, an odd number plus and odd number is even.

$\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.