Dynamic Programming, Counting Independent Sets
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]$.