How to compute $S_{2016}=\sum\limits_{k=1}^{2016}\left(\sum\limits_{n=k}^{2016}\frac1n\right)^2+\sum\limits_{k=1}^{2016}\frac1k$?

I came across a question asking the value of the following sum:

\begin{align}
\left(1+ \frac{1}{2}+\frac{1}{3}+\cdots +\frac 1{2015}+\frac{1}{2016}\right)^2 \\
+\left(\frac{1}{2}+\frac{1}{3}+\cdots +\frac 1{2015}+\frac{1}{2016}\right)^2 \\
+ \left(\frac{1}{3}+\cdots +\frac 1{2015}+\frac{1}{2016}\right)^2 \\[5 pt]
+\cdots \qquad\quad \vdots\qquad\qquad\\[5 pt]
+ \left(\frac{1}{2015}+\frac{1}{2016}\right)^2 \\
+ \left(\frac{1}{2016}\right)^2\\
+ \left(1+ \frac{1}{2}+\frac{1}{3}+\cdots +\frac 1{2015}+\frac{1}{2016}\right)\;
\end{align}

I can not find a good way to solve it. Any ideas?


Edit: That is, with no dots, $$S_{2016}=\sum_{k=1}^{2016}\left(\sum_{n=k}^{2016}\frac1n\right)^2+\sum_{k=1}^{2016}\frac1k$$

Solutions Collecting From Web of "How to compute $S_{2016}=\sum\limits_{k=1}^{2016}\left(\sum\limits_{n=k}^{2016}\frac1n\right)^2+\sum\limits_{k=1}^{2016}\frac1k$?"

Let $H_n$ be the $n$th Harmonic number with $H_0=0$.
$$\begin{align}
S_{2016}&=\sum_{k=1}^{2016}\left(\sum_{n=k}^{2016}\frac1n\right)^2+\sum_{k=1}^{2016}\frac1k\\
&=H_{2016}+\sum_{k=1}^{2016} (H_{2016}-H_{k-1})^2\\
&= H_{2016}+\sum_{k=1}^{2016} (H_{2016}^2+H_{k-1}^2-2H_{2016}H_{k-1})\\
&=H_{2016} + 2016H_{2016}^2 -2H_{2016}\sum_{k=1}^{2016}H_{k-1} + \sum_{k=1}^{2016} H_{k-1}^2\\
&=H_{2016} + 2016H_{2016}^2 -2H_{2016}\sum_{k=1}^{2015}H_{k} + \sum_{k=1}^{2015} H_{k}^2
\end{align}
$$

As computed here, $\sum_{k=1}^{2015}H_{k}= 2016H_{2015}-2015=2016H_{2016}-2016$ and $$\sum_{k=1}^{2015} H_{k}^2=2016H_{2015}^2-(2\cdot 2016+1)H_{2015} + 2\cdot 2015 $$

Replacing $H_{2015}$ with $H_{2016}-\frac{1}{2016}$ and plugging everything back into the other equality, you should get $S_{2016}=2\cdot 2016$

If you expand all:
$$S=1+2\times \frac{1}{2^2}+3\times \frac{1}{3^2}+\cdots +2016 \cdot \frac{1}{2016^2}+$$
$$2\cdot 1\left(1\cdot \frac12+1\cdot \frac13+\cdots 1\cdot \frac{1}{2016}\right)+$$
$$2\cdot 2\left(\frac12 \cdot \frac13+\frac12 \cdot \frac14+\cdots +\frac12 \cdot \frac{1}{2016}\right)+$$
$$\vdots$$
$$2\cdot 2015\left(\frac{1}{2015}\cdot \frac{1}{2016}\right)+$$
$$1+\frac12+\cdots +\frac{1}{2016}=$$
$$2\left(1+\frac12+\cdots+\frac{1}{2016}\right)+$$
$$2\left(\frac12+\frac13+\cdots+\frac{1}{2016}\right)+$$
$$\vdots$$
$$2\left(\frac{1}{2016}\right)=$$
$$2\cdot (2016)=4032.$$

