Return to Answer

Your approach to prove a theorem usually depends on how you define things. As Elaqqad said, you can't get rid of induction when you define the Fibonacci sequence by Induction. But if you define Fibonacci sequence from the start with no induction, you can prove some of its features without induction.

I usually suggest to be pragmatic, and accept mathematical induction. But, as you wish, I DO prove Fibonacci sequence is periodic mod 5 without using induction.

Let's start from a non-inductive definition of Fibonacci sequence. I use Binet's formula, as a closed-form expression of the Fibonnaci number.

Fibonnaci number is defined as a function of $n$, which outputs an Integer, and defined as*:

$F[n] := \cfrac{1}{\sqrt{5}}\cdot\left(\cfrac{1+\sqrt{5}}{2}\right)^n-\cfrac{1}{\sqrt{5}}\cdot\left(\cfrac{1-\sqrt{5}}{2}\right)^n$

We are about to show $$F_{n}\equiv F_{n+20}\pmod 5$$ for all $n \geq 2$

Actually, we also calculate the reminder. We prove that:

$F[n+20]-F[n]=10945.F[n]+6765F[n−1]$

Doing this is really cumbersome. You can't do this by hand, but using a computational software program like Mathematica as a form of Automated theorem proving you can do it easily:

Define the functions as above statement, and do this in Mathematica:

Simplify[f[n + 20] - f[n] - 10945 f[n] - 6765 f[n - 1]]

and you get exact zero:

0

which compeltes the proof.

I'm trying to extract the exact intermediatory simplifying steps from Mathematica. I'll post it as soon as I get it.

* I am not going to prove that F(n) is actually an integer here.

Your approach to prove a theorem usually depends on how you define things. As Elaqqad said, you can't get rid of induction when you define the Fibonacci sequence by Induction. But if you define Fibonacci sequence from the start with no induction, you can prove some of its features without induction.

I usually suggest to be pragmatic, and accept mathematical induction. But, as you wish, I DO prove Fibonacci sequence is periodic mod 5 without using induction.

Let's start from a non-inductive definition of Fibonacci sequence. I use Binet's formula, as a closed-form expression of the Fibonnaci number.

Fibonnaci number is defined as a function of $n$, which outputs an Integer, and defined as*:

$F[n] := \cfrac{1}{\sqrt{5}}\cdot\left(\cfrac{1+\sqrt{5}}{2}\right)^n-\cfrac{1}{\sqrt{5}}\cdot\left(\cfrac{1-\sqrt{5}}{2}\right)^n$

We are about to show $$F_{n}\equiv F_{n+20}\pmod 5$$ for all $n \geq 2$

Actually, we also calculate the reminder. We prove that:

$F[n+20]-F[n]=10945.F[n]+6765F[n−1]$

Doing this is really cumbersome. You can't do this by hand, but using a computational software program like Mathematica as a form of Automated theorem proving you can do it easily:

Define the functions as above statement, and do this in Mathematica:

Simplify[f[n + 20] - f[n] - 10945 f[n] - 6765 f[n - 1]]

and you get exact zero:

0

which compeltes the proof.

I'm trying to extract the exact intermediatory simplifying steps from Mathematica. I'll post it as soon as I get it.

* I am not going to prove that F(n) is actually an integer here.

It really depends on how you define things. As Elaqqad said, you can't get rid of induction when you define the sequence by Induction. But if you define it from the start with no induction, you can prove some of its features without induction. So, be pragmatic. But, as you wish, I do prove Fibonacci sequence is periodic mod 5 without using induction.

Let's start from a non-inductive definition of Fibonacci sequence. I use Binet formula, as a closed-form expression of the Fibonnaci number.

Fibonnaci number is defined as a function of $n$, which outputs an Integer, and defined as*:

$F[n] := \cfrac{1}{\sqrt{5}}\cdot\left(\cfrac{1+\sqrt{5}}{2}\right)^n-\cfrac{1}{\sqrt{5}}\cdot\left(\cfrac{1-\sqrt{5}}{2}\right)^n$

We are about to show $$F_{n}\equiv F_{n+20}\pmod 5$$ for all $n \geq 2$

Actually, we also calculate the reminder. We prove that:

$F[n+20]-F[n]=10945.F[n]+6765F[n−1]$

