Source - Zonal Informatics Olympiad 2006 Question Paper
Have tried deriving the answer through solutions to smaller problems, but of no avail.
Source - Zonal Informatics Olympiad 2006 Question Paper
Have tried deriving the answer through solutions to smaller problems, but of no avail.
Now incorporating EuYu's comment:
If $f(n)$ is the number of ways of tiling a $2 \times n$ rectangle then $f(n)=f(n-1)+f(n-2)+2\sum_{j\lt n-2}f(j)$ starting at $f(0)=1$, since the right hand end can be a vertical double tile, two horizontal double tiles, or in two orientations an L on the end with repeating horizontal doubles eventually capped by another L.
You can now answer the particular questions by hand, or by noting this is also $f(n)=2f(n-1)+f(n-3)$ starting at $f(0)=f(1)=1$, with the generating function $1/(1-2x-x^3),$ or just look up OEIS A052980 .