2

I tried making a double sum $$\sum_{r=1}^{n} \sum _{k=1}^r \frac{2r+1}{k}$$

But since the final limits aren’t same the changing of orders cannot be used. Can I get a hint on how to solve it?

Gary
  • 31,845
Aditya
  • 6,191
  • 1
    If you know that $P,Q$ are polynomials, then they are determined by their degrees and a few initial values. Perhaps you should first try to guess their degree, and then try to use the initial values to guess them. – Sarvesh Ravichandran Iyer Jul 24 '21 at 10:22

3 Answers3

2

I think a double sum is a good idea. Maybe, you need something like Fubini with $f(r,k)=\begin{cases}1, & k\leq r\\0,&k>r\end{cases}$ $$\begin{align}\sum_{r=1}^{n} \sum _{k=1}^r \frac{2r+1}{k}&=\sum_{r=1}^{n} \sum _{k=1}^{n}f(r,k) \frac{2r+1}{k}\\ &=\sum_{k=1}^{n} \sum _{r=1}^{n}f(r,k) \frac{2r+1}{k}\\ &=\sum_{k=1}^{n} \sum _{r=k}^{n} \frac{2r+1}{k}\\ &=\sum_{k=1}^n\frac 1k\cdot\big((n+1)^2-k^2\big)\\ &=\sum_{k=1}^n\frac 1k(n+1)^2-\sum_{k=1}^nk\\ &=\sum_{k=1}^n\frac 1k(n+1)^2-\frac 12n(n+1)\\ &=\left(\sum_{k=1}^{n+1}\frac 1k-\frac{1}{n+1}\right)(n+1)^2-\frac 12n(n+1)\\ &=\sum_{k=1}^{n+1}\frac 1k(n+1)^2-\frac 12n(n+1)-(n+1)\\ &=\sum_{k=1}^{n+1}\frac 1k(n+1)^2-\frac 12(n+1)(n+2) \end{align}.$$ Hopefully, there is no mistake in it.

Jochen
  • 2,260
  • 1
    This is of the form $R(n)\phi (n) - S(n)$ and not $P(n)\phi (n+1) - Q(n)$. – Gary Jul 24 '21 at 11:00
  • Yes, you're right. Thank you. I corrected it. Now, it's from the desired form :) – Jochen Jul 24 '21 at 11:03
  • I am not aware of the method you used. Can you elaborate? – Aditya Jul 24 '21 at 11:21
  • 1
    @ Aditya: I can try. We like to sum up all terms $\frac{2r+1}{k}$ with$k\leq r$ up to an integer $n$. If we draw all this points in a coordinate system $(k,r)$ we have all points under the diagonal. We can describe the set if we first fix $k$ and then observe which $r$ we get or the other way. If we define $A={(k,r)\in \mathbb N : 1\leq k\leq r \leq n, }$, for every function $g\colon \mathbb N\times\mathbb N\to\mathbb R$, we get $$\sum_{k=1}^n \sum_{r=k}^n g(k,r)= \sum_{(k,r)\in A} g(k,r)= \sum_{r=1}^n \sum_{k=1}^r g(k,r)$$ – Jochen Jul 24 '21 at 11:32
  • @Jochen: I just recognized you already provided a complete and correct answer. (+1) – Markus Scheuer Jul 24 '21 at 14:43
1

EDIT:

Using Python, I detected a small error in the final lines, which I have now fixed.

OP:

The sum

$$\sum_{r=1}^n\sum_{k=1}^r\frac{2r+1}{k}=3(1)+5\left(1+\frac{1}{2}\right)+7\left(1+\frac{1}{2}+\frac{1}{3}\right)+\dots+(2n+1)\left(1+\frac{1}{2}+\dots+\frac{2n+1}{n}\right)$$

Can be regrouped into sub-series as this:

$$(3(1)+5(1)+7(1)+\dots)+\left(\frac{5}{2}+\frac{7}{2}+\dots\right)+\left(\frac{7}{3}+\frac{9}{3}+\dots\right)+\dots$$

Each of these forms an arithmetic series sum. The formula for an arithmetic sum is $$\frac{2a+(m-1)r}{2}\cdot m=a+(a+r)+(a+2r)+\dots+(a+(m-1)r)$$

