South Africa National Olympiad 2000 (Tile 4xn rectangle using 2x1 tiles) Let $A_n$ be the number of ways to tile a $4×n$ rectangle using $2×1$ tiles. Prove that $A_n$ is divisible by 2 if and only if $A_n$ is divisible by 3.
My attempt: Define basic shapes A, B and C, where the shaded areas are occupied by ties. 
Going recursively, let $A(m)$, $B(m)$, $C(m)$ indicate number of ways to fill in rest of un-shaded area of A, B, C at position $m$ (for example, $A(0)$ means number of ways to fill in a blank $4×n$ rectangle).
Obviously $A(0) = A(2) + B(0) + B(1) + C(1)$, $B(0) = A(1) + A(2) + B(2)$, $C(1) = A(2) + C(3)$, $B(1)= A(2) + A(3) + B(3)...$, but, how do I prove $A(m) \equiv 0, 1, 5 (mod\space6)$?

 A: This is a very typical olympiad style problem. They can all typically be solved with the same machinery.
First, I'd recommend slightly redefining your series $A$, $B$, and $C$, as they are "reversed". Let $A'(n) = A_n$. Let $B'(n)$ be the number of ways of tiling a $4 \times n$ rectangle if the rightmost column contains exactly one vertical domino, which touches the upper right corner. Let $C'(n)$ be the number of ways of tiling a $4 \times n$ rectangle if the rightmost column contains exactly one vertical domino, which touches neither the upper right corner nor the lower right corner. 
You can derive a simple linear recurrence expressing $A'(n)$ in terms of lower-valued terms, similarly to how you got your "obvious" initial conditions. You can similarly derive recurrences for $B'(n)$ and $C'(n)$.
Using some basic "recurrence" algebra, you can eliminate all $B'$ and $C'$ terms to get a single linear recurrence with only $A'$ terms. Since the recurrence is linear, it must be periodic modulo 6. You simply need to compute the first few mod 6 values until it begins repeating and then your proof will be complete.
