Proving a slight variation of the fibonacci formula using complete induction

Question

I learned this formula for the Fibonacci series, and its respective proof in one of my Computer Science classes.

F(0) = 0; F(1) = 1; F(2) = 1

However, I am taking an abstract mathematics class and this slightly different formula has taken me nowhere for the past 2 hours...

I end up getting $3 + \sqrt 5 / 1 + \sqrt 5$ and $ 3 - \sqrt 5 / 1 - \sqrt 5$ in a part where I should get $1 + \sqrt 5 /2$ and $ 1 - \sqrt 5 /2$ to generate the formula in terms of n+1 by complete induction.

I noticed one of the differences is the boundaries, one starts with F(0) = 1, the other one with F(0) = 0.

The first one is easily proven in 6 lines...

The second one gives me these weird values that I can't reduce.

Can someone explain to me how to approach this?

Answer 1

First, I will tell you how the formula can be derived. The method can be generalized and is very useful.

The key idea is to start with the try $f(n)=x^n$. Because of $f(n)=f(n-1)+f(n-2)$ we get $x^n=x^{n-1}+x^{n-2}$. Dividing by $x^{n-2}$ this gives the characteristic equation $x^2=x+1$. Solving $x^2-x-1=0$, we get $\alpha=\frac{1+\sqrt{5}}{2}$ and $\beta=\frac{1-\sqrt{5}}{2}$. The general solution is therefore

$$f(n)=c_1\alpha^n+c_2\beta^n$$

Using the initial condition $f(0)=1,f(1)=1$ you can calculate $c_1$ and $c_2$.

The method works well, if the roots are distinct.

Answer 2

$F(0)=1$

$F(1)=1$

$F(n)=F(n-1)+F(n-2)$

$\alpha:=\frac{1+\sqrt{5}}{2}$, $\beta:=\frac{1-\sqrt{5}}{2}$

Claim : $$F(n)=\frac{\alpha^{n+1}-\beta^{n+1}}{\sqrt{5}}$$

Proof :

$n=0$ : $$F(0)=\frac{\alpha-\beta}{\sqrt{5}}=1$$ $n=1$ : $$F(1)=\frac{\alpha^2-\beta^2}{\sqrt{5}}=F(0)(\alpha+\beta)=1$$

Base case :

$n=2$ : $$F(2)=\frac{\alpha^3-\beta^3}{\sqrt{5}}=\frac{(\alpha-\beta)(\alpha^2+\alpha\beta+\beta^2)}{\sqrt{5}}=2F(0)=2=F(0)+F(1)$$

Remark : $$\alpha^2+\alpha\beta+\beta^2=(\alpha+\beta)^2-\alpha\beta=1-(-1)=2$$

Induction step :

$$F(n+1)=F(n)+F(n-1)=\frac{1}{\sqrt{5}}(\alpha^{n+1}-\beta^{n+1}+\alpha^n-\beta^n)$$ $$=\frac{1}{\sqrt{5}}(\alpha^n(\alpha+1)-\beta^n(\beta+1)$$

Now, $\alpha^2=\alpha+1$ , $\beta^2=\beta+1$ , because $\alpha$ and $\beta$ are the roots of $x^2-x-1$, so finally we get

$$\frac{1}{\sqrt{5}}(\alpha^{n+2}-\beta^{n+2})$$, which completes the proof.