Number Theory

1: Bounds for the p-adic Valuation of n!

Problem Statement: Prove that for every prime $p$ and any integer $n \geq 1$ we have:

Proof: By Legendre's formula, the $p$-adic valuation of $n!$ (the exponent of the highest power of $p$ that divides $n!$) is given by:

Upper Bound: We can bound the sum from above by dropping the floor function:

Evaluating this infinite geometric series, we get:

Thus, $v_p(n!) \leq \frac{n}{p-1}$.

Lower Bound: To find the lower bound, we observe that the sum is strictly greater than or equal to its first term (since all subsequent terms are non-negative):

Knowing the property of the floor function that $\lfloor x \rfloor > x - 1$, we have:

Conclusion: Combining both bounds, we obtain the required inequality:

$\blacksquare$

2: Bounds for Central Binomial Coefficients

Problem Statement: Prove that for every integer $n \geq 1$, we have:

and

Proof:

Part 1: Bounding $\binom{2n}{n}$ We start by recalling the Binomial Theorem:

Substituting $a=1$, $b=1$, and $m=2n$, we get:

Expanding this using the sum, we have exactly $2n+1$ terms:

Since $n \geq 1$, there are multiple positive terms in this sum. Therefore, the entire sum is strictly greater than its largest single term, which is the central binomial coefficient $\binom{2n}{n}$:

Furthermore, since $\binom{2n}{n}$ is the maximum term among all $2n+1$ terms, replacing every term in the sum with $\binom{2n}{n}$ gives an upper bound on the total sum:

Dividing by $2n+1$, we obtain the lower bound:

Combining these results, we get our first set of inequalities:

Part 2: Bounding $\binom{2n+1}{n}$ Now consider the expansion of $(1+1)^{2n+1}$:

Expanding this as a sum:

From the symmetry of binomial coefficients, we know $\binom{m}{k} = \binom{m}{m-k}$. Thus, the two central terms are equal:

Writing out the full sum, we get:

Because $n \geq 1$, there are strictly positive terms on the outside of the two central terms. Therefore, the sum of all terms is strictly greater than the sum of just the two middle terms:

Since these two middle terms are equal, we can substitute:

Dividing both sides by 2, we obtain the final inequality:

$\blacksquare$

3: Bounding the Product of Primes

Problem Statement: Prove that for every integer $n \geq 2$, the product of all primes not exceeding $n$ is less than $4^{n-1}$.

Proof: We will prove this using strong induction on $n$.

Base Case: For $n=2$, the only prime not exceeding $2$ is $2$ itself.

The base case holds.

Inductive Step: Assume the inequality holds for all integers $k$ such that $2 \leq k < n$. We consider two cases for $n$:

Case 1: $n$ is even. If $n$ is even and $n > 2$, $n$ cannot be prime. Therefore, the product of primes up to $n$ is exactly the same as the product of primes up to $n-1$:

By our strong induction hypothesis, since $n-1 < n$, we have:

Thus, the inequality holds when $n$ is even.

Case 2: $n$ is odd. Let $n = 2m+1$ for some integer $m \geq 1$. We can split the product of primes into two parts:

By the induction hypothesis, the first part is bounded by:

For the second part, consider the binomial coefficient from Exercise 2:

Any prime $p$ strictly greater than $m+1$ and less than or equal to $2m+1$ will divide the numerator $(2m+1)!$, but it is too large to divide any term in the denominator $m!(m+1)!$. Therefore, the product of all such primes must divide $\binom{2m+1}{m}$. This gives us the inequality:

From the previous exercise, we already established that $\binom{2m+1}{m} < 4^m$. Therefore:

Combining the bounds for both parts of our product:

Since $n = 2m+1$, we know that $2m = n-1$. Substituting this back in yields:

Conclusion: By the principle of strong induction, the inequality holds for all integers $n \geq 2$.

$\blacksquare$