title: Given an integer N, in how many ways can we tile a 4 x N rectangle with 3 x 1 tiles?
body: <p>I know tiling problems are not uncommon and they are usually solved with Dynamic programming. I've also read quite similar question <a href="http://www.algorithmist.com/index.php/UVa_10918" rel="nofollow">here</a> about tiling 3XN rectangle with 2X1 tiles but I still have problem figuring out the recurrent relations.</p>
  
  <p>Right now I know you can title 4X3 rectangle with 3X1 titles in 3 ways. So there's a relation here like f(n) = 3*f(n-3) + [other]. I've been scratching my head for a while now to figure what the 'other' part should be. Some help would be greatly appreciated.</p>