Exercise 4.4.24* (Sum of the first $n$ terms of the sequence $0, 1, 1,2,2,3,3,4,4,\ldots$)

Proof.

Some values of $f(n)$:

By convention, we define $f(0)=0$.

(a)

We note that $u_n=\lfloor n∕2\rfloor$ for all $n$, and $$\begin{array}{lll}\hfill f(n)& =\underset{k=1}{\overset{n}{\sum }}{u}_k=\underset{k=1}{\overset{n}{\sum }}\lfloor \frac{k}{2}\rfloor & \hfill \text{(1)}\end{array}$$

We shaw first that for all $n\in \mathbb{N}$,

$$\begin{array}{lll}\hfill \lfloor \frac{n}{2}\rfloor =\lfloor \frac{n^2}{4}\rfloor -\lfloor \frac{{(n-1)}^2}{4}\rfloor .& & \hfill \text{(2)}\end{array}$$

We write $n=2q+r$, where $r=0$ or $r=1$. Then

$$\begin{array}{llllll}\hfill \lfloor \frac{n^2}{4}\rfloor -\lfloor \frac{{(n-1)}^2}{4}\rfloor & =\lfloor \frac{{(2k+r)}^2}{4}\rfloor -\lfloor \frac{{(2k+r-1)}^2}{4}\rfloor & \hfill & & \hfill & \\ \hfill & =\left(q^2+\mathit{qr}+\lfloor \frac{r^2}{4}\rfloor \right)-\left(q^2+q(r-1)+\lfloor \frac{{(r-1)}^2}{4}\rfloor \right)& \hfill & & \hfill & \\ \hfill & =q& \hfill (\text{since }r\in \{0,1\})& & \hfill & & \hfill \\ \hfill & =\lfloor \frac{n}{2}\rfloor .& \hfill & & \hfill & \end{array}$$

(So a discrete primitive of $\lfloor n∕2\rfloor$ is $\lfloor n^2∕4\rfloor$.)

Therefore, for all $n\in {\mathbb{N}}^{\text{∗}}$

$$\begin{array}{llll}\hfill f(n)& =\underset{k=1}{\overset{n}{\sum }}\lfloor \frac{k^2}{4}\rfloor -\underset{k=1}{\overset{n}{\sum }}\lfloor \frac{{(k-1)}^2}{4}\rfloor & \hfill & \\ \hfill & =\underset{k=1}{\overset{n}{\sum }}\lfloor \frac{k^2}{4}\rfloor -\underset{k=0}{\overset{n-1}{\sum }}\lfloor \frac{k^2}{4}\rfloor & \hfill & \\ \hfill & =\lfloor \frac{n^2}{4}\rfloor .& \hfill & \end{array}$$

This shows that for all $n\in {\mathbb{N}}^{\text{∗}}$,

$$\begin{array}{lll}\hfill f(n)=\underset{k=1}{\overset{n}{\sum }}\lfloor \frac{k}{2}\rfloor =\lfloor \frac{n^2}{4}\rfloor .& & \hfill \text{(3)}\end{array}$$

(b)

We write $x=2q+r,y=2p+s,r,s\in \{0,1\}.$ Then by (1), $$\begin{array}{llll}\hfill f(x+y)-f(x-y)& =\lfloor \frac{{(x+y)}^2}{4}\rfloor -\lfloor \frac{{(x-y)}^2}{4}\rfloor & \hfill & \\ \hfill & =\lfloor \frac{{[2(q+p)+(r+s)]}^2}{4}\rfloor -\lfloor \frac{{[2(q-p)+(r-s)]}^2}{4}\rfloor & \hfill & \\ \hfill & =\left\{{(q+p)}^2+(q+p)(r+s)+\lfloor \frac{{(r+s)}^2}{4}\rfloor \right\}& \hfill & \\ \hfill & -\left\{{(q-p)}^2+(q-p)(r-s)+\lfloor \frac{{(r-s)}^2}{4}\rfloor \right\}& \hfill & \\ \hfill & =4\mathit{pq}+2\mathit{qs}+2\mathit{pr}+\lfloor \frac{{(r+s)}^2}{4}\rfloor -\lfloor \frac{{(r-s)}^2}{4}\rfloor .& \hfill & \end{array}$$

Moreover

$$\lfloor \frac{{(r+s)}^2}{4}\rfloor -\lfloor \frac{{(r-s)}^2}{4}\rfloor =\mathit{rs},$$

since both members are $0$ if $r=0$ or $s=0$, and both are $1$ if $r=s=1$. Therefore

$$\begin{array}{llll}\hfill f(x+y)-f(x-y)& =4\mathit{pq}+2\mathit{qs}+2\mathit{pr}+\mathit{rs}& \hfill & \\ \hfill & =(2q+r)(2p+s)& \hfill & \\ \hfill & =\mathit{xy}.& \hfill & \end{array}$$

This shows that

$$f(x+y)-f(x-y)=\mathit{xy}(x>y>0).$$

For instance, using the preceding table

No need to learn multiplication tables anymore ! □