Question

Assume that `f_1,f_2,...,f_n,...` are the Fibonacci numbers. Then `AAn in NN, f_(4n)` is a multiple of `3`. Prove this statement is true?

Don't even know where to start!

Thanks.

Answer 1

Use mathematical induction.

Explanation:

I will format my answer as much more of an explanation than a formal proof. That will be up to you.

Proposition: If `f_1,f_2,...,f_n,...` are the Fibonacci numbers, then for each `n in NN, f_(4n)` is a multiple of `3`.

I will use induction.

Proof.

To complete a proof by induction, you begin with a general statement, `P(n)`. In this case, our general statement is "`f_(4n)` is a multiple of 3." Recall that for `f_(4n)`to to be a multiple of `3`, it must be equal to the product of `3` and some integer.

To prove a proposition is true using induction, we show that if the statement is true for `n=k+1`, it is true `AA n in NN`. In analogy to a staircase, we're proving that if we can get onto the first step, we can continue to move up the staircase to get to whichever term we'd like, no matter how far into the sequence it is. We first must prove that we can get onto the "steps."

We now need a basis or base case for the statement, essentially showing that it does seem to work. When we're convinced that the statement is true, we set about trying to develop a mathematical proof to show that it is always true. We do this by testing the statement for different values. For example, if we test `P(1)`, we get that `f_4=3` (from the Fibonacci sequence), and `3` is a multiple of `3`. We conclude that `P(1)` is true and continue with the proof.

Then, `EE m in ZZ ∋ 3m=f_(4n)`.

The next part of the proof is the inductive hypothesis.

Inductive hypothesis: `f_(4k)=3m`.

Note we have replaced `n` with `k` as part of the hypothesis. We will now attempt to prove that the statement is true for `n=k+1` (or `k-1`). If this is true, then the statement is true `AA n in NN`. Replace `k` with `k+1`.

`=>f_(4(k+1))=3m`.

Essentially, we will try to make the left-hand side look like the right. In this case, we'll focus on the left side.

First, we can distribute to get `f_(4(k+1))=f_(4k+4)`. Because this is a Fibonacci number, we know that each number is equal to the sum of the two numbers which precede it. We can see this by looking at the Fibonacci sequence: `1,1,2,3,5,8,13,21,...`.

Therefore, `f_(4k+4)=f_(4k+3)+f_(4k+2)`.

Continuing:

`f_(4k+4)=f_(4k+3)+f_(4k+2)=(f_(4k+2)+f_(4k+1))+(f_(4k+1)+f_(4k))`

`=>2f_(4k+1)+f_(4k+2)+f_(4k)`

`=2f_(4k+1)+(f_(4k+1)+f_(4k))+f_(4k)`

`=3f_(4k+1)+2f_(4k)`

Recall our inductive hypothesis: `f_(4k)=3m`. We can substitute in `3m` for `f_(4k)`.

`=>3f_(4k+1)+2(3m)`

Factor out a `3`:

`=>3(f_(4k+1)+2m)`

So we have that `f_(4(k+1))=3(f_(4k+1)+2m)`. We wanted to prove that `f_(4(k+1))=3m` for some `m in ZZ`.

Since `(f_(4k+1)+2m) in ZZ, 3` is a multiple of `f_(4(k+1))`, we have shown that the statement is true for `n=k+1`.

`:.` By the process of mathematical induction, the statement is true for all `n in NN ∎`.

Answer 2

Use modulo `3` arithmetic...

Explanation:

The Fibonacci numbers can be defined by the rules:

`{(f_1 = 1), (f_2 = 1), (f_(n+2) = f_(n+1) + f_n " for " n >= 1) :}`

Note that any pair of consecutive terms determines all of the following terms, so if the pair `1, 1` of consecutive terms reoccurs then the sequence repeats from that point.

If we apply these rules in modulo `3` arithmetic, we get the sequence:

`1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0,...`

Note that modulo `3`, we have `f_9 = f_1 = 1` and `f_10 = f_2 = 1`, so the sequence repeats every `8` terms.

Note also that `f_4 = 0` and `f_8 = 0` modulo `3`.

Hence every term of the form `f_(4n)` is `0` modulo `3`.