How many ways can dominoes cover a $2 \times n$ rectangle? Justify proposed solution. I was able to get that $d_n = d_{n-1}+d_{n-2}$
It isn't finished, because I have to solve this recursive equation. 
I read about Binet's formula, but I don't know the steps between this
$$d_n = d_{n-1}+d_{n-2}$$
and this
$$f_n=\frac{1}{\sqrt{5}} \left[\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right]$$
Which is exactly what I'm looking for - function with $n$ as parameter.
 A: Your recurrence relation is correct.  The sequence either begins with one vertical tile followed by one of $d_{n - 1}$ admissible sequences of length $n - 1$ or two horizontal tiles followed by one of the $d_{n - 2}$ admissible sequences of length $n - 2$.  Hence, 
$$d_n = d_{n - 1} + d_{n - 2}$$
The recursion $d_n = d_{n - 1} + d_{n - 2}$ has characteristic equation $r^2 = r + 1$.  
\begin{align*}
r^2 & = r + 1\\
r^2 - r & = 1\\
r^2 - r + \frac{1}{4} & = 1 + \frac{1}{4}\\
\left(r - \frac{1}{2}\right)^2 & = \frac{5}{4}\\
r - \frac{1}{2} & = \pm \frac{\sqrt{5}}{2}\\
r & = \frac{1 \pm \sqrt{5}}{2}
\end{align*}
so 
$$d_n = A\left(\frac{1 + \sqrt{5}}{2}\right)^n + B\left(\frac{1 - \sqrt{5}}{2}\right)^n$$
where $A$ and $B$ are constants, which can be determined from the initial conditions $d_1 = 1$ (one vertical tile), $d_2 = 2$ (both tiles are horizontal or both are vertical).  Hence, $d_n = F_{n + 1}$, where $F_n$ is the $n$th Fibonacci number.  
Since Binet's formula gives an explicit formula for $F_n$, the $n$th Fibonacci number, 
$$F_n = \frac{1}{\sqrt{5}}\left[\left(\frac{1 + \sqrt{5}}{2}\right)^n - \left(\frac{1 - \sqrt{5}}{2}\right)^n\right]$$
the formula for $d_n$ can be found using that formula and the observation that $d_n = F_{n + 1}$.
