Algebra+ 08 - Fibonacci: UNIZOR.COM - Math+ & Problems - Algebra

Notes to a video lecture on http://www.unizor.com

Algebra+ 08 - Fibonacci

Note
We will use both terms average and mean interchangeably, but usually with proper qualification, like geometric mean or harmonic average.

Problem A

The Fibonacci sequence F(n) for integer n=0,1,2,3... is a sequence of numbers that starts with
F(0)=0, F(1)=1
and satisfies the rule for any integer n≥0:
F(n) + F(n+1) = F(n+2)
which results in
F(2)=F(0)+F(1)=0+1=1
F(3)=F(1)+F(2)=1+1=2
F(4)=F(2)+F(3)=1+2=3
F(5)=F(3)+F(4)=2+3=5
F(6)=F(4)+F(5)=3+5=8
F(7)=F(5)+F(6)=5+8=13
etc.
Derive formula for the Fibonacci sequence.

Hint A
Prove that if the following equation
Xⁿ + Xⁿ⁺¹ = Xⁿ⁺²
is true for n=0, it's true for any other positive integer n.

Solution A

Let's prove the statement in the Hint A above by using mathematical induction.
For n=0 it's assumed to be true.
Assume, it's true for some n, that is assume that
Xⁿ + Xⁿ⁺¹ = Xⁿ⁺²
is true for some n.
We have to prove that it's true for n+1, that is we have to prove that
Xⁿ⁺¹ + Xⁿ⁺² = Xⁿ⁺³
Indeed,
Xⁿ⁺¹ + Xⁿ⁺² =
= X·(Xⁿ + Xⁿ⁺¹) =
= [use assumption for n] =
= X·Xⁿ⁺² = Xⁿ⁺³

The formula
Xⁿ + Xⁿ⁺¹ = Xⁿ⁺²
looks very much like the definition for Fibonacci sequence
F(n) + F(n+1) = F(n+2)
But are there any X that satisfy the initial conditions for Fibonacci sequence
F(0)=0, F(1)=1?
If yes, the solution for a formula describing the sequence would be solved.

The answer is YES.
First of all, let's find value(s) of X for n=0, that is let's solve the equation
Xⁿ + Xⁿ⁺¹ = Xⁿ⁺²
for n=0.
X⁰ + X¹ = X² or
1 + X = X² or
X² − X − 1 = 0
It has two solutions
X_1,2 = (1 ± √1+4)/2 =
= (1 ± √5)/2
Both of these values, if used in the expression
Xⁿ + Xⁿ⁺¹ = Xⁿ⁺²
transform it into identity for any natural n because they do it for n=0 and because we have proven above by induction that, if true for n=0, it's true for all natural n.

Let's check if a condition
F(n) + F(n+1) = F(n+2)
is satisfied for F₁(n)=X₁ⁿ and F₂(n)=X₂ⁿ.

For X₁:
F₁(n) = [(1+√5)/2]ⁿ
F₁(n+1) = [(1+√5)/2]ⁿ⁺¹
F₁(n) + F₁(n+1) =
= [(1+√5)/2]ⁿ+[(1+√5)/2]ⁿ⁺¹=
= [(1+√5)/2]ⁿ·[1+(1+√5)/2] =
= [(1+√5)/2]ⁿ·[(3+√5)/2] =
= [(1+√5)/2]ⁿ·[(6+2√5)/4] =
= [(1+√5)/2]ⁿ·[(1+2√5+5)/4] =
= [(1+√5)/2]ⁿ·[(1+√5)/2]² =
= [(1+√5)/2]ⁿ⁺² = F₁(n+2)
Similarly, the condition
F(n) + F(n+1) = F(n+2)
is satisfied for X₂, we omit analogous calculations.

While the main condition of Fibonacci sequence, connecting any element with a sum of two preceding ones, is satisfied for both variants above, initial conditions for Fibonacci sequence
F(0)=1, F(1)=1
are not yet satisfied.

Notice that if
X₁ⁿ + X₁ⁿ⁺¹ = X₁ⁿ⁺² and
X₂ⁿ + X₂ⁿ⁺¹ = X₂ⁿ⁺² then
p·X₁ⁿ+q·X₂ⁿ +
+ p·X₁ⁿ⁺¹+q·X₂ⁿ⁺¹ =
= p·X₁ⁿ⁺²+q·X₂ⁿ⁺²
for any p and q.
So, the obvious suggestion is to find such p and q that a function
F(n) = p·X₁ⁿ+q·X₂ⁿ
where X₁=(1+√5)/2 and
X₂=(1−√5)/2, would satisfy the initial condition as well as the formula connecting the next sequence value with a sum of two preceding ones.

Condition F(0)=0 gives
p·X₁⁰+q·X₂⁰ = 0
Any non-zero number raised to the power of 0 gives 1. So, this condition is equivalent to
p + q = 0
Condition F(1)=1 gives
p·X₁¹+q·X₂¹ = 1
Any non-zero number raised to the power of 1 is itself. So, this condition is
p·X₁¹ + q·X₂¹ = 1 or
p·(1+√5)/2 + q·(1−√5)/2 = 1

Now we have a system of two linear equations with two unknowns p and q.
From the first equation
q = −p
Substitute it to the second equation:
p·(1+√5)/2 − p·(1−√5)/2 = 1
from which follows
p = 1/√5 and
q = −1/√5

The final formula for Fibonacci sequence is, therefore,
F(n) = (1/√5)·[(1+√5)/2]ⁿ −
− (1/√5)·[(1−√5)/2]ⁿ