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

Don't even know where to start!

Thanks.

##### 2 Answers

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

I will use induction.

**Proof.**

To complete a proof by induction, you begin with a general statement,

To prove a proposition is true using induction, we show that if the statement is true for

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

Then,

The next part of the proof is the inductive hypothesis.

Inductive hypothesis:

Note we have replaced

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

Therefore,

Continuing:

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

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

Recall our inductive hypothesis:

Factor out a

So we have that

Since

Use modulo

#### 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

If we apply these rules in modulo

#1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0,...#

Note that modulo

Note also that

Hence every term of the form