Proof by induction of a Fibonacci relation We know:
$F_0 = 0$
$F_1 = 1$
$F_i = F_{i-1} + F_{i-2}$ for $i \geq 2$
Prove by induction:
$F_i = \dfrac{\phi^i-{\phi^{*}}^i}{\sqrt{5}}$
where $\phi = (1+\sqrt{5}) / 2$ and $\phi = (1-\sqrt{5}) / 2$.
My attempt:
Base case: $i = 0$: $F_0 = 0$ (easy to show)
Assume true for $i = k$ and $i = k + 1$.
We have:
$F_k = \dfrac{\phi^k-{\phi^{*}}^k}{\sqrt{5}}$
and 
$F_{k+1} = \dfrac{\phi^{k+1}-{\phi^{*}}^{k+1}}{\sqrt{5}}$
Show it holds for $i = k + 2$ to complete induction. This is where I'm stuck. I have tried:
$F_{k+2} = F_{k+1} + F_{k} = \dfrac{\phi^{k+1}-{\phi^{*}}^{k+1}}{\sqrt{5}} + \dfrac{\phi^k-{\phi^{*}}^k}{\sqrt{5}}$
$F_{k+2} = \dfrac{\phi^k(1+\phi)-{\phi^{*}}^{k}(1+{\phi^*})}{\sqrt{5}}$
but I'm not sure where to go from here. Any help would be appreciated.
 A: Hint $\rm\quad \phi^{\:n+1}\!-\:\bar\phi^{\:n+1} =\ (\phi+\bar\phi)\ (\phi^n\!-\:\bar\phi^n)\ -\ \phi\:\bar\phi\ (\phi^{\:n-1}\!-\:\bar\phi^{\:n-1})$
Hence, upon substituting $\rm\,\ \phi+\bar\phi\ =\ 1\ =\ -\phi\bar\phi\ $ and dividing by $\:\phi-\bar\phi = \sqrt 5\:$ we deduce $\rm\ \ldots$
Remark $\ $ To understand the essence of the matter it's worth emphasizing that such an inductive proof amounts precisely to  showing that $\rm\:f_n\:$ and  $\rm\: \bar{f}_n = (\phi^n-\bar\phi^n)/(\phi-\bar\phi)\:$ are both solutions of the difference equation (recurrence) $\rm\ f_{n+2} = f_{n+1} + f_n\:,\:$ with initial conditions $\rm\ f_0 = 0,\ f_1 = 1\:.\:$ The (trivial) induction simply proves the uniqueness of such solutions. It will prove quite instructive to structure the proof from this standpoint. It will also mean that you can later reuse this uniqueness theorem for recurrences.
Generally, just as above, uniqueness theorems provide very powerful tools for proving equalities - a point which I emphasize in many prior posts. For example, see my prior posts on telescopy and the fundamental theorem of difference calculus, esp. this one.
A: Use $1+\phi=\phi^2$, to get 
$$
F_{k+2} = \dfrac{\phi^k(1+\phi)-{\phi^{*}}^{k}(1+{\phi^{*}})}{\sqrt{5}}= \dfrac{\phi^{k+2}-{\phi^{*}}^{(k+2)}}{\sqrt{5}}
$$
