How to pave a $n\times 1$ pavement My Problem
We have an unlimited amount of floor tiles - red $1\times 1$, blue $2\times 1$ and green $2\times 1$. How many ways can we pave a pavement $n\times 1$?
Solution
Firstly, I want to find the recurent formula. So I have calculated first ten elements of the series (first five I have done on paper, then it got harder so I have written myself a program that calculates it - hopefully, I haven't made any mistake). I will write just 6 terms to ilustrate
$$a_1=1\quad a_2=3\quad a_3=5\quad a_4=11\quad a_5=21\quad a_6=43$$
From these terms I came to conclusion that the recurent formula is 
$$a_{n+1}=2a_n+(-1)^{n+1}$$
But I don't know how to find the explicit (non recurent) formula from the recurent one. Any suggestions? 
 A: We obtain a recurrence for the $a_i$. A tiling of the $(n+1)\times 1$ pavement is obtained by adding a red on the right to a tiling of the $n\times 1$, or by adding a blue or a green on the right to a tiling of the $(n-1)\times 1$.
It follows that
$$a_{n+1}=a_n+2a_{n-1}.$$
Now solve this linear homogeneous recurrence with constant coefficients in one of the usual ways. I would note that the characteristic polynomial is $x^2-x-2$, with roots $2$ and $-1$, so the general solution of the recurrence has the shape $A\cdot 2^n+B\cdot (-1)^n$. We can find $A$ and $B$ by using the known values of $a_n$ at $n=1$ and $n=2$.
A: If a red tile is represented by the string $1$, a blue tile by the string $21$, and a green tile by the string $22$, then an $n\times1$ pavement is represented by a string of $1$s and $2$s of length $n$.  Any such string also represents a pavement, provided it satisfies one condition: that it not end in an odd number of $2$s.
Your recurrence follows:  let $a_n$ be the number of strings not ending in an odd number of $2$s.  One can create $2a_n$ strings of length $n+1$ by inserting either a $1$ or a $2$ in front of each of the $a_n$ length $n$ strings.  One circumstance requires special handling: if $n$ is odd, the string of $n$ $2$s is not among the strings enumerated by $a_n$.  As a result the legal string of $n+1$ $2$s won't be generated by the procedure above and must be added by hand.  Hence $a_{n+1}=2a_n+1$.  If $n$ is even, the string of $n$ $2$s is among the strings enumerated by $a_n$.  Inserting a $2$ in front of this string results in an illegal string, which must be removed by hand.  Hence $a_{n+1}=2a_n-1$.
A closed form also follows from this picture: if $n$ is even, legal strings are the string of $n$ $2$s or an arbitrary string of length $n-2k-1$ followed by a $1$ followed by $2k$ $2$s, with $k\in\{0,1,\ldots,n/2-1\}$.  There are
$$
1+\sum_{k=0}^{n/2-1}2^{n-2k-1}=1+2^{n-1}\frac{(1/4)^{n/2}-1}{1/4-1}=1+2^{n+1}\frac{1-(1/4)^{n/2}}{3}=\frac{2^{n+1}+1}{3}
$$
such strings.  If $n$ is odd, legal strings are arbitrary string of length $n-2k-1$ followed by a $1$ followed by $2k$ $2$s, with $k\in\{0,1,\ldots,(n-1)/2\}$.  There are
$$
\sum_{k=0}^{(n-1)/2}2^{n-2k-1}=2^{n-1}\frac{(1/4)^{(n+1)/2}-1}{1/4-1}=2^{n+1}\frac{1-(1/4)^{(n+1)/2}}{3}=\frac{2^{n+1}-1}{3}
$$
such strings.  Hence $a_n=\frac{1}{3}(2^{n+1}-(-1)^{n+1})$.
Probably the recurrence and characteristic equation method in André Nicolas's answer are more straightforward, especially if you have used similar techniques on other problems.  But the fact that the roots of the characteristic equation are integers suggests that they have combinatorial meaning. Hence this answer.
Addendum: It is worth mentioning how one might go about solving your recurrence if one didn't have a combinatorial interpretation to work with.  This method is actually less cumbersome than directly summing the geometric series that arise in the combinatorial interpretation.  Since yours is a one-term recurrence, it may, in the end, also be more straightforward than solving the two-term recurrence.
First note that any two solutions to your inhomogeneous recurrence differ by a solution to the homogeneous recurrence $a_{n+1}=2a_n$.  The homogeneous recurrence clearly has solutions $k\cdot2^n$.  So if one can find any single solution to the inhomogeneous recurrence, one then need only add $k\cdot2^n$ to it, with $k$ chosen to match your initial condition.
That the inhomogeneous term in your recurrence is $(-1)^{n+1}$ suggests trying the exponential solution $a_n=A(-1)^n$.  Substituting this into the recurrence gives
$$
A(-1)^{n+1}=2A(-1)^n+(-1)^{n+1},
$$
which implies that $3A=1$.  So a solution of the form $a_n=\frac{1}{3}(-1)^n+k\cdot2^n$ will work, and $k$ is easily determined.
