I am working on a problem presented in Levitin and Levitin's book on algorithmic puzzles.
Problem: The algorithm starts with a single square and on each of its next iterations adds new squares all around the outside. How many unit squares will there be after the nth iteration?
My problem: I understand that after n iterations, the longest horizontal row will contain $(2n - 1)$ squares. The rows above and below it will contain an odd number of squares from $1$ to $(2n - 3)$. How can I use these facts and the fact that the sum of the first $n - 1$ odd numbers is equal to $(n - 1)^2$ to find the total number of squares? In other words, how can I combine these facts into a solution?
Separate the diamond into a top half and a bottom half, and choose arbitrarily that the top half contains the middle row.
Then the number of squares in the top is the sum of the first $n$ odd integers, and the number of squares in the bottom is the first $n-1$ odd integers. Add and simplify.