Counting Squares Challenge: Proving Formula and Evaluating Sum

[lfdahl]

We have an $n \times n$ square grid of dots ($n \ge 2$).

Let $s_n$ denote the number of squares that can be constructed from the grid points.

(a). Show, that $$s_n = \frac{n^4-n^2}{12}.$$

Note, that squares with "diagonal sides" also count.

(b). Evaluate the sum:

\[S = \sum_{k = 2}^{\infty }\frac{1}{s_k}\]

 

[Opalg]

We have an $n \times n$ square grid of dots ($n \ge 2$).

Let $s_n$ denote the number of squares that can be constructed from the grid points.

(a). Show, that $$s_n = \frac{n^4-n^2}{12}.$$

Note, that squares with "diagonal sides" also count.

(b). Evaluate the sum:

\[S = \sum_{k = 2}^{\infty }\frac{1}{s_k}\]

(a)
[sp]Proving the formula for $s_n$ by induction, the base case $s_2 = 1$ is easy to check.

For the inductive step, label the rows and columns from $1$ to $n$. Then $s_{n-1}$ is the number of squares whose vertices are all in the first $n-1$ rows and columns of the $n\times n$ grid. Let $u_n$ be the number of squares with at least one vertex in column $n$, and let $v_n$ be the number of squares with no vertices in column $n$ but at least one vertex in row $n$. Then $s_n = s_{n-1} + u_n + v_n.$

[TIKZ][scale=0.5]
\foreach \x in {1,...,8}
\foreach \y in {1,...,8}
{
\fill [gray] (\x,\y) circle (2pt) ;
\draw (\x,0) node{$\x$} ;
\draw (0,\y) node{$\y$} ;
}
\draw[thin,gray,dashed] (1,7.5) -- (7.5,7.5) ;
\draw[thin,gray,dashed] (7.5,1) -- (7.5,8.2) ;
\foreach \x in {3,...,7}
\foreach \y in {1,...,3}
\fill [red] (\x,\y) circle (3pt) ;
\draw[thin,red] (8,3) -- (3,1) -- (1,6) -- (6,8) -- cycle ;
\draw[thin,red] (8,3) -- (5,3) -- (5,6) -- (8,6) -- cycle ;
\fill [blue] (8,3) circle (3pt) ;
[/TIKZ]
To calculate $u_n$, notice that the number of squares whose lowest vertex in column $n$ is at the point $(n,k)$ is $k(n-k)$. [In the above diagram, $n=8$, $k=3$, so $(n,k)$ is the blue dot. The possible locations for the lowest of the remaining three vertices are the red dots. Two of the resulting squares are shown in red. There are $k(n-k) = 3\times5$ red squares in this case. They are the dots in rows $1$ to $k$ and columns $k$ to $n-1$.]

Therefore \(\displaystyle u_n = \sum_{k=1}^{n-1}k(n-k) = \tfrac12n^2(n-1) - \tfrac16(n-1)n(2n-1) = \tfrac16n(n-1)(n+1).\)

The next step is to find $v_n$. Every square that counts towards $v_n$ must lie in the $(n-1)\times(n-1)$ grid consisting of rows $2$ to $n$ and columns $1$ to $n-1$ of the $n\times n$ grid. We are looking for the number of squares with at least one vertex in the top row of this $(n-1)\times(n-1)$ grid. The calculation for that is exactly the same as that for $u_{n-1}$. Therefore $v_n = u_{n-1} = \frac16(n-1)(n-2)n$.

Now for the actual inductive step. Assume that $s_{n-1} = \tfrac1{12}\bigl((n-1)^4 - (n-1)^2\bigr) = \tfrac1{12}(n-1)^2n(n-2).$ Then $$\begin{aligned}s_n &= s_{n-1} + u_n + v_n \\ &= \tfrac1{12}n(n-1)^2(n-2) + \tfrac16n(n-1)(n+1) + \tfrac 16n(n-1)(n-2) \\ &= \tfrac1{12}n(n-1)\bigl((n-1)(n-2) + 2(n+1) + 2(n-2)\bigr) \\ &= \tfrac1{12}n(n-1)(n^2+n) \\ &= \tfrac1{12}n^2(n-1)(n+1) = \tfrac1{12}(n^4 - n^2), \end{aligned}$$ as required. That completes the inductive proof.[/sp]

(b)
[sp]\(\displaystyle \frac{1}{s_k} = \frac{12}{k^2(k-1)(k+1)} = -\frac{12}{k^2} + \frac6{k-1} - \frac6{k+1},\) using partial fractions. Therefore $$S = \sum_{k = 2}^{\infty }\frac{1}{s_k}= -\sum_{k=2}^\infty \frac{12}{k^2} + \sum_{k=2}^\infty\Bigl(\frac6{k-1} - \frac6{k+1}\Bigr).$$ For the first of those sums, use the famous result \(\displaystyle \sum_{k=1}^\infty \frac1{k^2} = \frac{\pi^2}6,\) so that \(\displaystyle \sum_{k=2}^\infty \frac{12}{k^2} = 2\pi^2 - 12\). The second sum is a telescoping series in which only the early terms $6+3$ survive cancellation. So $S = - (2\pi^2 - 12) + 9 = 21 - 2\pi^2.$

