Answer to Question #256693 in Discrete Mathematics for Alina

Question

Let f_n be the n^th Fibonacci number. Prove that, for n > 0 [Hint: use strong induction]:

f_n = 1/√5 [((1+√5)/2)ⁿ - ((1-√5)/2)ⁿ ]

Answer 1

for n=1:

$F_1=1$

let for n=k:

$F_k=\frac{(\frac{1+\sqrt5}{2})^k-(\frac{1-\sqrt5}{2})^k}{\sqrt5}$

then for n=k+1:

$F_{k+1}=F_k+F_{k-1}=\frac{(\frac{1+\sqrt5}{2})^{k}-(\frac{1-\sqrt5}{2})^{k}}{\sqrt5}+\frac{(\frac{1+\sqrt5}{2})^{k-1}-(\frac{1-\sqrt5}{2})^{k-1}}{\sqrt5}=$

$=\frac{1}{\sqrt 5}((\frac{1+\sqrt 5}{2})^k(1+\frac{2}{1+\sqrt 5})-(\frac{1-\sqrt 5}{2})^k(1+\frac{2}{1-\sqrt 5}))$

$(1+\frac{2}{1+\sqrt 5})(\frac{1-\sqrt 5}{1-\sqrt 5})=\frac{1+\sqrt 5}{2}$

$(1+\frac{2}{1-\sqrt 5})(\frac{1+\sqrt 5}{1+\sqrt 5})=\frac{1-\sqrt 5}{2}$

So:

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