# Partial sum of a given series

An Exercise from Apostol's Introduction to Analytic Number Theory which I am not able to solve.

Let $\mathsf{S_{n}}$ denote the $n$-th partial sum of the series: $$\sum\limits_{r=1}^{\infty} \frac{1}{r(r+1)}$$

Prove that for every integer $k>1$, there exists integers $m$ and $n$, such that $$s_{m}-s_{n} =\frac{1}{k}$$

-
You know you can use partial fraction decomposition on your summand, yes? –  Guess who it is. Oct 18 '10 at 17:29
$s_m - s_n < 1/2$ so how can this be true for $k=2$? –  Derek Jennings Oct 18 '10 at 17:38
@Derek: Take $m = 1$, $n = 0$. The problem doesn't state that $m$ and $n$ must be positive integers. –  Mike Spivey Oct 18 '10 at 17:58
@Mike Spivey Note that the sum starts at r=1. –  Derek Jennings Oct 18 '10 at 18:10
@Derek Jennings: Right, but then if you take $n=0$, you get an empty sum, which is 0. –  Mike Spivey Oct 18 '10 at 18:14

When you've worked out your formula for $s_m-s_n,$ consider $m=(n+1)^2+n.$

-

(EDIT: My original post took $p$ to be the smallest prime that divides $k$. This is unnecessary. You can take $p$ to be any number other than 1 that divides $k$. Doing so gives you not just one solution but $d(k)-1$ solutions, one for each of the divisors of $k$ other than 1.)

(SECOND EDIT: See the answer to this question for all solutions in $m$ and $n$.)

First, $$\frac{1}{r(r+1)} = \frac{1}{r} - \frac{1}{r+1}.$$ Then $$s_n = \sum_{r=1}^n \left(\frac{1}{r} - \frac{1}{r+1}\right) = 1 - \frac{1}{n+1}.$$

Thus, for any $m,n \geq 1$, $$s_m - s_n = \frac{1}{n+1} - \frac{1}{m+1} = \frac{m-n}{(m+1)(n+1)}.$$

We want to find $m,n$ such that this last expression is equal to $\frac{1}{k}$. Let $p$ be any positive integer other than 1 that divides $k$. Take $m = (p-1)k-1$. Clearly $m$ is a positive integer.

Then we want to show that the resulting $n$ that solves $$\frac{m-n}{(m+1)(n+1)} = \frac{1}{k}$$ is also an integer.

We have

$$\frac{m-n}{(m+1)(n+1)} = \frac{1}{k} \Rightarrow (m-n)k = (m+1)(n+1)$$ $$\Rightarrow ((p-1)k-1 - n)k = (p-1)k(n+1) \Rightarrow (p-1)k-1 - n = (p-1)n + p-1$$ $$\Rightarrow pn = (p-1)k - p \Rightarrow n = \frac{(p-1)k}{p} - 1,$$

which means that $n$ is an integer because $p|k$.

Thus we have a family of solutions $$m = (p-1)k-1, n = \frac{(p-1)k}{p} - 1,$$ where $p$ is any positive integer other than 1 that divides $k$.

This works even in the case $k = 2$ because then we just get $m = 1$, $n = 0$.

-
Awesome, Mike! Apostol's problems are hard! –  anonymous Oct 18 '10 at 19:48

By partial fractions it telescopes to a sum matching the RHS of this well-known Egyptian fraction sum

$$\rm \frac{1}k\ =\ \frac{1}{k-1}\ -\ \frac{1}{k\:(k-1)}$$

-

First prove that $S_n=1-\frac{1}{n+1}$ by induction.

-