In the expansion of your sum, each sub-series (as I will call the groupings I made) begins with the number $2k+1$ divided by the $k$, where $k$ is the index of the sub-series, so $a=\frac{2k+1}{k}$. Each successive term is an odd number divided by $k$, so the term-term difference is $\frac{2}{k}=r$. Finally, since each sub-series is shorter in length, it turns out that there are $m=n-k+1$ numbers in the sub-series. So, the sum of each sub-series, such as $3+5+7+\dots$ ($k=1$) or $\frac{5}{2}+\frac{7}{2}+\dots$ ($k=2$) is:

$$\begin{align}S(k,n)&=\frac{2\cdot\frac{2k+1}{k}+(n-k+1-1)\cdot\frac{2}{k}}{2}\cdot(n-k+1)\\&=\left(\frac{2k+1}{k}+\frac{n-k}{k}\right)\cdot(n-k+1)\\&=\frac{n+k+1}{k}\cdot(n-k+1)\\&=\frac{n^2+2n+1-k^2}{k}\\&=\frac{(n+1)^2}{k}-k\end{align}$$

Now the original series can be written as the sum of the sums of all these sub-series:

$$\sum_{r=1}^n\sum_{k=1}^r\frac{2r+1}{k}=\sum_{k=1}^nS(k,n)=\sum_{k=1}^n\frac{(n+1)^2}{k}-k$$

Consider $S(k=n+1,n)$: that term would equal $(n+1)^2/(n+1)-(n+1)=0$. Therefore we can increment the number of terms on the above sum safely, as adding zero won't change it.

We now want to evaluate

$$\sum_{k=1}^{n+1}\frac{(n+1)^2}{k}-k=(n+1)^2\left(\sum_{k=1}^{n+1}\frac{1}{k}\right)-k=(n+1)^2\phi(n+1)-\sum_{k=1}^{n+1}k$$

The last sum is a simple triangle formula sum, and so finally we get:

$$(n+1)^2\phi(n+1)-\sum_{k=1}^{n+1}k=(n+1)^2\phi(n+1)-\frac{(n+1)(n+2)}{2}=P(n)\phi(n+1)-Q(n)$$

Where $$P(n)=(n+1)^2\text{ and }Q(n)=\frac{(n+1)(n+2)}{2}$$

FShrike
  • 40,125
  • Where is the $\frac{2k+1}{k}$term? Did you mean $\frac{2r+1}{k}$? – Aditya Jul 24 '21 at 14:21
  • @Aditya No I did not. The "$k$" here refers to a specific sub-series, indexed by $k$: for example, the sub-series grouping of $(5/2)+(7/2)+(9/2)+\dots$ is indexed by $k=2$ - which you will note begins with the term $(5/2)=(2k+1)/k$ – FShrike Jul 24 '21 at 14:23
  • @Aditya I've edited my answer to be clearer about $k$ – FShrike Jul 24 '21 at 14:27
  • @Aditya The series I talk about for most of the answer are separate from your series involving $r$; I broke up that series into a new double series (with the same sum) that is easier to deal with – FShrike Jul 24 '21 at 14:40
1

Hint: The sums can be interchanged, since we have \begin{align*} \sum_{r=1}^{n} \sum _{k=1}^r \frac{2r+1}{k} =\sum_{\color{blue}{1\leq k\leq r\leq n}}\frac{2r+1}{k} =\sum_{k=1}^n\sum_{r=k}^n\frac{2r+1}{k} \end{align*} and this might be helpful to solve the problem.

Note: The numbers $\phi(r)=\sum_{k=1}^r \frac{1}{k}$ are more commonly denoted by $H_r$ and are called harmonic numbers.

Markus Scheuer
  • 108,315
  • I did manage to get to that interchange (not sure if it was right), but left because I couldn’t exploit it. How to move beyond that? – Aditya Jul 24 '21 at 14:16
  • @Aditya: The answer from Jochen is fine and correct. It has the required form $\phi(n+1) P(n)+Q(n)$. You might simply want to skip the lines with $f(r,k)$. – Markus Scheuer Jul 24 '21 at 14:45