the sequence of Fibonacci numbers is defined as follows: $x_1=1, x_2=1$, and, for $n>2, x_n=x_{n-1} + x_{n-2}$. Prove that
$$ x_n=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right )^n - \left (\frac{1-\sqrt{5}}{2}\right )^n\right ] $$ for every natural number $n$.
You can find a proof here.
But my favorite proof takes a different course. Let $\mathbf x = \{x_n\}_{n \in \Bbb N}$ and $\mathbf y = \{y_n\}_{n \in \Bbb N}$ be sequences satisfying the Fibonicci recurrence relation. That is: for $n > 1, x_n = x_{n-1} + x_{n-2}$ and $y_n = y_{n-1} + y_{n-2}$. Note that for any real number $a$, $a\mathbf x = \{ax_n\}_{n \in \Bbb N}$ and $\mathbf x + \mathbf y = \{x_n + y_n\}_{n \in \Bbb N}$ are also sequences that obey the same recurrence relation. That is, the set of all such sequences forms a vector space. Further, because the value of $x_0$ and $x_1$ completely determines the entire sequence, the vector space has to be two-dimensional. Thus if we can find two independent sequences that satisfy the recurrence relation, every such sequence can be written as a linear combitnation of them.
Consider a sequence of the form $\{r^n\}$ for some $r$. For it to satisfy the recurrence relation, we must have $r^n = r^{n-1} + r^{n-2}$. Assuming that $r \ne 0$, this is equivalent to $r^2 = r + 1$. The quadratic solves to $$r = \frac{1 \pm \sqrt 5}2$$.
Thus every sequence, including the Fibonicci numbers, that satisfies the recurrence relation $x_n = x_{n-1} + x_{n-2}$ can be written in the form $$ x_n = A\left(\frac{ 1 + \sqrt 5}{2}\right)^n+ B\left(\frac{ 1 - \sqrt 5}{2}\right)^n$$ for some $A, B$.
By plugging in $x_0 = 0, x_1 = 1$, you get two equations in $A, B$ which solve to $A = -B = \frac{1}{\sqrt 5}$.
With induction, you are given the formula. So you simply have to show it holds for the base case(s), and then use the formula for n and n+1 to show it holds for n+2. You might want to review induction for easier problems.
Don't feel like you have to come up with that formula for $X_n$ out of nowhere, which is harder than just showing it works.
Initial step: $X_2$ = $X_1$ = 1. Does $x_n=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right )^1 - \left (\frac{1-\sqrt{5}}{2}\right )^1\right ]$ = 1 = $X_2$ = $X_1$ ?
Induction step:
Assume the result is true for $X_{n-1}$ and $X_n$.
Then $X_{n+1} = X_n + X_{n - 1} =\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right )^n - \left (\frac{1-\sqrt{5}}{2}\right )^n\right ] + \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right )^{n-1} - \left (\frac{1-\sqrt{5}}{2}\right )^{n-1}\right ]$
can you show that this is equal to $\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right )^{n+1} - \left (\frac{1-\sqrt{5}}{2}\right )^{n+1}\right ]$ ?
Once you show those. You are done. By induction the result is true for all n.
