# Proof using the p-adic valuation

$$\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!

• No you don't get (1) this way. What you get is $v_2(\sum^n n!/i)=v_2(\sum^{[n/2]} n!/2i)$. You have to iterate this formula to get (1). – Carot Dec 29 '19 at 9:34
• I am sorry but....I still can't get it... – Vann Dec 29 '19 at 9:44

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), hence $$2^m\leq n<2^{m+1}$$. Consequently, $$2^mq>n$$ for every $$q\geq 2$$, hence $$v_2(i) 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}

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$$.