If $\phi(r) =1+\frac 12 +\frac 13… \frac 1r$ and $\sum_{r=1}^{n} (2r+1)\phi (r) =P(n)\phi(n+1)-Q(n)$. Find $P$ and $Q$. 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?
 A: 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.
A: 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}$$
A: 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.
