Verify the proof for “For every $n, q$, where $n,q \in Z^+, n\geq 2, \sum_{i=1}^n\frac1n\neq q$”. [$n^{th}$ harmonic number is never an integer]

elementary-number-theoryharmonic-numbersnumber theorysolution-verificationsummation

Background : I have little experience writing proofs. I found this problem in the book Solving Mathematical Problems by Terrence Tao. I wish to prove that $n^{th}$ harmonic number is never an integer. In the book it says that Bertrand's Postulate ($\forall n$, where $n\in Z^+\;\;\exists$, a prime $p$, such that $n<p<2n$) is required to prove it, but I tried to prove it in a more elementary manner. I believe I have found required proof and wish to have it verified and critiqued.

Theorem :
For every $n, q$, where $n,q \in Z^+, n\geq 2 $, it is true that $$\sum_{i=1}^n\frac1n\neq q$$

Proof. We will assume that the sum is equal to an integer, and reach a proof by contradiction with a counterexample.

Multiplying the individual terms by each other to make them common in denominator then adding them together results in the fraction. As per assumption, it should be equal to an integer $q$.

$$\frac{(2\times3 \times … \times n)+(1\times3\times … \times n)+ …+(1 \times 2 \times … \times (n-1))} {n!}=q$$
Thus,
$$n!q= (2\times3 \times … \times n)+(1\times3\times … \times n)+ …+(1 \times 2 \times … \times (n-1))$$
Since, $n\geq2$, therefore $n!$ is divisible by $2$.
$$2\bigg(\frac{n!}{2}\bigg)q= (2\times3 \times … \times n)+(1\times3\times … \times n)+ …+(1 \times 2 \times … \times (n-1))$$

Therefore, if $q$ is an integer, the numerator must be even for all positive integer $n$. However, taking the counterexample of $n=3$ the numerator equals $11$, which is not an even integer. This is a contradiction. Therefore the negation of our assumption must be true, and there do not exist positive integers $q, n$ such that the $n^{th}$ harmonic number equals $q$, as desired.

$QED.$

Best Answer

You have your "for all " and "there exists" mixed up. $q$ depends on $n$ so call it $q_n$. And "the numerator" depends on $n$ too so call it $u_n.$ The 1st sentence of your last paragraph should say: "Therefore if there exists $n$ such that $q_n\in \Bbb Z$ then there exists $n$ such that $u_n$ is even."... NOT "for all $n$."

For $n\in \Bbb Z^+$ let $S(n)=\sum_{j=1}^n (1/j).$ Let $V(n)$ be the largest non-negative integer $j$ such that $2^j\leq n.$ That is, $2^{V(n)}\leq n<2^{1+V(n)}.$

Prove that if $S(n)=\frac {A_n}{B_n2^{V(n)}}$ where $A_n, B_n$ are odd positive integers then $S(n+1)=\frac {A_{n+1}}{B_{n+1}2^{V(n+1)}}$ where $A_{n+1}, B_{n+1}$ are odd positive integers. This implies that $S(n)\not \in \Bbb N$ for $n\geq 2$ because $n\geq 2\implies V(n)\geq 1.$

The proof requires some care. Split it into 2 cases:(i). When $n+1$ is a power of $2.$ (That is , $n+1=2^{V(n+1)}),$ and (ii). When $n+1$ is not a power of $2.$

Related Solutions

[Math] Prove that every integer $n\geq 7$ can be expressed as a sum of distinct primes.

We shall inductively prove a stronger form, namely that every positive integer $n \ge 7$ can be written as the sum of distinct primes such that the largest is at most $\max(11,n-7)$. It turns out that strengthening makes the induction work!

Take $n \ge 28$.

Let $m = \lceil \frac{n-6}{2} \rceil= \lfloor\frac{n-5}{2} \rfloor$.

Let $p$ be a prime such that $m+1 \le p \le 2m-1$ [by Bertrand's postulate].

Then $\frac{n-5}{2} \le p \le n-7$.

By the induction to be established $n-p$ can be written as a sum of distinct primes such that the largest is at most $\max(11,n-p-7)$, which is less than $p$ because $p \ge \frac{28-5}{2} > 11$ and $2p \ge n-5 > n-7$.

Thus $n$ can be written as a sum of distinct primes such that the largest is at most $\max(7,n-7)$, and the induction holds as long as the claim is true for every $n$ from $7$ to $27$.

7 = 5+2
8 = 5+3
9 = 7+2
10 = 5+3+2
11 = 11
12 = 7+5
13 = 11+2
14 = 7+5+2
15 = 7+5+3
16 = 11+5
17 = 7+5+3+2
18 = 11+7
19 = 11+5+3
20 = 11+7+2
21 = 11+7+3
22 = 13+7+2
23 = 13+7+3
24 = 13+11
25 = 13+7+5
26 = 13+11+2
27 = 13+11+3

Elementary Number Theory – Prime Between n and n^2 Without Bertrand’s Postulate

I have stumbled upon this paper due to Erdős, which in the course of proving something far more general proves this result (see a remark at the end of this page). I am replicating that proof here, with minor modifications by myself.

Suppose $n>8$ and that there are no primes between $n,n^2$. Since clearly (obvious induction works) $\pi(n)\leq\frac{1}{2}n$, by assumption we have $\pi(n^2)=\pi(n)\leq\frac{1}{2}n$. Now consider number $\binom{n^2}{n}$. All of its prime factors are less than $n^2$, and so less than $n$. We have the following inequality:

$$\binom{n^2}{n}=\frac{n^2}{n}\frac{n^2-1}{n-1}\dots\frac{n^2-n+2}{2}\frac{n^2-n+1}{1}>\frac{n^2}{n}\frac{n^2}{n}\dots\frac{n^2}{n}\frac{n^2}{n}=\left(\frac{n^2}{n}\right)^n=n^n$$

At the same time, consider $p$ prime and let $p^a$ be the greatest power of $p$ less than or equal to $n^2$. Since $\binom{n^2}{n}=\frac{(n^2)!}{(n^2-n)!n!}$, By Legendre's formula, exponent of the greatest power of $p$ dividing this binomial coefficient is equal to

$$\left(\lfloor\frac{n^2}{p}\rfloor-\lfloor\frac{n^2-n}{p}\rfloor-\lfloor\frac{n}{p}\rfloor\right)+\left(\lfloor\frac{n^2}{p^2}\rfloor-\lfloor\frac{n^2-n}{p^2}\rfloor-\lfloor\frac{n}{p^2}\rfloor\right)+\dots+\left(\lfloor\frac{n^2}{p^a}\rfloor-\lfloor\frac{n^2-n}{p^a}\rfloor-\lfloor\frac{n}{p^a}\rfloor\right)\leq 1+1+\dots+1=a$$

(first equality is true, because all further terms in the sum are zero. First inequality is true because for any $a,b\in\Bbb R$ $\lfloor a+b\rfloor-\lfloor a\rfloor-\lfloor b\rfloor\in\{0,1\}$)

Since $\binom{n^2}{n}$ is a product of at most $\pi(n)$ prime powers, all at most $p^a\leq n^2$ (by above), we must have

$$\binom{n^2}{n}\leq (n^2)^{\pi(n)}\leq (n^2)^{\frac{1}{2}n}=n^n$$

We have proved two contradictory inequalities, so this ends the proof by contradiction.

Best Answer

Related Solutions

[Math] Prove that every integer $n\geq 7$ can be expressed as a sum of distinct primes.

Elementary Number Theory – Prime Between n and n^2 Without Bertrand’s Postulate

Related Question