Number of ways to select non-adjacent squares from a rectangular grid? I know that the number of selections of $k$ non-adjacent objects from $n$ objects (in a line) is ${n-k+1 \choose k}$, and for all possible values of $k$ including 0, it's $F_n$, the $n^{th}$ Fibonacci number.
However, when I tried expanding to the second dimension, the problem seems to become far more complicated, and I see no way of employing the 1-dimensional solution. How many ways are there to select any number of non-adjacent squares in a grid (including the empty selection)?
 A: You want to know the number of independent sets in a "grid graph".  This is counted at the OEIS for square grids, and it has been shown by Calkin and Wilf that if $F_{m,n}$ is the number of independent sets of an $m \times n$ grid graph, then $\lim_{m \to \infty, n \to \infty} F_{m, n}^{1/mn}$ exists and is about 1.503.   Reinhardt Euler gives some explicit formulas in the case of small $m$ and arbitrary $n$.  There are probably other sources.
Showing this limit (as done in the Calkin-Wilf paper) is hard , so let's see if we can come up with something a bit simpler.  It's easy to show that if this limit exists, it must be somewhere between $\sqrt{2}$ and $\phi = (1 + \sqrt{5})/2$.  The number of independent sets on a $m \times n$ grid graph has to be less than the number on a line of length $mn$, which is the $(mn)$th Fibonacci number (as you know) -- this gives the upper bound.  But on the other hand we can take any subset consisting of only black squares, of which there are $mn/2$ (unless $m$ and $n$ are both odd, but this is still basically right even then) which gives the lower bound.
