# How do I prove this sum is not an integer

Assume that $k,n\in\mathbb{Z}^+$. Prove that the sum \begin{equation*} \dfrac{1}{k+1}+\dfrac{1}{k+2}+\dfrac{1}{k+3}+\ldots +\dfrac{1}{k+n-1}+\dfrac{1}{k+n} \end{equation*} is not an integer.

The case $k=0$ is proved in this question: "Is there an elementary proof that $\sum_{k=1}^{n}\frac{1}{k}$ is never an integer?"

-
Note that your sum is merely $H_{k+n}-H_k$; a proof similar to the one in the linked question might work here as well. – J. M. Sep 22 '10 at 15:32

The proof that I gave in that thread works just as well here. It depends only on the fact that in any contiguous sequence of integers (here denominators) the maximal power $\rm 2^k$ that divides any element occurs in precisely one element. Indeed, after the first (necessarily odd) multiple of $\rm 2^k$, the next multiple would, by contiguity, be an even multiple, so a multiple of $\rm 2^{k+1}$, contra maximality. Here is said proof:

HINT $\;$ Since there is a unique denominator $\rm 2^k$ having maximal power of $2$, upon multiplying all terms through by $\rm 2^{k-1}$ one deduces the contradiction that $\rm\; a/2 = b/c \;$ with $\rm \; a,\ c \:$ odd. As an example:

$\quad\quad\quad\quad\quad\quad m = \frac{1}{2} + \frac{1}{3} +\; \frac{1}{4} \;+\; \frac{1}{5} + \frac{1}{6} + \frac{1}{7}$

$\quad\quad\Rightarrow\quad\;\; 2m = \; 1 + \frac{2}{3} +\; \frac{1}{2} \;+\; \frac{2}{5} + \frac{1}{3} + \frac{2}{7}$

$\quad\quad\Rightarrow\quad -\frac{1}{2} = \; 1 + \frac{2}{3} - 2m + \frac{2}{5} + \frac{1}{3} + \frac{2}{7}$

The prior sum has all odd denominators so reduces to a fraction with odd denominator $\rm d\:|3\cdot 5\cdot 7$.

Note $\:$ I purposely avoided any use of valuation theory because Anton requested an "elementary" solution. The above proof can easily be made comprehensible to a high-school student. The proof is trivial to anyone who knows valuation theory: namely the sum has a lone dominant term with 2-adic value $\rm v_2<0\:$ so, by the domination principle, the sum has 2-adic value $\rm v_2<0\:,\:$ i.e. the sum has even denominator in lowest terms, so it is nonintegral.

-
Would you mind transcribing here your proof? – Américo Tavares Sep 22 '10 at 16:17

{Differences of harmonic numbers are not integers}

Consider $\sum_{k=m}^n {1\over k}$. Find the largest power of $2^r$ that divides one of the denominators between $m$ and $n$. There can be no even multiples of $2^r$ between $m$ and $n$, hence there is only one odd multiple.

Therefore $2^{r-1}(1/m+\cdots+1/n)$ is equal to $1/2o_1$ plus a bunch of fractions with odd denominator. Adding them gives one fraction with an odd denominator, write it as $x/o_2$. Here $o_1$ and $o_2$ are odd integers.

We have $2^{r-1}(1/m+\cdots+1/n)=1/2o_1+x/o_2$ so that $${1\over m}+\cdots+{1\over n}={2xo_1+o_2\over 2^r o_1 o_2}.$$ Therefore $2^r$ divides the denominator. If $n\not=m$, then $r\geq1$ and the sum is not an integer.

Cf. Exercise 6.21 (page 311) of Graham, Knuth, and Patashnik.

-