Waste less time on Facebook — follow Brilliant.

Need help for the proofs about number theory.

Note: \(p_{n}\) is the n-th prime number (\(p_{1} = 2, p_{2} = 3, p_{3} = 5\), etc).

1.) Prove that \(p_{n+1} < \sum\limits_{i=1}^{n} p_{i} \) for any integer \(n > 2\).

2.) Prove that \(\sum\limits_{i=1}^{n} p_{i} < \prod\limits_{i=1}^{n} p_{i}\) for any integer \(n > 1\).

3.) Prove or counterexample that \(\sqrt{n!} \notin \mathbb{N}\) for any integer \(n > 1\).

Note by Samuraiwarm Tsunayoshi
4 years ago

No vote yet
1 vote

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 \( 2 \times 3 \)
2^{34} \( 2^{34} \)
a_{i-1} \( a_{i-1} \)
\frac{2}{3} \( \frac{2}{3} \)
\sqrt{2} \( \sqrt{2} \)
\sum_{i=1}^3 \( \sum_{i=1}^3 \)
\sin \theta \( \sin \theta \)
\boxed{123} \( \boxed{123} \)


Sort by:

Top Newest

Bertrand's Postulate

Rajeh Alghamdi - 4 years ago

Log in to reply

You can have a one-liner inductive proof of Problem 1) using Bertrand's postulate, which is a well known proven result in number theory.

The base case for \(n=3\) is easy. Assume the assertion to hold good for an integer \(n\geq 3\). Using this postulate, we have \(p_{n+1} < p_{n+2} < 2 p_{n+1}= p_{n+1}+ p_{n+1} < \sum_{i=1}^{n+1}p_i\), where the last inequality follows from the induction assumption.

Abhishek Sinha - 4 years ago

Log in to reply

I agree with your q3 solution, it is very common in questions like these to use Bertrand's Postulate. In a moment I will post a very nice problem indeed. q2 is very susceptible to induction (just simple induction, maybe with a contradiction element if you want to simplify things). q1 is a very nice problem, as it combines techniques used in both q2 and q3 (use induction, with a contradiction, then use Bertrand's Postulate), so I thank you for these series of problems. If you want to know the problem I previously mentioned, just visit my page.

TheKnee OfJustice - 4 years ago

Log in to reply

I just proved number 3 in 3 seconds lol. Just Bertrand's Postulate that there exists a prime number from \(\frac{n}{2}\) to \(n\) if \(n\) is even or from \(\frac{n-1}{2}\) to \(n-1\) if \(n\) is odd.

For even number \(n\), if \(p > \frac{n}{2}\), then \(2p > n\). Which means the next number that has a factor \(p\) doesn't exist in \(n,n-1,n-2,...,3,2,1\) any more. So \(n!\) only have 1 factor of \(p\) and makes it not perfect square.

For odd number \(n\), if \(p > \frac{n-1}{2}\), then \(2p > n-1\). Same as above, there exists only 1 factor \(p\).

How about \(n\)? Can \(n\) have a factor of \(p\)? No. If \(2p = n\), then \(n\) is an odd number, which contradicts the given. So \(2p > n\) or \(2p < n\).

For \(2p > n\), we're done. \(2p\) doesn't exist in \(n,n-1,n-2,...,3,2,1\) any more.

For \(2p < n\), since \(2p > n-1\), therefore \(2p\) can't be integers, which contradicts the truth.

Therefore, \(\sqrt{n!}\) can't be integers for any \(n > 1\).

Log in to reply


Problem Loading...

Note Loading...

Set Loading...