1
$\begingroup$

Forgive poor formatting, I don't know how to use mathjax very well. I am a 10th grade student with little experience writing proofs looking for constructive criticism.

I found this problem in the book Solving Mathematical Problems by Terrence Tao. In the book it says that Bertrand's Postulate (for every $n$, where $n$ is an element of $Z^+$, there exists a prime $p$, such that $n<p<2n$) is required to prove it, but--interested--I tried to see if it can be proved in a more elementary manner. I believe I have found one and wish to have it verified and critiqued. I shall proceed:

Theorem. For every $n, q$, where $n$ and $q$ are elements of $Z^+$, $2<=n$, it is true that $1/1+1/2+...+1/n$ does not equal $q$. (Could someone please tell me how to use summation notation in mathjax, thanks).

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:

$2$ x $3$ x ... x $n+1$ x $3$ x ... x $n+ ...+1$ x $2$ x ... x $n-1 /n!$

Assuming this is equal to an inteqer, $q$, then:

$n!q = 2$ x $3$ x ... x $n+1$ x $3$ x ... x $n+ ...+1$ x $2$ x ... x $n-1$

$2(n!/2)q = 2$ x $3$ x ... x $n+1$ x $3$ x ... x $n+ ...+1$ x $2$ x ... x $n-1$ ($n$ is greater than $2$, therefore $n!$ is divisible by $2$).

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 $nth$ harmonic number equals $q$, as desired.

$QED.$

$\endgroup$
  • $\begingroup$ You can find mathjax tutorial here: math.meta.stackexchange.com/questions/5020/… $\endgroup$ – Aniruddha Deshmukh Nov 12 '18 at 4:35
  • $\begingroup$ You can also have that $1 \times 2 \times \cdots \times \left( n - 1 \right) = n!q - \left( \sum\limits_{i = 1}^{n - 1} \prod\limits_{j = 1 \\ j \neq i}^n j \right)$ and hence $n | 1 \times 2 \times \cdots \times \left( n - 1 \right)$ which is a contradiction. Usually, for proving something by contradiction, we do not counter examples. Rather, we use a strong fallacy that arises due to our assumption which we then call "contradiction". $\endgroup$ – Aniruddha Deshmukh Nov 12 '18 at 4:41
  • 5
    $\begingroup$ You are just showing, Riley, that for $n=3$ you don't get an integer. What meant to be done is to show that no matter what $n$ is, you don't get an integer. And this can be done without Bertrand, by considering the highest power of two involved. See math.stackexchange.com/questions/2746/… $\endgroup$ – Gerry Myerson Nov 12 '18 at 4:43
  • $\begingroup$ It is useful to consider the number of factors of $2$ in $\operatorname{lcm}(1,2,3,\ldots,n)$ and note that there is only one number in $1,2,3,\ldots,n$ that has that number of factors of $2$. $\endgroup$ – robjohn Nov 12 '18 at 7:34
  • $\begingroup$ Thank you for all your comments, and critiques. I understand the errors I have made now and hope to learn from them by considering your critiques. Also, the ord$2$ proof is really cool thanks for showing me it. $\endgroup$ – Riley Culloty Nov 12 '18 at 11:09
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ "Bertrand's Postulate" is actually a theorem, first proven in the early 19th century. I dk if it has any bearing on this Q $\endgroup$ – DanielWainfleet Nov 13 '18 at 3:34
  • $\begingroup$ Thank you, your answer was very in depth. I unfortunately can't upvote because my reputation is too low. I will have a go at proving that. $\endgroup$ – Riley Culloty Nov 13 '18 at 4:27
  • $\begingroup$ I once looked at the highest power of $3$ that divides the denominator of $S(n)$ when $S(n)$ is in lowest terms and found that for some $n$, it is less than the highest power of $3$ not exceeding $n$. With powers of $2$ it is just an even/odd issue but for powers of $3$ it gets complicated. $\endgroup$ – DanielWainfleet Nov 13 '18 at 8:17
  • 1
    $\begingroup$ You may not be able to upvote, Riley, but you are able to "accept" the answer by clicking in the check mark next to it, if you are satisfied with the answer. $\endgroup$ – Gerry Myerson Nov 13 '18 at 10:10

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.