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
2 years, 7 months ago

No vote yet
1 vote


Sort by:

Top Newest

Bertrand's Postulate Rajeh Alghamdi · 2 years, 7 months 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 · 2 years, 7 months 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 · 2 years, 7 months 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\). Samuraiwarm Tsunayoshi · 2 years, 7 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...