KGS math club/solution pairing

Proof. Proceed by induction on $n$ . The statement is true for $n = 64$ , since the lhs of the inequality evaluates to $4352$ and the rhs evaluates to $4372$ . Now assume the statement is true for $n \geq 64$ and note that $68 \leq 2n + 1$ . Adding this inequality to the induction hypothesis gives

$68n + 68 \leq n^2 + 276 + 2n + 1$

which simplifies to

$68(n + 1) \leq (n + 1)^2 + 276$

and this gives the statement for $n + 1$ .

Claim (4) - Rewriting the main inequality

For each $n \geq 64$ , the inequality $n + 4\sqrt{n + 25} + 29 \leq 2n + 3$ holds.

Proof. Start with the inequality from Claim (3).

$68n \leq n^2 + 276$

Subtract $52n$ from both sides

$16n \leq n^2 - 52n + 276$

Add $400$ to both sides

$16n + 400 \leq n^2 - 52n + 676$

Factor both sides, using the binomial formula for the rhs

$16(n + 25) \leq (n - 26)^2$

Take the square root of both sides

$4\sqrt{n + 25} \leq n - 26$

Finally, adding $n + 29$ to both sides gives the statement.

Claim (5) - Finding odd perfect squares

For each even $n \geq 64$ there is an odd perfect square in the closed interval $[n + 24, 2n - 1]$ .

Proof. Proceed by induction on the even $n$ . The statement is true for $n = 64$ , since

$n + 24 = 88 \leq 11^2 = 121 \leq 127 = 2n - 1$

Now assume that the statement is true for $n$ , that is, there is an odd $k$ with $n + 24 \leq k^2 \leq 2n - 1$ . If $k^2$ is already at least $n + 26$ , then $k^2$ also satisfies the statement for $n + 2$ , since then

$(n + 2) + 24 = n + 26 \leq k^2 \leq 2n - 1 \leq 2n + 3 = 2(n + 2) - 1$

The remaining case $n + 24 \leq k^2 < n + 26$ actually simplifies to

$k^2 = n + 25$

since the case $k^2 = n + 24$ is ruled out, because $n$ is even and $k$ is odd. Add $4k + 4$ to the equation above and obtain

$k^2 + 4k + 4 = n + 4k + 29$

Factoring the lhs and replacing $k$ in the rhs gives

$(k + 2)^2 = n + 4\sqrt{n + 25} + 29$

By Claim (4), this expression is less or equal to $2n + 3$ . Hence, $(k + 2)^2$ is an odd perfect square in the interval $[(n + 2) + 24, 2(n + 2) - 1]$ and this concludes the induction.

The Finish

Using the claims, we prove the Main Statement by induction on the even $n$ .

By the Claims (1) and (2), the Main Statement is true for all $n \leq 62$ .

Now let $n$ be even with $n \geq 64$ . With Claim (5), we find an odd perfect square $k^2$ in the interval $[n + 24, 2n - 1]$ . Let $p = k^2 - n$ and observe

$24 \leq p \leq n - 1$

which implies the stronger inequality

$24 < p \leq n - 1$

since $p$ is odd. By construction of $p$ , $p$ and $n$ sum up to $k^2$ and hence are partners. Furthermore, since $p$ and $n$ are of opposite parity, there is an even number of numbers strictly between them. These numbers may be paired up straightforward in the following way

$(p + 1) + (n - 1) = k^2$ $(p + 2) + (n - 2) = k^2$ $(p + 3) + (n - 3) = k^2$ $\dots$

Hence, in order to complete the pairing for all numbers up to $n$ , it only remains to pair up the numbers up to $p - 1$ . Note that $p - 1$ is even.

If $64 \leq p - 1$ , then apply Claim (5) recursively again, to $p - 1$ instead of $n$ , in order to pair up another portion of the yet unpaired numbers. Eventually, we will reach a scenario where $p - 1 \leq 62$ . By the construction of $p$ we know that $24 \leq p - 1$ . Hence $p - 1$ cannot be one of the exceptional cases and we may apply Claim (2) to find a pairing for all the remaining numbers up to $p - 1$ .

Page

Toolbox

Search

KGS math club/solution pairing

Contents

Main Statement

Preparations

Claim (1) - The exceptional cases

Claim (2) - Pairings for small cases

Claim (3) - The main inequality

Claim (4) - Rewriting the main inequality

Claim (5) - Finding odd perfect squares

The Finish