1
$\begingroup$

This question already has an answer here:

1) Let $F_n$ denote the $n^t$$^h$ Fibonacci number. Prove by induction:

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

Clear explanation would be appreciated.

$\endgroup$

marked as duplicate by whuber, muzzlator, Dominic Michaelis, vonbrand, Amzoti Apr 3 '13 at 16:44

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

0
$\begingroup$

There's a clear explanation on this link Fibonacci series . Key point of the $n$th term of a fibonacci series is the use of golden ratio. $\phi =\dfrac{1+\sqrt5}{2}$. There has been a use of Matrices in the proof.

$\endgroup$
0
$\begingroup$

Put $$\varphi=\frac{1+\sqrt 5}2,\;\lambda=\frac{1-\sqrt5}2.$$ These are the roots to the quadratic equation $x^2-x-1=0,$ so in particular, we have $$\varphi^2=\varphi+1,\;\lambda^2=\lambda+1.$$ Note also that $$\varphi-\lambda=\sqrt5,\;\lambda+\varphi=1.$$

Since $F_0=F_1=1,$ then $\varphi-\lambda=\sqrt5$ gives us the first base case, so that $$F_1=F_0=\frac1{\sqrt5}(\varphi-\lambda)=\frac1{\sqrt5}\bigl((\varphi+1)-(\lambda+1)\bigr)=\frac1{\sqrt5}(\varphi^2-\lambda^2)$$ gives us the second base case.

Now suppose $F_n=\frac1{\sqrt5}(\varphi^{n+1}-\lambda^{n+1})$ and $F_{n+1}=\frac1{\sqrt5}(\varphi^{n+2}-\lambda^{n+2})$ for some $n.$ Note that $$\varphi^{n+1}-\lambda^{n+1}=(\varphi-\lambda)\sum_{k=0}^n\varphi^{n-k}\lambda^k=\sqrt5\sum_{k=0}^n\varphi^{n-k}\lambda^k$$ and likewise $$\varphi^{n+2}-\lambda^{n+2}=\sqrt5\sum_{k=0}^{n+1}\varphi^{n+1-k}\lambda^k,$$ so $$\begin{align}F_{n+2} &= F_n+F_{n+1}\\ &= \sum_{k=0}^n\varphi^{n-k}\lambda^k+\sum_{k=0}^{n+1}\varphi^{n+1-k}\lambda^k\\ &= \lambda^{n+1}+\sum_{k=0}^n\varphi^{n-k}\lambda^k+\sum_{k=0}^n\varphi^{n+1-k}\lambda^k\\ &= \lambda^{n+1}+\sum_{k=0}^n\varphi^{n-k}\lambda^k+\varphi\sum_{k=0}^n\varphi^{n-k}\lambda^k\\ &= 1\cdot\lambda^{n+1}+(1+\varphi)\sum_{k=0}^n\varphi^{n-k}\lambda^k.\end{align}$$ Now, recalling that $\varphi+\lambda=1$ and $1+\varphi=\varphi^2,$ we have $$\begin{align}F_{n+2} &= (\varphi+\lambda)\cdot\lambda^{n+1}+\varphi)^2\sum_{k=0}^n\varphi^{n-k}\lambda^k\\ &= \varphi\lambda^{n+1}+\lambda^{n+2}+\sum_{k=0}^n\varphi^{n+2-k}\lambda^k\\ &= \sum_{k=0}^{n+2}\varphi^{n+2-k}\lambda^k\\ &= \frac1{\varphi-\lambda}(\varphi-\lambda)\sum_{k=0}^n\varphi^{n+2-k}\lambda^k\\ &= \frac1{\varphi-\lambda}(\varphi^{n+3}-\lambda^{n+3}),\end{align}$$ and since $\varphi-\lambda=\sqrt5,$ the induction step is completed.

$\endgroup$
0
$\begingroup$

Hint (if you know something about discrete dynamical systems)

you can look for solutions of the d.d.s. of the form $A \lambda_1^n + B\lambda_2^n$, where $\lambda_i$ are the solutions of the associated equation $p(\lambda) = \lambda^2 - \lambda - 1 = 0$. $A,B$ are to be determined by the initial condition $F_0 = 0$, $F_1 = 1$.

$\endgroup$
  • $\begingroup$ Unless there is a very good reason, we prefer not to arbitrarily delete good content: the answers could well help other users in the future. $\endgroup$ – robjohn May 13 '13 at 1:08

Not the answer you're looking for? Browse other questions tagged or ask your own question.