[/sp]

 

[lfdahl]

(a)
[sp]Proving the formula for $s_n$ by induction, the base case $s_2 = 1$ is easy to check.

For the inductive step, label the rows and columns from $1$ to $n$. Then $s_{n-1}$ is the number of squares whose vertices are all in the first $n-1$ rows and columns of the $n\times n$ grid. Let $u_n$ be the number of squares with at least one vertex in column $n$, and let $v_n$ be the number of squares with no vertices in column $n$ but at least one vertex in row $n$. Then $s_n = s_{n-1} + u_n + v_n.$

[TIKZ][scale=0.5]
\foreach \x in {1,...,8}
\foreach \y in {1,...,8}
{
\fill [gray] (\x,\y) circle (2pt) ;
\draw (\x,0) node{$\x$} ;
\draw (0,\y) node{$\y$} ;
}
\draw[thin,gray,dashed] (1,7.5) -- (7.5,7.5) ;
\draw[thin,gray,dashed] (7.5,1) -- (7.5,8.2) ;
\foreach \x in {3,...,7}
\foreach \y in {1,...,3}
\fill [red] (\x,\y) circle (3pt) ;
\draw[thin,red] (8,3) -- (3,1) -- (1,6) -- (6,8) -- cycle ;
\draw[thin,red] (8,3) -- (5,3) -- (5,6) -- (8,6) -- cycle ;
\fill [blue] (8,3) circle (3pt) ;
[/TIKZ]
To calculate $u_n$, notice that the number of squares whose lowest vertex in column $n$ is at the point $(n,k)$ is $k(n-k)$. [In the above diagram, $n=8$, $k=3$, so $(n,k)$ is the blue dot. The possible locations for the lowest of the remaining three vertices are the red dots. Two of the resulting squares are shown in red. There are $k(n-k) = 3\times5$ red squares in this case. They are the dots in rows $1$ to $k$ and columns $k$ to $n-1$.]

Therefore \(\displaystyle u_n = \sum_{k=1}^{n-1}k(n-k) = \tfrac12n^2(n-1) - \tfrac16(n-1)n(2n-1) = \tfrac16n(n-1)(n+1).\)

The next step is to find $v_n$. Every square that counts towards $v_n$ must lie in the $(n-1)\times(n-1)$ grid consisting of rows $2$ to $n$ and columns $1$ to $n-1$ of the $n\times n$ grid. We are looking for the number of squares with at least one vertex in the top row of this $(n-1)\times(n-1)$ grid. The calculation for that is exactly the same as that for $u_{n-1}$. Therefore $v_n = u_{n-1} = \frac16(n-1)(n-2)n$.

Now for the actual inductive step. Assume that $s_{n-1} = \tfrac1{12}\bigl((n-1)^4 - (n-1)^2\bigr) = \tfrac1{12}(n-1)^2n(n-2).$ Then $$\begin{aligned}s_n &= s_{n-1} + u_n + v_n \\ &= \tfrac1{12}n(n-1)^2(n-2) + \tfrac16n(n-1)(n+1) + \tfrac 16n(n-1)(n-2) \\ &= \tfrac1{12}n(n-1)\bigl((n-1)(n-2) + 2(n+1) + 2(n-2)\bigr) \\ &= \tfrac1{12}n(n-1)(n^2+n) \\ &= \tfrac1{12}n^2(n-1)(n+1) = \tfrac1{12}(n^4 - n^2), \end{aligned}$$ as required. That completes the inductive proof.[/sp]

(b)
[sp]\(\displaystyle \frac{1}{s_k} = \frac{12}{k^2(k-1)(k+1)} = -\frac{12}{k^2} + \frac6{k-1} - \frac6{k+1},\) using partial fractions. Therefore $$S = \sum_{k = 2}^{\infty }\frac{1}{s_k}= -\sum_{k=2}^\infty \frac{12}{k^2} + \sum_{k=2}^\infty\Bigl(\frac6{k-1} - \frac6{k+1}\Bigr).$$ For the first of those sums, use the famous result \(\displaystyle \sum_{k=1}^\infty \frac1{k^2} = \frac{\pi^2}6,\) so that \(\displaystyle \sum_{k=2}^\infty \frac{12}{k^2} = 2\pi^2 - 12\). The second sum is a telescoping series in which only the early terms $6+3$ survive cancellation. So $S = - (2\pi^2 - 12) + 9 = 21 - 2\pi^2.$

[/sp]

Thankyou very much, Opalg for an exemplary contribution!(Handshake)