Find a recurrence relation for the number of different square subboards of any size that can be drawn on an $n\times n$ chessboard.
I worked this out up to $n= 4$. For $n=1$, there's $1$, $n=2$ gives $5$, $n=3$ gives $14$, and $n=4$ gives $30$. However, I don't see how the recurrence relation. Any ideas?
Count the subsquares by their sizes. For $n=1$ you get $1$; for $n=2$ you get $4+1$; for $n=3$ you get $9+4+1$; and for $n=4$ you get $16+9+4+1$. Doesn’t that suggest a recurrence? Or did you see that already but not see how to justify it?
Added: To get the recurrence $a_n=a_{n-1}+2\binom{n}2+n$, divide your $n\times n$ board into the upper left $(n-1)\times(n-1)$ board, $B$, the righthand column, $C$, and the bottom row, $R$, which has a one-cell overlap with $C$. Every subsquare either lies entirely in $B$ or intersects one or both of $C$ and $R$. There are $a_{n-1}$ subsquares lying wholly in $B$.
To count the rest, note that each cell of the large board is the upper lefthand corner of exactly one subsquare that intersects at least one of $C$ and $R$. Let $i$ and $k$ be distinct elements of $\{1,\dots,n\}$. They pick out two cells of the board, the one in row $i$ and column $k$, and the one in row $k$ and column $i$, and hence the corresponding subsquares intersecting $C$ and $R$. (There is exactly one of each.) There are $\binom{n}2$ pairs of distinct integers in $\{1,\dots,n\}$, so we’ve accounted for another $2\binom{n}2$ subsquares. The only subsquares not yet counted are those whose upperlefthand corners are on the main diagonal, i.e., in row $i$ and column $i$ for some $i\in\{1,\dots,n\}$, and there are $n$ of those. Thus,
$$a_n=a_{n-1}+2\binom{n}2+n\;.$$
To get the closed form, use the identity
$$\sum_{m=k}^n\binom{m}k=\binom{n+1}{k+1}$$
with $k=1$ and $k=2$.