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


This needs considerable tedious hard slog to complete it.
In particular: a) Demonstration that these cannot be so expressed, b) demonstration that all others below 324 can be so expressed
To discuss this page in more detail, feel free to use the talk page.
When this work has been completed, you may remove this instance of {{Finish}} from the code.
If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.


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:

\(\ds \paren {i - 4}^2 - \paren {k - \paren {i - 4}^2 }\) \(\ge\) \(\ds 2 \paren {i - 4}^2 - \paren {i + 1}^2\) From $k \le T_{i + 1}$
\(\ds \) \(=\) \(\ds 2 i^2 - 16 i + 32 - i^2 - 2 i - 1\)
\(\ds \) \(=\) \(\ds i^2 - 18 i + 31\)
\(\ds \) \(=\) \(\ds i \paren {i - 18} + 31\)
\(\ds \) \(\ge\) \(\ds 31\) From $i \ge 18$
\(\ds \) \(>\) \(\ds 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.


This article needs proofreading.
Please check it for mathematical errors.
If you believe there are none, please remove {{Proofread}} from the code.
To discuss this page in more detail, feel free to use the talk page.
When this work has been completed, you may remove this instance of {{Proofread}} from the code.



Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Numbers_not_Sum_of_Distinct_Squares&oldid=468955"