Update: Doug showed me a fast algorithm that does the trick. It doesn't use recursion. For an nxn board, the algorithm counts the possibilities given a knight in each of these regions:

1.    The central (n-4)x(n-4) sub-board

2.    The squares bordering this central sub-board but excluding the four "corners" where the row and column squares intersect

3.    The edge squares adjacent to the ones in #2

4.    The four "corners" excluded in #2 that are one square diagonal from each of the four corners of the nxn board

5.    The eight edge squares adjacent to the four corners of the nxn board

6.    The four corners of the nxn board

Sum these and divide by two (because the two knights are interchangeable) and you can calculate the solution very quickly for any nxn. Mapping this over [1..n] will provide the required output. My takeaway from this is that using the solution to case n-1 in order to solve case n may not be the most efficient way to do things. Sometimes just solving for case n from scratch is faster.

Thanks Doug.

Julian