How many possibilities are there of dividing a 2xn rectangle to smaller 2x1 rectangles? (if we lay the big rectangle horizontally) I observed that either the small rectangle must be vertical, or a pair of two 2x1 horizontal rectangles on top of each other (in a 2x2 square) like a sandwich. any other formation will not have a "flat" end.
So if all the 2x1 rectangles are vertical, that's 1 way.
Then I can choose 2 adjacent (vertical) rectangles and "rotate" them to form the sandwich shape. this adds n-1 possibilities.
I can choose 2 pairs of adjacent rectangles to from 2 sandwiches and this adds, I believe, n(n+1)/2 possibilities.
But how do I keep going?
To obtain a configuration for a $2\times n$ rectangle, you can either append a vertical tile to a $2\times(n-1)$ rectangle, or two horizontal tiles to a $2\times(n-2)$ rectangle. Thus the count $a_n$ of such configurations satisfies the recurrence relation $a_n=a_{n-1}+a_{n-2}$. Also, clearly $a_0=1$ and $a_1=1$. You might recognize this recurrence relation and these initial conditions from the Fibonacci numbers.