Dynamic Programming, Counting Independent Sets My first thought is to make OPT(i, j), where i is n, and j is some condition on the column. But 
my experience with DP is from knapsack and weighted interval scheduling, but I'm unsure of how to approach this. Any ideas would be great.
Let $OPT_N[i]$ be the number of independent sets in the graph with $2i$ vertices with the additional constraint that neither of the leftmost two vertices can be selected into an independent set.

Let $OPT_T[i]$ be the number of independent sets in the graph with $2i$ vertices with the additional constraint that the top of the leftmost two vertices must be selected in the independent set.

Let $OPT_B[i]$ be the number of independent sets in the graph with $2i$ vertices with the additional constraint that the bottom-most of the leftmost two vertices must be selected in the independent set.

According to the above definitions $OPT_N[1] = OPT_T[1] = OPT_B[1] = 1$ while, for $i&gt;1$:
$$
\begin{align*}
OPT_N[i] &amp;= OPT_N[i-1] + OPT_T[i-1] + OPT_B[i-1]\\
OPT_T[i] &amp;= OPT_N[i-1] + OPT_B[i-1]\\
OPT_B[i] &amp;= OPT_N[i-1] + OPT_T[i-1]
\end{align*}
$$

The number of independent sets on a graph with $2i$ vertices is then $OPT_N[n] + OPT_T[n] + OPT_B[n] = OPT_N[n+1]$.

You can simplify the above formulas by noticing that you must have $ OPT_T[i] = OPT_B[i]$.