Which recurrence describes tiling a 2×n2 \times n2×n board with 1×21 \times 21×2 dominoes?
an=an−1+an−2+1a_n = a_{n-1} + a_{n-2} + 1an=an−1+an−2+1
an=an−1+2an−2a_n = a_{n-1} + 2a_{n-2}an=an−1+2an−2
an=2an−1+an−2a_n = 2a_{n-1} + a_{n-2}an=2an−1+an−2
an=an−1+an−2a_n = a_{n-1} + a_{n-2}an=an−1+an−2