Doing this is really cumbersome. You can't do this by hand, but using a computational software program like Mathematica, you can do it easily:

Do this in Mathematica:

Simplify[f[n + 20] - f[n] - 10945 f[n] - 6765 f[n - 1]]

and you get:

0

Done. :-)

I'm trying to extract the exact intermediatory simplifying steps from Mathematica. I'll post it as soon as I get it.

• I am not going to prove that F(n) is actually an integer here.

Your approach to prove a theorem usually depends on how you define things. As Elaqqad said, you can't get rid of induction when you define the Fibonacci sequence by Induction. But if you define Fibonacci sequence from the start with no induction, you can prove some of its features without induction.

I usually suggest to be pragmatic, and accept mathematical induction. But, as you wish, I DO prove Fibonacci sequence is periodic mod 5 without using induction.

Let's start from a non-inductive definition of Fibonacci sequence. I use Binet's formula, as a closed-form expression of the Fibonnaci number.

Fibonnaci number is defined as a function of $n$, which outputs an Integer, and defined as*:

$F[n] := \cfrac{1}{\sqrt{5}}\cdot\left(\cfrac{1+\sqrt{5}}{2}\right)^n-\cfrac{1}{\sqrt{5}}\cdot\left(\cfrac{1-\sqrt{5}}{2}\right)^n$

We are about to show $$F_{n}\equiv F_{n+20}\pmod 5$$ for all $n \geq 2$

Actually, we also calculate the reminder. We prove that:

$F[n+20]-F[n]=10945.F[n]+6765F[n−1]$

Doing this is really cumbersome. You can't do this by hand, but using a computational software program like Mathematica as a form of Automated theorem proving you can do it easily:

Define the functions as above statement, and do this in Mathematica:

Simplify[f[n + 20] - f[n] - 10945 f[n] - 6765 f[n - 1]]

and you get exact zero:

0

which compeltes the proof.

I'm trying to extract the exact intermediatory simplifying steps from Mathematica. I'll post it as soon as I get it.

* I am not going to prove that F(n) is actually an integer here.

Let's start from here:

$F[n] := \cfrac{1}{\sqrt{5}}\cdot\left(\cfrac{1+\sqrt{5}}{2}\right)^n-\cfrac{1}{\sqrt{5}}\cdot\left(\cfrac{1-\sqrt{5}}{2}\right)^n$

If we prove this, we are done:

$F[n+20]-F[n]=10945.F[n]+6765F[n−1]$

Do this in Mathematica:

Simplify[f[n + 20] - f[n] - 10945 f[n] - 6765 f[n - 1]]

and you get:

0

Done. :-)

One side note: It really depends on how you define things. You can't get rid of induction when you define the sequence by Induction. But if you define it from the start with no induction, you can prove some of its features without induction. So, be pragmatic.

It really depends on how you define things. As Elaqqad said, you can't get rid of induction when you define the sequence by Induction. But if you define it from the start with no induction, you can prove some of its features without induction. So, be pragmatic. But, as you wish, I do prove Fibonacci sequence is periodic mod 5 without using induction.

Let's start from a non-inductive definition of Fibonacci sequence. I use Binet formula, as a closed-form expression of the Fibonnaci number.

Fibonnaci number is defined as a function of $n$, which outputs an Integer, and defined as*:

$F[n] := \cfrac{1}{\sqrt{5}}\cdot\left(\cfrac{1+\sqrt{5}}{2}\right)^n-\cfrac{1}{\sqrt{5}}\cdot\left(\cfrac{1-\sqrt{5}}{2}\right)^n$

We are about to show $$F_{n}\equiv F_{n+20}\pmod 5$$ for all $n \geq 2$

Actually, we also calculate the reminder. We prove that:

$F[n+20]-F[n]=10945.F[n]+6765F[n−1]$

Doing this is really cumbersome. You can't do this by hand, but using a computational software program like Mathematica, you can do it easily:

Do this in Mathematica:

Simplify[f[n + 20] - f[n] - 10945 f[n] - 6765 f[n - 1]]

and you get:

0

Done. :-)

I'm trying to extract the exact intermediatory simplifying steps from Mathematica. I'll post it as soon as I get it.

• I am not going to prove that F(n) is actually an integer here.