proving golden ration with induction

Question

If $\displaystyle a=\frac{1+\sqrt{5}}{2}$ and $\displaystyle b=\frac{1-\sqrt{5}}{2}$, prove that $\displaystyle f_n=\frac{a^n-b^n}{\sqrt{5}}$ for all $n\in\mathbb{P}$

Would we start with a base case for proof of induction?

In that case, $n=0$ would be the base case

so how would you prove for $n$ and $n+1$?

Answer 1

Assume that $$ f_0 = 0\\ f_1 = 1\\ f_{n+1} = f_n + f_{n-1} $$ Check the relation for $n=0,1$ (easy).

The general solution of such an equation has the form $$ f_n = Ar_1^n + Br_2^n $$ with $r_{1,2}$ solutions of the characteristic equation: $$ r^2 = r + 1 $$ Check that $$r_{1,2} = \frac{1\pm\sqrt{5}}2$$ and then you are done: as your given candidate gives the good values for $n=0,1$ this is the only solution.

Alternative: prove that if $$ f_n = \frac{a^n + b^n}{\sqrt{5}}\\ f_{n+1} = \frac{a^{n+1} + b^{n+1}}{\sqrt{5}} $$then $$f_{n+2} = \frac{a^{n+2} + b^{n+2}}{\sqrt{5}} $$

Answer 2

Hint $\ $ Note $\,a^n\,$ is a solution of the fibonacci recurrence since

$$\ a^{n+2}-a^{n+1}-a^n = a^n(a^2-a-1) = a^n(0) = 0$$

Similarly $\,b^n\,$ satisfies the recurrence since it too is a root of $\,x^2-x-1.$ Hence by linearity any linear combination $\,c a^n + d b^n\,$ also satisfies the recurrence for any $\,c,d\,$ that are constants (i.e. independent of $\,n).$ In particular $\,g_n = (a^n-b^n)/\sqrt{5}\,$ satisfies the recurrence. Thus $\,f_n,\,g_n\,$ are both solutions of the recurrence and, as easily checked, they have the same initial conditions $\,f_0=0,\,f_1 =1.\ $ Now a simple induction proves that any two such solutions are equal (the uniqueness theorem). Equivalently, considering $\,f_n-g_n,\,$ it suffices to show that $\,0\,$ is the only solution with initial conditions both $= 0,\,$ an obvious induction.

Answer 3

Hint: You have that $$a = \frac{1 + \sqrt{5}}{2}$$ and that $$b = \frac{1 - \sqrt{5}}{2}$$

Show that $a^2 = a + 1$ and $b^2 = b + 1$. Then use strong induction.

Base case: $n = 1$

I leave it to you to show that the equality holds true.

Inductive step: Suppose that $n > 1$ and that $n = 2, 3, .., n$ is true, show that $n+1$ is true.

So $$F_{n+1} = \frac{a^{n+1} + b^{n+1}}{\sqrt{5}}$$

$$F_{n+1} = \frac{(a^{n-1})(a^2) - (b^{n-1})(b^2)}{\sqrt{5}}$$

Try it from there.