Find a formula for the nth Fibonacci Number So I'm being asked to find a formula for the nth fibonacci number.  
I know the answer is $$x_{n}=\frac{(1+5^{1/2})^{n} -(1-5^{1/2})^n}{\sqrt{5}2^n}$$  However I don't really know how to get there.  It seems so complicated and I need some help.  
 A: The Fibonacci numbers are defined by the recurrence $F_{n+2}=F_{n+1}+F_n$, with $F_0=F_1=1$.
Computing the first terms, you find
$$1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144\cdots$$
The sequence seems to grow quickly, in an exponential way. To confirm that, let us take the ratios of successive numbers:
$$1, 2, 1.5, 1.666\cdots, 1.6, 1.625, 1.615\cdots, 1.619\cdots$$
This seems to confirm the exponential hypothesis, at least to a first approximation. Let us look closer and try a solution of the form $F_n=ar^n$:
$$F_{n+2}=ar^{n+2}=F_{n+1}+F_n=ar^{n+1}+ar^n.$$
After simplification, we get $r^2=r+1$, and $a$ is inderterminate.
The quadratic equation has two solutions, namely $r=\dfrac{1\pm\sqrt 5}2=r_0,r_1$.
On this moment, we can conclude that $a_0r_0^n$ and $a_1r_1^n$ are two possible solutions of the recurrence. But none can satisfy the initial conditions, $F_0=a_ir_i^0=a_i=1,F_1=a_ir_i^1=a_ir_i=1$, as this would imply $r_i=1$.
A little of thinking (or the understanding of what a linear equation is) will let you try to combine the two solutions by adding them, and attempt
$$F_n=a_0r_0^n+a_1r_1^n.$$
Then the initial conditions say
$$F_0=a_0r_0^0+a_1r_1^0=a_0+a_1=1\\F_1=a_0r_0^1+a_1r_1^1=a_0r_0+a_1r_1=1,$$
which you should be able to solve easily for $a_0$ and $a_1$.
Hence, with these constants,
$$F_n=a_0r_0^n+a_1r_1^n$$
is true for all $n$.
A: This can be solved using generating functions: We have $$F_{n+1} = F_n+F_{n-1}\space \space \space \space \space (F_0 = 0,F_1 = 1) \space\space\space\space\space\space(1).$$ Now define the function $F(x) = \sum_{n\geq0}F_nx^n$ Summing the left and right sides of (1) over the whole numbers, we have $\displaystyle{\frac{F(x)-x}{x} = F(x) + xF(x)}$. Solving for $F(x)$ yields $F(x) = \frac{x}{1-x-x^2}$, which can then be expanded into a series to find an explicit formula for $F_n$.
