Proof using the p-adic valuation

Question

$$\text{Prove that }\sum_{i=1}^n \frac{1}{i}\text{ is not an integer for }n\ge 2$$

Here is the solution :

Notice that $$\sum_{i=1}^n \frac{1}{i} = \sum_{i=1}^n \frac{\frac{n!}{i}}{n!}$$ We consider $v_2\left(\sum_{i=1}^n \frac{n!}{i}\right)$. We know that $$v_2\left(\frac{n!}{2i-1} + \frac{n!}{2i}\right)=v_2\left(\frac{n!}{2i}\right)$$We then get $v_2\left(\frac{n!}{4i-2}+\frac{n!}{4i}\right)=v_2\left(\frac{n!}{4i}\right)$ and repeating to sum up the factorial in this way we arrive at $$v_2\left(\sum_{i=1}^n\frac{n!}{i}\right)=v_2\left(\frac{n!}{2^{\lfloor \log_2 n\rfloor}}\right)\tag{1}$$

I don't understand from the part : "and repeating to sum up the factorial this way we arrive at...", where did equation $(1)$ come from? Can anyone help? Thanks!

Answer 1

Alternative solution. Equation $(1)$ can be obtained from a general statement: if $v_p(a_i)>v_p(a_m)$ for every $1\leq i\leq n$ with $i\neq m$, then $$v_p\left(\sum_{i=1}^na_i\right)=v_p(a_m)$$ For we have \begin{align} v_p\Biggl(\sum_{1\leq i\leq n\\i\neq m}a_i\Biggr) &\geq\inf_{1\leq i\leq n\\i\neq m}v_p(a_i)\\ &>v_p(a_m) \end{align} consequently \begin{align} v_p\Biggl(\sum_{1\leq i\leq n}a_i\Biggr) &=v_p\Bigl(a_m+\sum_{1\leq i\leq n\\i\neq m}a_i\Bigr)\\ &=\inf\left\{v_p(a_m),v_p\Biggl(\sum_{1\leq i\leq n\\i\neq m}a_i\Biggr)\right\}\\ &=v_p(a_m) \end{align}

In your case, let $m=\lfloor\log_2(n)\rfloor$; then $m\leq\log_2(n)<m+1$, hence $2^m\leq n<2^{m+1}$. Consequently, $2^mq>n$ for every $q\geq 2$, hence $v_2(i)<m$ for every $1\leq i\leq n$ with $i\neq 2^m$. This proves: \begin{align} &v_2\left(\frac{n!}i\right)>v_2\left(\frac{n!}{2^m}\right)& &i\neq 2^m \end{align} Thus\begin{align} v_2\Biggl(\sum_{1\leq i\leq n}\frac{n!}{i}\Biggr)=v_2\Bigl(\frac{n!}{2^m}\Bigr) \end{align}

Answer 2

I liked the problem and thought I'd think about it for a bit. Here's my proof.

Being an integer can also be described as $|\sum_{i=1}^n \frac{1}{i}|_p\le 1$ for all $n \ge 2 $ and for all primes $p$. We can force a contradiction at any specific prime easily if we look at when $n=p$ then by the 'strongest wins' property of the ultrametric inequality,

$$\left| \sum_{i=1}^p \frac{1}{i} \right|_p = \left|\frac{1}{p} + \sum_{i=1}^{p-1} \frac{1}{i} \right|_p = \left| \frac{1}{p} \right|_p = p > 1$$

At this prime, we only know $\sum_{i=1}^n \frac{1}{i}$ is not an integer in the range $p \le n < 2p$ as there is no competition with the $\frac{1}{p}$ term. At $n=2p$ we have a potential competition with $\left| \frac{1}{p} +\frac{1}{2p} \right|_p\le p $ which may be 1 or less, which means it can potentially be an integer after that.

However since between $p$ and $2p$ we are guaranteed a prime $q$ by Bertrand's postulate, then we have found a new counterexample $|\sum_{i=1}^q \frac{1}{i}|_q = q > 1$ which is valid on the larger range $p \le n < 2q$ and so by induction we can always find a prime further out, thus the sum is never an integer for $n \ge 2$.