So i was given this question just to try for practice to test our knowledge and i'm really confused on how to go about this question. How should i go about this question, i'm confused with the greek notation and also on how to approach it.
In this question, we will define a sequence of numbers $$L_n$$ for $$n \geq 1$$, and prove something about it. The differences from what you may have seen so far are: * It has two base cases, * And the definition of $$L_{n+1}$$ involves both $$L_n$$ and $$L_{n-1}$$. * You will still do "induction", but you need to check //two// base cases! ** Let $$L_1 = 1, L_2 = 3$$. ** And with $$n \geq 2$$, define $$L_{n+1} = L_n + L_{n-1}$$. ** Prove that $$L_n = \varphi^n + \Phi^n$$, where $$\varphi = \frac{1 + \sqrt{5}}{2}$$ and $$\Phi = \frac{1 - \sqrt{5}}{2}$$. * //Note: The quantity $$\varphi$$ is referred to as the "golden ratio", and the quantity $$\Phi$$ is related to it. The Greek letters $$\varphi$$ and $$\Phi$$ are both called "phi", but the first is lower-case and the second is upper-case.// * //Hint: In order to do this question, you should check that $$\varphi$$ and $$\Phi$$ are the two roots of the equation $$x^2 = x+1$$. This may help in the inductive step...//
Hint
So $L_n = \phi^n + \Phi^n$ and $L_{n-1} = \phi^{n-1} + \Phi^{n-1}$, and we have $$ L_{n+1} = L_n + L_{n-1} = \phi^n + \Phi^n + \phi^{n-1} + \Phi^{n-1} = \phi^{n-1} (\phi+1) + \Phi^{n-1} (\Phi+1) $$ and now use the fact that $\phi$ and $\Phi$ solve $x^2 = x+1$, so $\phi+1=\phi^2$ and $\Phi+1 = \Phi^2$.
Can you finish the proof?