LogFAQs > #878382261

organicbamf posted...

(I'm not sure if the above suffices for all seeds, we did more and I'm trying to cut out unneeded stuff, but I think it does)

You only need the first two as initial conditions. And a recursion is definitely the best way to go with this problem.

Let a_n be the number of ways to tile a 2x2n grid. Then by considering the left-most blocks, we get

a_n = a_{n-1} (from square) + a_{n-2} (from two I's) + 2(a_{n-2}+a_{n-3}+...+a_0) (from L and I interpolation and symmetry), with a_0=a_1=1.

This appears to be the square of the Fibonacci number F_{n+1} and letting b_n=(F_{n+1})^2, it's easy work out that b_n satisfies the same recurrence as the a's with the same initial conditions.