Why is Euler's Formula for Planar Graph Not Working Here? 
I have worked out $r(n) = 2^n$, $e(n) = 1 + 3 \times 2^n$, $v(n) = 2\times(2^n - 1) + 4$
The expressions of $r(n)$, $e(n)$, and $v(n)$ are correct and this can be verified with $n = 0, 1, 2, 3\ldots$ 
But when I calculate $v(n) - e(n) + r(n)$, it does not equal to $2$. What's wrong?
Also, can we derive the relationship between v(n) and e(n) using the sum of degree of vertices?

It looks like you are confused about what is the "outter" region. At step $0$, when you have only one rectangle, there are two faces :

The green one is the "inside", the blue one (that extend indefinitively on the plane) is the "outside". Hence 


*

*If you just want to count the number of rectangles, then indeed $r(n)=2^n$.

*But if you want to count the number of faces in graph term, then you must include the outter face, and your formula should be $f(n)=r(n)+1=2^n+1$, verifying $v(n)-e(n)+f(n)=2$, or $v(n)-e(n)+r(n)=1$
