$\begingroup$

Can someone advise on proving the following by induction. I'm assuming strong induction should be used here?

Here $F_n$ is the $n$th Fibonacci number. Prove that

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

$\endgroup$ 2

3 Answers

$\begingroup$

Yes, go with induction.

First, check the base case $$F_1=1$$ That should be easy.

For the inductive step, consider, on the one hand:

(1) $$F_{n+1}= F_n+F_{n-1}$$

Then, write what you need to prove, to have it as a guidance of what you need to get to. That is:

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

Use (1) and your hypothesis and write

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

this translates to

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

---

To finish, note that (a) $${\left(1+\frac{2}{1+\sqrt 5}\right)}{\left(\frac{1-\sqrt 5}{1-\sqrt 5}\right)}={\frac {1+\sqrt 5}{2}}$$ and (b)$${\left(1+\frac{2}{1-\sqrt 5}\right)}{\left(\frac{1+\sqrt 5}{1+\sqrt 5}\right)}={\frac {1-\sqrt 5}{2}}$$

which is exactly what you need to end the proof.

$\endgroup$ 5 $\begingroup$

$$F_n=\frac{\phi^n-\psi^n}{\sqrt5}$$

Then the recurrence relation can be written

$$F_{n+2}-F_{n+1}-F_n=\frac{\phi^2\phi^n-\psi^2\psi^n}{\sqrt5}-\frac{\phi\phi^n-\psi\psi^n}{\sqrt5}-\frac{\phi^n-\psi^n}{\sqrt5}=0.$$

The identify holds if

$$\phi^2-\phi-1=\psi^2-\psi-1=0,$$ which is precisely the case.

The base cases for $F_0=0$ and $F_1=1$ are easy to check.

$\endgroup$ $\begingroup$

It's enough for your induction to work to know that the previous two satisfy this equality. So the induction would work like this:

1) Base. Check that $ F_0, F_1 $ satisfy the equality

2) Step. Assume that $ F_{n-2}, F_{n-1} $ satisfy the equality and derive $ F_n $ for $ n > 1 $

More details can be found here

$\endgroup$