# Numbers not Sum of Distinct Squares

## 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$

## 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.