How many rectangles can be found in this shape? 
Question: How many rectangles can be found in the following shape?


My first solution:
Let $a_n$ be the number of rectangles in such a shape with side length $n$. Then, the number of the newly added $1 \times k$ rectangles while expanding the shape with side length $n-1$ to the shape with side length $n$ is, $n^2$. Similarly, the number of the newly added $2 \times k$ rectangles while expanding is, $(n-2)^2$, the number of the $3 \times k$ ones is $(n-4)^2$, and so on. So, we have, $$a_n = a_{n-1} + 1^2+3^2+\ldots +n^2$$ or, $$a_n = a_{n-1} + 2^2+4^2+\ldots +n^2$$ depending on the parity of $n$. In either case, we have $$a_n=a_{n-2}+1^2+2^2+ \ldots n^2$$ So, $a_{n+1} = a_{n-1} + 1^2+2^2+ \ldots (n+1)^2$. Subtracting both sides, we have, $a_{n+1}-a_n = a_{n-1} - a_{n-2} + (n+1)^2$. Repeating the same method, we obtain $$a_{n+1}-4a_n+5a_{n-1} = 5a_{n-3} - 4a_{n-4}+a_{n-5}$$ This recurrence relation has characteristic equation $r^6-4r^5+5r^4-5r^2+4r-1=0 \iff (r-1)^5 \cdot (r+1) = 0$. So, using the usual ways to solve recurrence relations, we can obtain $a_n=\frac{n^4}{24} + \frac{n^3}{4} + \frac{11n^2}{24} + \frac{n}{4} = \binom{n+3}{4}$.
However, since the answer is so simple, I tried to solve it with a method which can give the result in a more 'direct' way:
Let us find these rectangles by choosing 2 rows and 2 columns and looking at their intersection. If we choose the right most column, we have $n$ choices for the other column and only $1$ choice for the rows. If we choose column which is the second from right, we have $n-1$ choices for the other column (in order not to over count), and, $\binom{2+2-1}{2}$ (number of ways to choose 2 rows out of 2 rows including repetitions) choices for the row. Using this argument, we can obtain, $$a_n = \sum_{k=0}^{n-1} (n-k) \cdot \binom{(k+1)+2-1}{2} = \sum_{k=0}^{n-1} (n-k) \cdot \binom{k+2}{2}=\sum_{k=0}^{n-1} \frac{(n-k) \cdot (k+2) \cdot (k+1)}{2}$$ After some computation, we can see from here that $a_n=\binom{n+3}{4}$.
However, I think this solution is also overcomplicated and I think that there is a really elegant and/or 'direct' solution for this problem. So, my question is, how can this problem be solved with a 'direct' method (for example, a combinatorial method which immediately gives the number as $\binom{n+3}{4}$)? It would be nice to see your 'nice' solutions too, thank you.

Searching ${n+3 \choose 2}$ at OEIS you can find in A000332 the reference to A004320 and there the document Counting the lattice rectangles inside Aztec diamonds and square biscuits by Teofil Bogdan and Mircea Dan Rus and the solution to problem 3, on page 3. Basically, for each rectangle you have to choose four coordinates for the vertices $(x_1,y_1), (x_1,y_2), (x_2,y_1), (x_2,y_2)$ with $x_1 \lt x_2 \lt y_1 \lt y_2$ among $n+3$ values.
