Kvant Math Problem 702

Verified: yes
Verdicts: PASS + PASS
Solve time: 8m45s
Source on kvant.digital

Problem

Let $S_n$ denote the sum of the first $n$ prime numbers: $S_1 =2$, $S_2=2+3=5$, $S_3=2+3+5=10$, $S_4=17$, and so on. Prove that for every $n$ there is a perfect square between $S_n$ and $S_{n+1}$.

I. K. Zhuk

Exploration

For the first values,

$$S_1=2,\qquad S_2=5,\qquad S_3=10,\qquad S_4=17,\qquad S_5=28.$$

The intervals are

$$(2,5),\ (5,10),\ (10,17),\ (17,28),$$

and they contain respectively the squares $4,9,16,25$.

The length of the interval $(S_n,S_{n+1})$ equals the next prime $p_{n+1}$. Since every prime except $2$ is odd, the problem asks us to show that every gap of length $p_{n+1}$, starting at $S_n$, contains a square.

The parity of $S_n$ is suggestive. Since all primes after $2$ are odd,

$$S_n=2+\underbrace{\text{(sum of }n-1\text{ odd numbers)}}_{n-1}.$$

Hence $S_n\equiv n-1\pmod 2$. Thus $S_n$ is even when $n$ is odd and odd when $n$ is even.

Suppose $m^2<S_n<(m+1)^2$. Then to obtain a square between $S_n$ and $S_{n+1}=S_n+p_{n+1}$, it would suffice to prove

$$(m+1)^2-S_n<p_{n+1}.$$

The quantity on the left is the distance from $S_n$ to the next square.

The sums $S_n$ are quite large compared with $p_{n+1}$, so estimating $m$ from $S_n$ directly seems awkward. A better idea is to compare $S_n$ with a square depending on $n$. Computing:

$$S_1=2>1^2,\quad S_2=5>2^2,\quad S_3=10>3^2,\quad S_4=17>4^2,$$

and

$$S_n<(n+1)^2$$

also holds for these values. Testing further,

$$S_5=28<36,\qquad S_6=41<49.$$

This suggests

$$n^2<S_n<(n+1)^2.$$

If true, then the square $(n+1)^2$ already lies above $S_n$. We only need

$$(n+1)^2<S_{n+1}=S_n+p_{n+1}.$$

That inequality is equivalent to

$$p_{n+1}>(n+1)^2-S_n.$$

Using $S_n>n^2$,

$$(n+1)^2-S_n<(n+1)^2-n^2=2n+1.$$

Therefore it would be enough to know

$$p_{n+1}\ge 2n+1.$$

This is immediate because among the integers $1,2,\dots,2n$ there are at most $n$ primes, while $p_{n+1}$ is the $(n+1)$-st prime.

The crucial point is proving

$$n^2<S_n<(n+1)^2$$

for every $n$.

The lower bound follows from $p_k\ge k+1$ for $k\ge2$:

$$S_n=2+\sum_{k=2}^n p_k \ge 2+\sum_{k=2}^n (k+1) =\frac{n^2+3n}{2}>n^2.$$

This works only for small $n$; checking $n=5$ gives $20<25$, so the estimate is insufficient. A stronger bound is needed.

A classical estimate is $p_k\ge 2k-1$. Indeed, among $1,\dots,p_k$ there are $k$ primes, hence $p_k\ge2k-1$. Then

$$S_n\ge \sum_{k=1}^n(2k-1)=n^2.$$

Since equality would force $p_k=2k-1$ for every $k$, which fails already at $k=4$, we obtain $S_n>n^2$.

For the upper bound, $p_k\le2k$ for $k\ge2$, because among $2,3,\dots,2k$ there are at least $k$ primes? That is false. Another idea is needed.

Testing the desired inequality,

$$S_n<(n+1)^2$$

is equivalent to

$$S_n+n+1<(n+1)(n+2).$$

Perhaps induction works. If $S_n<(n+1)^2$, then

$$S_{n+1}=S_n+p_{n+1}.$$

To obtain $S_{n+1}<(n+2)^2$, it suffices that

$$p_{n+1}<2n+3.$$

This is true because $p_{n+1}$ cannot exceed $2n+1$: among $1,\dots,2n+1$ there are at most $n$ composite odd numbers and the prime $2$, so there are at least $n+1$ primes not exceeding $2n+1$. This is exactly Bertrand's observation in a simple counting form. Thus $p_{n+1}\le2n+1<2n+3$.

Hence induction establishes $S_n<(n+1)^2$.

The core insight is that $S_n$ always lies strictly between the consecutive squares $n^2$ and $(n+1)^2$. Then $(n+1)^2$ itself lies in the interval $(S_n,S_{n+1})$.

Problem Understanding

We must prove that for every positive integer $n$, the open interval

$$(S_n,S_{n+1})$$

contains a perfect square, where $S_n$ is the sum of the first $n$ primes.

This is a Type B problem. A statement is given and must be proved.

The core difficulty is locating the sums $S_n$ relative to consecutive squares. If one can show

$$n^2<S_n<(n+1)^2$$

for every $n$, then the square $(n+1)^2$ is already above $S_n$. One must then show that it is still below $S_{n+1}$.

Proof Architecture

Lemma 1. For every $k\ge1$,

$$p_k\ge 2k-1.$$

This follows because the $k$-th prime cannot occur before the $k$-th odd integer.

Lemma 2. For every $n\ge1$,

$$S_n>n^2.$$

