Proving a slight variation of the fibonacci formula using complete induction 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?
 A: $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.  
A: 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.
