2
$\begingroup$

I was reading a proof to the following fact: for $n>1$, $\sum_{i=1}^{n} \frac{1}{i} \notin \mathbb{Z}$.
The proof is as follows: Denote for prime $p$ by $v_p(a)$ the p-adic valuation of $a$.
Write the sum as $\sum_{i=1}^{n}\frac{\frac{n!}{i}}{n!}$. We will show that $2$ divides the denominator more times that $2$ divides the numerator. We consider $v_2(\sum_{i=1}^{n} \frac{n!}{i})$. By the theorem $v_p(a) > v_p(b) \rightarrow v_p(a+b)=v_p(b)$ we get $v_2(\frac{n!}{2i-1}+\frac{n!}{2i})=v_2(\frac{n!}{2i})$. We then get $v_2(\frac{n!}{4i-1}+\frac{n!}{4i})=v_2(\frac{n!}{4i})$ and repeating to sum up the factorial in this way we arrive at $v_2(\sum_{i=1}^{n} \frac{n!}{i})=v_2(\frac{n!}{2^{[log_2(n)]}})$
However for $\sum_{i=1}^{n} \frac{1}{i}$ to be an integer we need $v_2(\sum_{i=1}^{n} \frac{n!}{i}) \geq v_2(n!)$ which is the same as $v_2(\frac{n!}{2^{[log_2(n)]}}) \geq v_2(n!)$ which is the same as $0 \geq v_2(n!)$ which is not true for $n>1$.

I didn't understand this proof. I followed until he said "and repeating to sum up the factorial in this way we arrive at...". What is meant there? Can someone explain in more detail what's happening?

$\endgroup$
0
$\begingroup$

Here is an easier way to understand the proof:

Let $k$ be so that $2^k \leq n <2^{k+1}$.

Write $$\sum_{i=1}^{n} \frac{1}{i}= \left(\sum_{1 \leq i \leq n ; i \neq 2^k} \frac{1}{i} \right)+\frac{1}{2^k}$$

Now, bring at the same denominator $$\left(\sum_{1 \leq i \leq n ; i \neq 2^k} \frac{1}{i} \right)=\frac{A}{B}$$ where $A,B$ is reduced.

Show that $2^k \nmid B$. Deduce from here that

$$\frac{A}{B}+\frac{1}{2^k}=\frac{C}{D}$$ $2^k |D$ but $2^k \nmid C$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for the answer, but I am looking for an explaination to the particular step I mentioned in the proof I gave, instead of an easier way to write the proof. $\endgroup$ – Omer Apr 26 at 19:23
  • $\begingroup$ @Omer Here is what they mean: $$v_2(\frac{n!}{2i-1}+\frac{n!}{2i})=v_2(\frac{n!}{2i})$$ This means $$v_2(\frac{n!}{4i-3}+\frac{n!}{4i-2})+v_2(\frac{n!}{4i-1}+\frac{n!}{4i})=v_2(\frac{n!}{4i-2})+v_2(\frac{n!}{4i}) =v_2(\frac{n!}{4i})\\v_2(\frac{n!}{8i-7}+\frac{n!}{8i-6})+v_2(\frac{n!}{8i-5}+\frac{n!}{8i-4})+v_2(\frac{n!}{8i-3}+\frac{n!}{8i-2})+v_2(\frac{n!}{8i-1}+\frac{n!}{8i})=v_2(\frac{n!}{8i-4})+v_2(\frac{n!}{8i}) =v_2(\frac{n!}{8i})\\...$$ $\endgroup$ – N. S. Apr 26 at 19:43
  • $\begingroup$ Okay, but how does that lead to the conclusion? Where does $v_2(\sum_{i=1}^{n} \frac{n!}{i})$ comes from after that? $\endgroup$ – Omer Apr 26 at 20:04
  • $\begingroup$ @Omer If you keep doing that and $2^k \leq n <2^{k+1}$ (i.e. $k= \lfloor log_2(n) \rfloor$) then you end up with $$v_2(\sum_{i=1}^{n} \frac{n!}{i})=v_2(\frac{n!}{2^k})=0$$ $\endgroup$ – N. S. Apr 26 at 20:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.