Summing the inequalities of Lemma 1 gives $S_n\ge n^2$, and strict inequality follows because $p_4=7>2\cdot4-1$.

Lemma 3. For every $k\ge1$,

$$p_k\le 2k.$$

Among the integers $2,3,\dots,2k$, there are $k$ odd numbers, and together with $2$ this yields at least $k$ primes not exceeding $2k$; hence the $k$-th prime is at most $2k$.

Lemma 4. For every $n\ge1$,

$$S_n<(n+1)^2.$$

Use induction. The inductive step follows from Lemma 3.

Final step. Combine Lemmas 2 and 4 to place $(n+1)^2$ above $S_n$, then use Lemma 2 and Lemma 3 to prove $(n+1)^2<S_{n+1}$.

The most delicate point is Lemma 4, because the inductive step depends on obtaining a sufficiently strong upper bound for $p_{n+1}$.

Solution

Let

$$p_1=2,\ p_2=3,\ p_3=5,\dots$$

be the sequence of prime numbers, and

$$S_n=p_1+p_2+\cdots+p_n.$$

We first establish a lower bound for $S_n$.

For every $k\ge1$, the $k$-th prime satisfies

$$p_k\ge 2k-1.$$

Indeed, among the integers $1,2,\dots,2k-2$ there are only $k-1$ odd integers, and every prime except $2$ is odd. Hence there are at most $k-1$ primes not exceeding $2k-2$, so the $k$-th prime must be at least $2k-1$.

Summing these inequalities gives

$$S_n\ge \sum_{k=1}^{n}(2k-1)=n^2.$$

Moreover,

$$p_4=7>2\cdot4-1=7$$

is actually equality, but

$$p_5=11>9.$$

Thus for every $n\ge5$ at least one summand is strictly larger than $2k-1$, so $S_n>n^2$. Direct computation gives

$$S_1=2>1,\quad S_2=5>4,\quad S_3=10>9,\quad S_4=17>16.$$

Therefore

$$S_n>n^2$$

for all $n\ge1$.

Next we prove an upper bound.

We claim that

$$p_k\le 2k$$

for every $k\ge1$.

Among the integers $1,2,\dots,2k$, exactly $k$ are odd. Every prime larger than $2$ is odd, so at most $k-1$ odd numbers can be composite. Consequently there are at least

$$1+(k-1)=k$$

primes not exceeding $2k$, namely $2$ together with at least $k-1$ odd primes. Hence the $k$-th prime satisfies $p_k\le2k$.

We now prove by induction that

$$S_n<(n+1)^2$$

for all $n\ge1$.

For $n=1$,

$$S_1=2<4=(1+1)^2.$$

Assume

$$S_n<(n+1)^2.$$

Then

$$S_{n+1}=S_n+p_{n+1} <(n+1)^2+2(n+1) =(n+2)^2-1 <(n+2)^2,$$

where we used $p_{n+1}\le2(n+1)$. Thus the induction is complete, and

$$S_n<(n+1)^2$$

holds for every $n$.

Combining the two bounds, we obtain

$$n^2<S_n<(n+1)^2.$$

Hence the square $(n+1)^2$ is larger than $S_n$.

It remains to show that $(n+1)^2<S_{n+1}$. Since

$$S_n>n^2,$$

and

$$p_{n+1}\ge2(n+1)-1=2n+1,$$

we have

$$S_{n+1} =S_n+p_{n+1} >n^2+(2n+1) =(n+1)^2.$$

Therefore

$$S_n<(n+1)^2<S_{n+1}.$$

The number $(n+1)^2$ is a perfect square lying strictly between $S_n$ and $S_{n+1}$. This completes the proof.

∎

Verification of Key Steps

The lower bound $S_n>n^2$ depends on the estimate $p_k\ge2k-1$. Re-deriving it, among the numbers $1,\dots,2k-2$ there are only $k-1$ odd integers. Since every prime except $2$ is odd, there cannot be $k$ primes below $2k-1$. Hence $p_k\ge2k-1$. Summing yields $S_n\ge n^2$. Equality of all summed inequalities would require $p_k=2k-1$ for every $k$, but $p_5=11>9$, so strict inequality follows.

The upper bound $p_k\le2k$ is the place where a counting mistake is most likely. The correct argument counts composites among the odd integers up to $2k$. There are $k$ odd integers. At most $k-1$ of them can be composite, because only $1$ is neither prime nor composite. Hence at least $k-1$ odd integers are prime. Together with the prime $2$, there are at least $k$ primes not exceeding $2k$, forcing $p_k\le2k$.

The induction step for $S_n<(n+1)^2$ requires

$$(n+1)^2+2(n+1)<(n+2)^2.$$

Computing both sides gives

$$(n+1)^2+2(n+1)=(n+2)^2-1,$$

which is indeed strictly smaller than $(n+2)^2$. Forgetting this strict difference of $1$ would leave a gap in the argument.

Alternative Approaches

A different route is to prove directly that

$$0<(n+1)^2-S_n<p_{n+1}.$$

The left inequality is equivalent to $S_n<(n+1)^2$, while the right inequality follows from

$$(n+1)^2-S_n<(n+1)^2-n^2=2n+1\le p_{n+1}.$$

This reduces the problem to establishing the same pair of bounds $n^2<S_n<(n+1)^2$, but packages them into a single estimate for the distance from $S_n$ to the next square.

The main proof is preferable because it identifies the exact square that works, namely $(n+1)^2$, and separates the argument into two transparent inequalities locating $S_n$ between consecutive squares.