# Induction technique on the fibonacci sequence [duplicate]

This question already has an answer here:

$$F_n=\frac{(\frac{1+\sqrt{5}}{2})^{n}-(\frac{1-\sqrt{5}}{2})^{n}}{\sqrt{5}}$$

Proof: Let n=1 thus, \begin{align*} F_1&=\frac{(\frac{1+\sqrt{5}}{2})^{1}-(\frac{1-\sqrt{5}}{2})^{1}}{\sqrt{5}}\\ &=\frac{\frac{1+\sqrt{5}}{2}-\frac{1-\sqrt{5}}{2}}{\sqrt{5}}\\ &=\frac{\frac{1+\sqrt{5}-1+\sqrt{5}}{2}}{\sqrt{5}}\\ &=\frac{\frac{\sqrt{5}+\sqrt{5}}{2}}{\sqrt{5}}\\ &=\frac{\frac{2\sqrt{5}}{2}}{\sqrt{5}}\\ &=\frac{{\sqrt{5}}}{\sqrt{5}}\\ &=1 \end{align*} Suppose $$F_k=\frac{(\frac{1+\sqrt{5}}{2})^{k}-(\frac{1-\sqrt{5}}{2})^{k}}{\sqrt{5}}$$ Also $F(k+1)=F(k)+F(k-1)$ \begin{align*} F(k)+F(k-1)&=\frac{(\frac{1+\sqrt{5}}{2})^{k}-(\frac{1-\sqrt{5}}{2})^{k}}{\sqrt{5}}+\frac{(\frac{1+\sqrt{5}}{2})^{k-1}-(\frac{1-\sqrt{5}}{2})^{k-1}}{\sqrt{5}}\\ &=\frac{(\frac{1+\sqrt{5}}{2})^{k}+(\frac{1+\sqrt{5}}{2})^{k-1}-(\frac{1-\sqrt{5}}{2})^{k}-(\frac{1-\sqrt{5}}{2})^{k-1}}{\sqrt{5}}\\ &=\frac{((\frac{1+\sqrt{5}}{2})+1)(\frac{1+\sqrt{5}}{2})^{k-1}-((\frac{1-\sqrt{5}}{2})+1)(\frac{1-\sqrt{5}}{2})^{k-1}}{\sqrt{5}}\\ &=\frac{((\frac{3+\sqrt{5}}{2}))(\frac{1+\sqrt{5}}{2})^{k-1}-((\frac{3-\sqrt{5}}{2}))(\frac{1-\sqrt{5}}{2})^{k-1}}{\sqrt{5}}\\ &=\frac{((\frac{1+\sqrt{5}}{2})^{2})(\frac{1+\sqrt{5}}{2})^{k-1}-((\frac{1-\sqrt{5}}{2})^{2})(\frac{1-\sqrt{5}}{2})^{k-1}}{\sqrt{5}}\\ &=\frac{(\frac{1+\sqrt{5}}{2})^{k+1}-(\frac{1-\sqrt{5}}{2})^{k+1}}{\sqrt{5}}\hfill \end{align*}

I was told there was a mistake but I feel this is right can I get clarification on my proof if it seems right?

## marked as duplicate by Dietrich Burde, Community♦Oct 28 '16 at 15:27

• You should have two bases cases $F_1$ and $F_2$ for the inductive step to work on. – Ian Miller Oct 28 '16 at 15:21
• In your initial case you only proved $F_1$. In your inductive step you find $F_{k+1}$ using both $F_k$ and $F_{k-1}$. If we use the inductive step to prove $F_3$ it relies upon both $F_2$ and $F_1$ being true but you haven't established that $F_2$ is true. – Ian Miller Oct 28 '16 at 15:25
• Also instead of doing $F_2$ you could do $F_0$ which is slightly easier arithmetically. Then $F_2$ is done inductively from $F_1$ and $F_0$. – Ian Miller Oct 28 '16 at 15:28