Homework for 9/26/02

My solution is probably not be the best - and in fact I have a feeling I'm overlooking something obvious that would provide a huge shortcut.

First, I found a way to count the number of matchings. Where n is the number of columns in the grid, this turns out to be:
1) a(n) = 2a(n-1) + 3a(n-2) + 2(sum_{i=3}^{n-1} a(n-i))
Next, I used induction. Assume:
2) a(n) = 3a(n-1) + a(n-2) - a(n-3)
We know:
a(n+1) = 2a(n) + 3a(n-1) + 2(sum_{i=2}^{n-1} a(n-i))
= 6a(n-1) + 2a(n-2) - 2a(n-3) + 3a(n-1) + 2(sum_{i=2}^{n-1} a(n-i))
= 9a(n-1) + 4a(n-2) - 2a(n-3) + 2(sum_{i=3}^{n-1} a(n-i))
= 9a(n-1) + 3a(n-2) - 3a(n-3) + 2(sum_{i=3}^{n-1} a(n-i)) + a(n-2) + a(n-3)
= 3(3a(n-1) + a(n-2) - a(n-3)) + 2(sum_{i=3}^{n-1} a(n-i)) + a(n-2) + a(n-3)
= 3a(n) + 2(sum_{i=3}^{n-1} a(n-i)) + a(n-2) + a(n-3)
From 2), we can also assume: a(n-3) = a(n-2) + 3a(n-1) - a(n)
Therefore: a(n+1) = 3a(n) + a(n-2) + [a(n-2) + 3a(n-1) - a(n)] + 2(sum_{i=3}^{n-1} a(n-i))
= 3a(n) + 2a(n-2) + 3a(n-1) - a(n) + 2(sum_{i=3}^{n-1} a(n-i))
= 3a(n) + 2a(n-1) + 3a(n-2) - a(n) + 2(sum_{i=3}^{n-1} a(n-i)) - a(n) - a(n-2) + a(n-1)
= 3a(n) + a(n) - a(n) - a(n-2) + a(n-1)
= 3a(n) + a(n-1) - a(n-2)
Which is what we were trying to prove. Since we know the first three values of a(n), and 2) checks out for n = 3, I think I have proved 2) for n >= 3.

Thanks to... er.. I think Inna for showing me this much faster way: