8
$\begingroup$

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$$

$\endgroup$
  • $\begingroup$ Hint: When you expand all the squares, how many terms $$\frac1{k^2}$$ do you get? And how many terms $$\frac1{k\ell}$$ for $k\ne\ell$? $\endgroup$ – Did Sep 16 '17 at 16:28
  • $\begingroup$ Interesting question (+1). The answer is $4032$ i.e. $2\times 2016$. But why? $\endgroup$ – hypergeometric Sep 16 '17 at 16:29
  • $\begingroup$ @hypergeometric "But why?" See my previous comment. :-) $\endgroup$ – Did Sep 16 '17 at 16:31
  • $\begingroup$ @Did. It was rhetorical question :). For the OP. $\endgroup$ – hypergeometric Sep 16 '17 at 16:32
  • $\begingroup$ I still can not figure it out and also how do you know the answer to this question in short time. Is it some kind of "common sense" for you? $\endgroup$ – jdhao Sep 16 '17 at 16:43
6
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ Nice answer and reference (+1). $\endgroup$ – hypergeometric Sep 16 '17 at 17:13
  • 2
    $\begingroup$ Interesting to note that Jack's solution which you referenced was posted exactly three years ago today! $\endgroup$ – hypergeometric Sep 16 '17 at 17:30
  • $\begingroup$ I like your answer! :-( $\endgroup$ – Robert Z Sep 17 '17 at 18:32
  • $\begingroup$ @RobertZ why the sad face ? $\endgroup$ – Gabriel Romon Sep 17 '17 at 18:47
  • $\begingroup$ @Gabriel Romon Because I wrote a similar answer but I got downvotes! $\endgroup$ – Robert Z Sep 17 '17 at 19:15
3
$\begingroup$

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.$$

$\endgroup$
  • $\begingroup$ Nice answer (+1). $\endgroup$ – hypergeometric Sep 16 '17 at 17:07
  • $\begingroup$ @hypergeometric, thank you. $\endgroup$ – farruhota Sep 16 '17 at 17:09
2
$\begingroup$

(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}$$

$\endgroup$
  • $\begingroup$ this is like a top down solution where we go from root to leaf, the other solution is kind of like bottom up solution $\endgroup$ – jdhao Sep 18 '17 at 15:43
  • $\begingroup$ @Hao - Yes, it is! For this approach, I thought it would be clearer to expand it from the closed form. $\endgroup$ – hypergeometric Sep 18 '17 at 15:45
1
$\begingroup$

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).

$\endgroup$
  • 1
    $\begingroup$ Hmmm... Probably the least enlightening "hint", no? $\endgroup$ – Did Sep 16 '17 at 16:33
  • $\begingroup$ @Did It is not very elegant, but it works. ;-) $\endgroup$ – Robert Z Sep 16 '17 at 17:15
  • $\begingroup$ So, not a "hint" at all, right? $\endgroup$ – Did Sep 16 '17 at 17:23
  • $\begingroup$ @Did No, this is not a hint. $\endgroup$ – Robert Z Sep 16 '17 at 17:27
  • $\begingroup$ @Robert Z Elegant general solution (+1). You might be interested as well in my recent question/solution math.stackexchange.com/questions/2419134/… $\endgroup$ – Dr. Wolfgang Hintze Sep 18 '17 at 8:32
1
$\begingroup$

(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}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.