Numbers not Sum of Distinct Squares

From ProofWiki
Jump to navigation Jump to search

Theorem

The positive integers which are not the sum of $1$ or more distinct squares are:

$2, 3, 6, 7, 8, 11, 12, 15, 18, 19, 22, 23, 24, 27, 28, 31, 32, 33, 43, 44, 47, 48, 60, 67, 72, 76, 92, 96, 108, 112, 128$

This sequence is A001422 in the On-Line Encyclopedia of Integer Sequences (N. J. A. Sloane (Ed.), 2008).


Proof


It will be proved that the largest integer which cannot be expressed as the sum of distinct squares is $128$.

The remaining integers in the sequence can be identified by inspection.


We prove this using a variant of Second Principle of Mathematical Induction.


Let $\map P n$ be the proposition:

$n$ can be expressed as the sum of distinct squares.


Basis for the induction

We verify the result up to $18^2 = 324$.

Then we conclude all $n$ with $129 \le n \le 324$ can be expressed as the sum of distinct squares.

So $\map P n$ is true for all $129 \le n \le 324$.

This is the basis for the induction.


Induction Hypothesis

Suppose for some $k > 324$, $\map P j$ is true for all $129 \le j < k$.

That is, every integer between $129$ and $k - 1$ can be expressed as the sum of distinct squares.

This is the induction hypothesis.


Induction Step

This is the induction step:


We find the largest integer $i$ such that $i^2 < k \le \paren {i + 1}^2$.

We show that $k - \paren {i - 4}^2$ can be expressed as the sum of distinct squares, and the sum does not involve $\paren {i - 4}^2$.

Then $k$ can be expressed as the sum of distinct squares.


Since $k > 324 = 18^2$, we must have $i \ge 18$.

Hence $k > k - \paren {i - 4}^2 > i^2 - \paren {i - 4}^2 = 4 \paren {2 i - 4} \ge 4 \times 32 = 128$.

Thus $k - \paren {i - 4}^2$ can be expressed as the sum of distinct squares by Induction Hypothesis.


A sufficient condition such that the sum does not involve $\paren {i - 4}^2$ is $\paren {i - 4}^2 > k - \paren {i - 4}^2$.

We have:

\(\displaystyle \paren {i - 4}^2 - \paren {k - \paren {i - 4}^2 }\) \(\ge\) \(\displaystyle 2 \paren {i - 4}^2 - \paren {i + 1}^2\) From $k \le T_{i + 1}$
\(\displaystyle \) \(=\) \(\displaystyle 2 i^2 - 16 i + 32 - i^2 - 2 i - 1\)
\(\displaystyle \) \(=\) \(\displaystyle i^2 - 18 i + 31\)
\(\displaystyle \) \(=\) \(\displaystyle i \paren {i - 18} + 31\)
\(\displaystyle \) \(\ge\) \(\displaystyle 31\) From $i \ge 18$
\(\displaystyle \) \(>\) \(\displaystyle 0\)

Therefore we have $\paren {i - 4}^2 > k - \paren {i - 4}^2$.


Hence $\map P k$ is true.


By the Second Principle of Mathematical Induction, $\map P n$ is true for all $n \ge 128$.

Thus every integer greater than $128$ can be expressed as the sum of distinct square numbers.


Sources