1.13
Exercise 1.13: Prove that Fib(n) is the closest integer to ϕ n 5 \frac{\phi ^ n}{\sqrt 5} 5 ϕ n ϕ = 1 + 5 2 \phi=\frac{1+\sqrt 5}{2} ϕ = 2 1 + 5 ψ = 1 − 5 2 \psi = \frac{1-\sqrt 5}{2} ψ = 2 1 − 5 F i b ( n ) = ϕ n − ψ n 5 Fib(n)=\frac{\phi^n - \psi^n}{5} F i b ( n ) = 5 ϕ n − ψ n
First of all, we know the following two equations are true:
F i b ( 0 ) = 0 = ϕ 0 − ψ 0 5 = 1 − 1 5
Fib(0) = 0 = \frac{\phi^0-\psi^0}{\sqrt{5}} = \frac{1-1}{\sqrt 5}
F i b ( 0 ) = 0 = 5 ϕ 0 − ψ 0 = 5 1 − 1
F i b ( 1 ) = 1 = ϕ 1 − ψ 1 5 = 1 + 5 2 − 1 − 5 2 5
Fib(1) = 1 = \frac{\phi^1-\psi^1}{\sqrt 5} = \frac{\frac{1+\sqrt 5}{2} - \frac{1-\sqrt 5}{2}}{\sqrt 5}
F i b ( 1 ) = 1 = 5 ϕ 1 − ψ 1 = 5 2 1 + 5 − 2 1 − 5
Then we suppose that F i b ( n ) = ϕ n − ψ n 5 Fib(n) = \frac{\phi^n - \psi^n}{\sqrt 5} F i b ( n ) = 5 ϕ n − ψ n n ≥ 2 n\ge2 n ≥ 2
And from the definition of Fibonacci numbers we have the following:
F i b ( n + 1 ) = F i b ( n ) + F i b ( n − 1 ) = ϕ n − ψ n 5 + ϕ n − 1 − ψ n − 1 5
Fib(n+1) = Fib(n) + Fib(n-1) = \frac{\phi^n - \psi^n}{\sqrt 5} + \frac{\phi^{n-1} - \psi^{n-1}}{\sqrt 5}
F i b ( n + 1 ) = F i b ( n ) + F i b ( n − 1 ) = 5 ϕ n − ψ n + 5 ϕ n − 1 − ψ n − 1
= ( ϕ n + ϕ n − 1 ) − ( ψ n + ψ n − 1 ) 5
= \frac{(\phi^n + \phi^{n-1}) - (\psi^n + \psi^{n-1})}{\sqrt 5}
= 5 ( ϕ n + ϕ n − 1 ) − ( ψ n + ψ n − 1 )
Now the only question is if the following equations are true?
ϕ n + 1 = ϕ n + ϕ n − 1
\phi^{n+1} = \phi^n + \phi^{n-1}
ϕ n + 1 = ϕ n + ϕ n − 1
ψ n + 1 = ψ n + ψ n − 1
\psi^{n+1} = \psi^n + \psi^{n-1}
ψ n + 1 = ψ n + ψ n − 1
If the above equations are true, then the previous equations can be deducted into:
F i b ( n + 1 ) = F i b ( n ) + F i b ( n − 1 ) = ϕ n + 1 + ψ n + 1 5
Fib(n+1)=Fib(n)+Fib(n-1) = \frac{\phi^{n+1} + \psi^{n+1}}{\sqrt 5}
F i b ( n + 1 ) = F i b ( n ) + F i b ( n − 1 ) = 5 ϕ n + 1 + ψ n + 1
So the equation F i b ( n ) = ϕ n − ψ n 5 Fib(n) = \frac{\phi^n - \psi^n}{\sqrt 5} F i b ( n ) = 5 ϕ n − ψ n n ≥ 0 n\ge0 n ≥ 0
And
∣ ϕ n 5 − F i b ( n ) ∣ = ∣ ϕ n 5 − ϕ n − ψ n 5 ∣ = ∣ ψ n 5 ∣ = ∣ ( 1 − 5 2 ) n 5 ∣ ≤ ∣ 1 − 5 2 5 ∣ = 5 − 1 2 5 = 1 − 1 5 2
\mid \frac{\phi^n}{\sqrt 5} - Fib(n) \mid = \mid \frac{\phi^n}{\sqrt 5} - \frac{\phi^n - \psi^n}{\sqrt 5} \mid = \mid \frac{\psi^n}{\sqrt 5} \mid = \mid \frac{(\frac{1-\sqrt 5}{2})^n}{\sqrt 5} \mid \le \mid \frac{\frac{1-\sqrt 5}{2}}{\sqrt 5} \mid = \frac{\sqrt 5 - 1}{2\sqrt 5} = \frac{1-\frac{1}{\sqrt5}}{2}
∣ 5 ϕ n − F i b ( n ) ∣ = ∣ 5 ϕ n − 5 ϕ n − ψ n ∣ = ∣ 5 ψ n ∣ = ∣ 5 ( 2 1 − 5 ) n ∣ ≤ ∣ 5 2 1 − 5 ∣ = 2 5 5 − 1 = 2 1 − 5 1
= 1 2 − 1 2 5 < 1 2
= \frac{1}{2} - \frac{1}{2\sqrt 5} < \frac{1}{2}
= 2 1 − 2 5 1 < 2 1
So F i b ( n ) Fib(n) F i b ( n ) ϕ n 5 \frac{\phi^n}{\sqrt 5} 5 ϕ n
Now let's examine the previous question: are the following equations true?
ϕ n + 1 = ϕ n + ϕ n − 1
\phi^{n+1} = \phi^n + \phi^{n-1}
ϕ n + 1 = ϕ n + ϕ n − 1
ψ n + 1 = ψ n + ψ n − 1
\psi^{n+1} = \psi^n + \psi^{n-1}
ψ n + 1 = ψ n + ψ n − 1
We firstly examine the equations for n = 0 n=0 n = 0
ϕ 0 = 1
\phi^0 = 1
ϕ 0 = 1
then for n = 1 n=1 n = 1
ϕ 1 = 1 + 5 2
\phi^1 = \frac{1+\sqrt 5}{2}
ϕ 1 = 2 1 + 5
and then for n = 2 n = 2 n = 2
ϕ 2 = ( 1 + 5 2 ) 2 = 1 + 5 + 2 5 4 = 3 + 5 2 = 1 + 1 + 5 2 = ϕ 0 + ϕ 1
\phi^2 = (\frac{1 + \sqrt 5}{2})^2 = \frac{1 + 5 + 2\sqrt 5}{4} = \frac{3 + \sqrt 5}{2} = 1 + \frac{1+\sqrt 5}{2} = \phi^0 + \phi^1
ϕ 2 = ( 2 1 + 5 ) 2 = 4 1 + 5 + 2 5 = 2 3 + 5 = 1 + 2 1 + 5 = ϕ 0 + ϕ 1
Suppose for all n ≥ 2 n \ge 2 n ≥ 2 ϕ n = ϕ n − 1 + ϕ n − 2 \phi^n = \phi^{n-1} + \phi^{n-2} ϕ n = ϕ n − 1 + ϕ n − 2
ϕ n + 1 = ϕ n ϕ = ( ϕ n − 1 + ϕ n − 2 ) ϕ = ϕ n + ϕ n − 1
\phi^{n+1} = \phi^n \phi = (\phi^{n-1} + \phi^{n-2}) \phi = \phi^n + \phi^{n-1}
ϕ n + 1 = ϕ n ϕ = ( ϕ n − 1 + ϕ n − 2 ) ϕ = ϕ n + ϕ n − 1
So indeed that ϕ n + 1 = ϕ n + ϕ n − 1 \phi^{n+1} = \phi^{n} + \phi^{n-1} ϕ n + 1 = ϕ n + ϕ n − 1
Now let's see if ψ n + 1 = ψ n + ψ n − 1 \psi^{n+1} = \psi^{n} + \psi^{n-1} ψ n + 1 = ψ n + ψ n − 1
Since ψ 0 = 1 \psi^0 = 1 ψ 0 = 1 ψ 1 = 1 − 5 2 \psi^1 = \frac{1-\sqrt 5}{2} ψ 1 = 2 1 − 5
ψ 2 = ( 1 − 5 2 ) 2 = 1 + 5 − 2 5 2 = 3 − 5 2 = 1 + 1 − 5 2 = ψ 0 + ψ 1
\psi^{2} = (\frac{1-\sqrt 5}{2})^2 = \frac{1+5-2\sqrt 5}{2} = \frac{3-\sqrt 5}{2} = 1 + \frac{1 - \sqrt 5}{2} = \psi^0 + \psi^1
ψ 2 = ( 2 1 − 5 ) 2 = 2 1 + 5 − 2 5 = 2 3 − 5 = 1 + 2 1 − 5 = ψ 0 + ψ 1
Suppose for all n ≥ 2 n \ge 2 n ≥ 2 ψ n = ψ n − 1 + ψ n − 2 \psi^n = \psi^{n-1} + \psi^{n-2} ψ n = ψ n − 1 + ψ n − 2
ψ n + 1 = ψ ψ n = ψ ( ψ n − 1 + ψ n − 2 ) = ψ n + ψ n − 1
\psi^{n+1} = \psi\psi^n=\psi(\psi^{n-1} + \psi^{n-2})=\psi^n+\psi^{n-1}
ψ n + 1 = ψ ψ n = ψ ( ψ n − 1 + ψ n − 2 ) = ψ n + ψ n − 1
So indeed, ψ n + 1 = ψ n + ψ n − 1 \psi^{n+1}=\psi^n+\psi^{n-1} ψ n + 1 = ψ n + ψ n − 1 n ≥ 0 n \ge 0 n ≥ 0