$h_0 = 0 $
$ h_1 = 1 $
$h_j = h_{j-1}+ h_{j-2} $ for j >=2
I want to prove with strong induction that $h_j = \frac{1}{\sqrt{5}} \left[ \left( \frac{1 + \sqrt{5}}2 \right)^j - \left( \frac{1 - \sqrt{5}}2 \right)^j \right]$ for j>=0
For the base cases,
n=0, $\frac{1}{\sqrt{5}} \left[ \left( \frac{1 + \sqrt{5}}2 \right)^0 - \left( \frac{1 - \sqrt{5}}2 \right)^0 \right]$ = 0
n=1, $\frac{1}{\sqrt{5}} \left[ \left( \frac{1 + \sqrt{5}}2 \right)^1- \left( \frac{1 - \sqrt{5}}2 \right)^1 \right] = 1$
Which agrees with $h_0$ and $ h_1$.
I know that I assume $h_p = \frac{1}{\sqrt{5}} \left[ \left( \frac{1 + \sqrt{5}}2 \right)^p - \left( \frac{1 - \sqrt{5}}2 \right)^p \right]$ for p>= 0 and show that $h_{p+1} = \frac{1}{\sqrt{5}} \left[ \left( \frac{1 + \sqrt{5}}2 \right)^{p+1} - \left( \frac{1 - \sqrt{5}}2 \right)^{p+1} \right]$. My problem is, I don't how where to show that this is true.
Hint:
the caracteristic equation is
$x^2-x-1=0$
the solutions are $x_1=\frac{1+\sqrt{5}}{2}$ $x_2=\frac{1-\sqrt{5}}{2}$
thus
$h_n=ax_1^n+bx_2^n$
we get the constant $a$ and $b$ using initial conditions.