We show that for any positive integer $n$
$$
S_n:=\sum_{j=1}^n\left(\sum_{k=j}^n\frac{1}{k}\right)^2+\sum_{k=1}^n\frac{1}{k}=\sum_{j=1}^{n} (H_n-H_{j-1})^2 +H_n=2n.$$
where $H_n=\sum_{k=1}^n\frac{1}{k}$.
We have that
\begin{align*}
S_n&=nH_n^2-2H_n\sum_{j=1}^{n}H_{j-1}+\sum_{j=1}^{n}H_{j-1}^2+H_n\\
&=
nH_n^2-2H_n((n+1)H_{n}-n-H_n)\\
&\quad+((n+1)\,H_n^2-(2n+1)\,H_n+2n-H_n^2)+H_n\\
&=2n
\end{align*}
where we used
$$\sum_{j=1}^{n}H_j=(n+1)\,H_n-n,\quad \sum_{j=1}^n H_j^2=(n+1)\,H_n^2-(2n+1)\,H_n+2n$$
(see Sum of Squares of Harmonic Numbers).

(new solution – a bit shorter)

$$\require{cancel}\begin{align}
&\;\;\;\sum_{j=1}^n\left(\sum_{r=j}^n\frac 1r\right)^2+\sum_{j=1}^n\frac 1j\\
&=\sum_{j=1}^n\left(\sum_{r=j}^n\sum_{s=j}^n\frac 1{rs}\right)+\sum_{j=1}^n\frac 1j\\
&=\sum_{j=1}^n\left[2\sum_{r=j}^n\sum_{s=r}^n\frac 1{rs}-\sum_{r=j}^n\frac 1{r^2}\right]+\sum_{j=1}^n\frac 1j\\
&=2\sum_{j=1}^n\sum_{r=j}^n\sum_{s=r}^n\frac 1{rs}-\sum_{j=1}^n\sum_{r=j}^n\frac 1{r^2}+\sum_{j=1}^n\frac 1j\\
&=2\sum_{r=1}^n\sum_{j=1}^r\sum_{s=r}^n\frac 1{rs}-\sum_{r=1}^n\sum_{j=1}^r\frac 1{r^2}+\sum_{r=1}^n\frac 1r
&&\scriptsize(1\le j\le r\le n)\\
&=\color{lightgrey}{2\sum_{r=1}^n\sum_{s=r}^nr\cdot \frac 1{rs}-\sum_{r=1}^nr\cdot \frac 1{r^2}+\sum_{r=1}^n \frac 1r}\\
&=2\sum_{r=1}^n\sum_{s=r}^n\frac 1s\cancel{-\sum_{r=1}^n\frac 1r}+\cancel{\sum_{r=1}^n\frac 1r}\\
&=2\sum_{s=1}^n\sum_{r=1}^s\frac 1s
&&\scriptsize(1\le r\le s\le n)\\
&=2\sum_{s=1}^n1\\
&=\color{red}{2n}
\end{align}$$

Putting $n=2016$ gives the solution as $2\times 2016=\color{red}{4032}$.


(earlier solution below)

$$\begin{align}
\left(1+\frac 12+\frac 13+\cdots+\frac 1{n-1}+\frac 1n\right)\;\, \\
+\left(1+\frac 12+\frac 13+\cdots+\frac 1{n-1}+\frac 1n\right)^2\\
+\left(\frac 12+\frac13+\cdots+\frac1{n-1}+\frac1n\right)^2\\
+\left(\frac13+\cdots+\frac1{n-1}+\frac1n\right)^2\\
+\cdots\qquad \qquad\vdots\quad \quad\\
+\left(\frac 1{n-1}+\frac 1n\right)^2\\
+\left(\frac 1n\right)^2\\
&=\sum_{j=1}^n \frac 1j+\sum_{j=1}^n\left(\sum_{r=j}^n\frac 1r\right)^2\\\
&=\sum_{j=1}^n\frac 1j+\sum_{j=1}^n\left(\sum_{r=j}^n \frac 1{r^2}+2\sum_{j\le r<s}^n\frac 1{rs}\right)\\
&=\sum_{j=1}^n\frac 1j+\sum_{j=1}^n\sum_{r=j}^n\frac 1{r^2}+2\sum_{j=1}^n\sum_{r=j}^n\sum_{s=r+1}^n\frac 1{rs}\\
&=\sum_{j=1}^n\frac 1j+\sum_{r=1}^n\sum_{j=1}^r\frac 1{r^2}+2\sum_{r=1}^{n-1}\sum_{j=1}^r\sum_{s=r+1}^n\frac 1{rs}
&&\scriptsize(1\le j\le r\le n)\atop{\scriptsize(1\le j\le r<s\le n)}\\
&=\sum_{j=1}^n\frac 1j+\sum_{r=1}^nr\cdot \frac 1{r^2}+2\sum_{r=1}^{n-1}\sum_{s=r+1}^nr\cdot \frac 1{rs}\\
&\color{lightgrey}{=\sum_{j=1}^n \frac 1j+\sum_{r=1}^n \frac 1r+2\sum_{r=1}^{n-1}\sum_{s=r+1}^n\frac 1s}\\
&=2\sum_{r=1}^n \frac 1r+2\sum_{r=1}^{n-1}\sum_{s=r+1}^n\frac 1s\\
&=2\sum_{r=0}^{n-1}\sum_{s=r+1}^n\frac 1s\\
&=2\sum_{s=1}^n\frac 1s\sum_{r=0}^{s-1}1\\
&=2\sum_{s=1}^n\frac 1s\cdot s\\
&=\color{red}{2n}\end{align}$$

Putting $n=2016$ gives the solution as $2\times 2016=\color{red}{4032}$.

(Please excuse this second solution post – it is a bit too long to be included in the original solution)

$$\scriptsize\begin{align}
\color{red}{2n}
&=\boxed{\begin{array}{l}
&2\big[1\\
&\;\; +\left(\frac 12+\frac 12\right)\\
&\;\;+\left(\frac 13+\frac 13+\frac 13\right)\\
&\;\;+\qquad \cdots\qquad\ddots\\
&\;\;+\left(\frac 1n+\frac 1n+\frac 1n+\cdots+\frac 1n\right)\big]
\end{array}}\\\\
&=\boxed{\begin{array}{r}
2\big[\left(1+\frac 12+\frac 13+\frac 14+\cdots +\frac 1n\right)&\\
+\left(\frac 12+\frac 13+\frac 14+\cdots +\frac 1n\right)&\\
+\left(\frac 13+\frac 14+\cdots +\frac 1n\right)&\\
+\ddots\quad\cdots\quad \vdots\\
+\left(\frac 1n\right)\big]
\end{array}}\\\\
&=\boxed{\begin{array}{r}
2\big[1\cdot\frac 11\left(1+\frac 12+\frac 13+\frac 14+\cdots +\frac 1n\right)&\\
+2\cdot \frac 12\left(\frac 12+\frac 13+\frac 14+\cdots +\frac 1n\right)&\\
+3\cdot \frac 13\left(\frac 13+\frac 14+\cdots +\frac 1n\right)&\\
+\ddots\quad\;\cdots\;\quad\vdots\\
+n\cdot \frac 1n\left(\frac 1n\right)\big]
\end{array}}\\\\
&=\boxed{\begin{array}{r}
2\big[1\left(1+\frac 12+\frac 13+\frac 14+\cdots+\frac 1n\right)& \\
+\frac 12\left(\frac 12+\frac 13+\frac 14+\cdots+\frac 1n\right)&\\
+\frac 13\left(\frac 13+\frac 14+\cdots+\frac 1n\right)&\\
+\ddots\quad\cdots\quad\vdots\\
+\frac 1n\left(\frac 1n\right)\end{array}
\begin{array}{r}
\\
+\frac 12\left(\frac 12+\frac 13+\frac 14+\cdots+\frac 1n\right)&\\
+\frac 13\left(\frac 13+\frac 14+\cdots+\frac 1n\right)&\\
+\ddots\quad\cdots\quad\vdots\\
+\frac 1n\left(\frac 1n\right)\end{array}
\begin{array}{r}
\\
\\
+\frac 13\left(\frac 13+\frac 14+\cdots+\frac 1n\right)&\\
+\ddots\quad\cdots\quad\vdots\\
+\frac 1{n}\left(\frac 1n\right)\end{array}
+\cdots
\begin{array}{r}
\\
\\
\\
\\
+\frac 1n\left(\frac 1n\right)\big]\end{array}}\\\\
&=\boxed{\color{blue}{\begin{array}{r}
2\big[1\left(\quad\frac 12+\frac 13+\frac 14+\cdots+\frac 1n\right)& \\
+\frac 12\left(\quad\frac 13+\frac 14+\cdots+\frac 1n\right)&\\
+\frac 13\left(\quad\frac 14+\cdots+\frac 1n\right)&\\
+\ddots\quad\cdots\quad\vdots\\
+\frac 1{n-1}\left(\quad\frac 1n\right)\end{array}}
\color{green}{\begin{array}{r}
\\
+\frac 12\left(\quad\frac 13+\frac 14+\cdots+\frac 1n\right)&\\
+\frac 13\left(\quad\frac 14+\cdots+\frac 1n\right)&\\
+\ddots\quad\cdots\quad\vdots\\
+\frac 1{n-1}\left(\quad\frac 1n\right)\end{array}}
\color{orange}{\begin{array}{r}
\\
\\
+\frac 13\left(\quad\frac 14+\cdots+\frac 1n\right)&\\
+\ddots\quad\cdots\quad\vdots\\
+\frac 1{n-1}\left(\quad\frac 1n\right)\end{array}}
+\cdots
\begin{array}{r}
\\
\\
\\
\\
+\frac 1{n-1}\left(\quad\frac 1n\right)\big]\end{array}\\
+
\color{blue}{\begin{array} .\big(1+\frac1{2^2}+\frac 1{3^2}+\frac 1{4^2}+\cdots+\frac 1{n^2}\big)\end{array}}
+\color{green}{\begin{array}.\big(\frac1{2^2}+\frac 1{3^2}+\frac 1{4^2}+\cdots+\frac 1{n^2}\big)
\end{array}}
+\color{orange}{\begin{array}.\big(\frac 1{3^2}+\frac 1{4^2}+\cdots+\frac 1{n^2}\big)
\end{array}}
+\cdots\qquad\qquad
+\begin{array}.\big(\frac 1{n^2}\big)\end{array}
\\
+
\color{magenta}{\begin{array} .\big(1+\frac1{2^2}+\frac 1{3^2}+\frac 1{4^2}+\cdots+\frac 1{n^2}\big)\end{array}
+\begin{array}.\big(\frac1{2^2}+\frac 1{3^2}+\frac 1{4^2}+\cdots+\frac 1{n^2}\big)
\end{array}
+\begin{array}.\big(\frac 1{3^2}+\frac 1{4^2}+\cdots+\frac 1{n^2}\big)
\end{array}
+\cdots\qquad\qquad
+\begin{array}.\big(\frac 1{n^2}\big)\end{array}}}\\\\
&=
\boxed{
\;\;\color{blue}{\begin{array}
.\big(1+\frac12+\frac 13+\frac 14+\cdots+\frac 1n\big)^2
\end{array}}
+\quad\color{green}{\begin{array}
.\big(\frac12+\frac 13+\frac 14+\cdots+\frac 1n\big)^2
\end{array}}
+\;\color{orange}{\begin{array}
.\big(\frac 13+\frac 14+\cdots+\frac 1n\big)^2
\end{array}}
+\cdots+\begin{array}
.\big(\frac 1{n-1}+\frac 1n\big)^2
\end{array}+
\tiny\big(\frac 1n\big)^2\\
+\color{magenta}{\begin{array}.\big(1+2\cdot \frac 1{2^2}+3\cdot \frac 1{3^2}+\cdots+n\cdot \frac 1{n^2}\big)\end{array}}}\\\\
&=
\boxed{
\;\;\begin{array}
.\big(1+\frac12+\frac 13+\frac 14+\cdots+\frac 1n\big)^2
\end{array}
+\quad\begin{array}
.\big(\frac12+\frac 13+\frac 14+\cdots+\frac 1n\big)^2
\end{array}
+\;\begin{array}
.\big(\frac 13+\frac 14+\cdots+\frac 1n\big)^2
\end{array}
+\cdots+\begin{array}
.\big(\frac 1{n-1}+\frac 1n\big)^2
\end{array}+
\tiny\big(\frac 1n\big)^2\\
+\begin{array}.\big(1+\frac 12+\frac 13+\frac 14+\cdots+\frac 1n\big)\end{array}}
\end{align}$$


