# Integers and Induction Question (formula for Fibonacci numbers)

I've been working on this for a while now and I can't seem to get anywhere. Could anyone help me out or walk me through a solution? Any help at all would be wonderful. Thank you.

Find a, b such that $Fn = a( \frac {1 + \sqrt 5}{2})^n + b( \frac {1 - \sqrt5}{2})^n$ for every $n ∈ \mathbb N$. Prove by induction that this is true for $Fn$ is correct for every $n ∈ \mathbb N$.

-

To find $a$ and $b$, just substitute $n=0$ and $n=1$ into the equation

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

to get two equations in the two unknowns $a$ and $b$. $F_0=0$ and $F_1=1$, so you get this system:

\left\{\begin{align*} &a+b=0\\\\ &\left(\frac{1+\sqrt5}2\right)a+\left(\frac{1-\sqrt5}2\right)b=1\;. \end{align*}\right.

The second equation may look a little ugly, but the system is actually very easy to solve, and the solution isn’t very ugly.

Once you have $a$ and $b$, you have to show by induction that if we define

$$x_n=a\left(\frac{1+\sqrt5}2\right)^n+b\left(\frac{1-\sqrt5}2\right)^n\;,$$

then $F_n=x_n$ for all $n\ge 0$. This will certainly be true for $n=0$ and $n=1$, since you used those values of $F_n$ to get $a$ and $b$ in the first place. To finish the job, you’ll have the induction hypothesis that $F_k=x_k$ for all $k\le n$ (for some $n\ge 1$, and your induction step will be showing that $F_{n+1}=x_{n+1}$. Of course you know that $F_{n+1}=F_n+F_{n-1}$, and your induction hypothesis tells you that $F_n+F_{n-1}=x_n+x_{n-1}$, so your task will really be to prove that $x_n+x_{n-1}=x_{n+1}$ for the particular $a$ and $b$ that you found initially. If you have the right $a$ and $b$, this is fairly straightforward algebra.

-