Number of ways to fill 3xN tiles with 2 x 1 dominoes (SPOJ: M3TILE)

I've been trying to solve this programming problem, but since I can't figure it out, I found a solution online. but I can't really understand why that solution works either ..

the task is to calculate in how many ways can a 3*n (n >= 0, n is the only input) rectangle be completely filled with 2*1 dominos.

e.g. (red lines represent dominos):

This was what I first drew on a sheet of paper when I read the text, and I saw that there were three possible combinations that a 3*2 rectangle can have, and that if n is odd the solution is 0 because there is no way to fill up the entire rectangle then (one piece will always stay uncovered by a domino).

So I thought the solution was simply 3^n, if n was even, and 0, if n was odd. turns out, I was wrong.

I found a relatively simple solution here:

#include <iostream>

using namespace std;

int main()
{
    int arr[31];

    arr[0]=1;
    arr[1]=0;
    arr[2]=3;
    arr[3]=0;

    for(int i = 4; i < 31; i++) {
        arr[i] = arr[i-2] * 4 - arr[i-4]; //this is the only line i don't get
    }

    int n;

    while(1) {
        cin >> n;

        if(n == -1) {
            break;
        }

        cout << arr[n] << endl;
    }

    return 0;
}

Why does this work?!