Addendum

The solution can be expressed in a much neater and compact form using summation notation, and also the following notation which I have just conjured up.

Define the Back-Ended Harmonic Series as $$B_{r,n}=B_r=\frac 1r+\frac 1{r+1}+\frac 1{r+2}+\cdots+\frac 1n\qquad (1\le r\le n;\;\; r, n\in \mathbb Z)$$
and the squares of terms of the Back-Ended Harmonic Series as
$$C_{r,n}=C_r=\frac 1{r^2}+\frac 1{(r+1)^2}+\frac 1{(r+1)^2}+\cdots+\frac 1{n^2}\qquad (1\le r\le n;\;\; r, n\in \mathbb Z)$$

Using the definitions above, we have the following useful identities:
$$\begin{align}
B_r&=\frac 1r+B_{r+1}\tag{*}\qquad \text{(recursive definition)}\\
B_r^2&=C_r+2\sum_{r\le s<t\le n} \frac 1{st}\\
&=C_r+2\sum_{s=r}^n\frac 1s\sum_{t=s+1}^n \frac 1t\\
&=C_r+2\sum_{s=r}^n \frac 1s B_{s+1}\tag{**}\\
\end{align}$$

Now back to the question.

$$\begin{align}
2n
&=2\sum_{r=1}^n r\cdot \frac 1r\\
&=2\sum_{r=1}^n\sum_{j=1}^r \frac 1r &&\text{(counting }r)\\
&=2\sum_{j=1}^n\sum_{r=j}^n\frac 1r &&\text {(swapping summation order)}\\
&=2\sum_{j=1}^nB_j&&\text{(by definition)}\\
&=2\sum_{j=1}^n j\cdot \frac 1jB_j\\
&=2\sum_{j=1}^n\sum_{k=1}^j \frac 1j B_j&&\text{(counting }j)\\
&=2\sum_{k=1}^n\sum_{j=k}^n\frac 1j B_j &&\text {(swapping summation order)}\\
&=2\sum_{k=1}^n\sum_{j=k}^n \frac 1j\left(\frac 1j+B_{j+1}\right)&&\text{(using *)}\\
&=2\sum_{k=1}^n\sum_{j=k}^n \frac 1jB_{j+1}+\sum_{k=1}^n \sum_{j=k}^n\frac 1{j^2}
+\sum_{k=1}^n \sum_{j=k}^n\frac 1{j^2}
&&\text{(isolating }\frac 1{j^2})\\
&=\underbrace{\sum_{k=1}^n\left(2\sum_{j=k}^n \frac 1jB_{j+1}+C_k\right)}\;\quad+\sum_{j=1}^n\sum_{k=1}^j \frac 1{j^2}
&&\begin{array}.\text{(using }\sum_{j=k}^n \frac 1{j^2}=C_k\\
\text{and swapping summation order)}\end{array}\\
&=\qquad \left(\sum_{k=1}^n B_k^2\right)\;\qquad\qquad+\sum_{j=1}^n j\cdot \frac 1{j^2}
&&\text{(using **)}\\
&=\qquad \left(\sum_{k=1}^n B_k^2\right)\;\qquad\qquad+\sum_{j=1}^n \frac 1{j}\\
&=\qquad \left(\sum_{k=1}^n B_k^2\right)\;\qquad\qquad +B_1\\
\end{align}$$