Originally Posted by

**ossinator** Hello. I searched for a topic for the same question, but my queries were fruitless, although they returned some similar questions. If i have missed it, please lock this one, and redirect me to the proper thread.

It's not a homework assignment, but a personal inquiry due to some home studies I'm performing. I have a little background in maths, but haven't done anything of the sorts in quite a while ( > 4 years), and was looking for some confirmation on my work. Anyhow, here's the problem.

Prove that $\displaystyle i$th Fibonacci number satisfies the equality

$\displaystyle

F_n = \frac{{\phi}^n - {\hat{\phi}}^n}{\sqrt{5}}

$

Where $\displaystyle \phi $ is the golden ratio and $\displaystyle \hat{\phi} $ is its conjugate.

What I've done:

Proof by induction.

Base cases:

$\displaystyle

F_0 = {\phi}^0 - {\hat{\phi}}^0

$

$\displaystyle

\\F_0 = 0

$

$\displaystyle

F_1 = {\phi}^1 - {\hat{\phi}}^1

$

$\displaystyle

\\F_1 = 1

$

Inductive hypothesis:

Suppose that it holds for $\displaystyle F_n$ and $\displaystyle F_{n-1}$

We also know, that $\displaystyle \phi$ and $\displaystyle \hat{\phi}$ are the roots of the equation $\displaystyle x^2 = x + 1$

Therfore, if we multiply both sides of the equation by $\displaystyle {\phi} ^ {n-1}$, we get $\displaystyle {\phi}^{n+1} = {\phi}^{n} + {\phi}^{n-1} $

The same for $\displaystyle \hat{\phi}$.

From that we trivially arrive at

$\displaystyle

\frac{{\phi}^{n+1} - {\hat{\phi}}^{n+1}}{\sqrt5} = \frac{{\phi}^n + {\phi}^{n-1}}{\sqrt5} - \frac{{\hat{\phi}}^{n} + {\hat{\phi}}^{n-1}}{\sqrt5}

$

Which is what we were trying to prove. Can you please confirm my reasoning? I'm not sure if I'm allowed such an assumption in my inductive hypothesis, and also my reasoning looks a little circular. If there's a gap, can you please point it out to me, as well as any hints at getting the proper solution?