Numbers not Expressible as Sum of Distinct Pentagonal Numbers

From ProofWiki
Jump to navigation Jump to search

Theorem

The positive integer which cannot be expressed as the sum of distinct pentagonal numbers are:

$2, 3, 4, 7, 8, 9, 10, 11, 14, 15, 16, 19, 20, 21, 24, 25, 26, 29, 30,$
$31, 32, 33, 37, 38, 42, 43, 44, 45, 46, 49, 50, 54, 55, 59, 60, 61, 65,$
$66, 67, 72, 77, 80, 81, 84, 89, 94, 95, 96, 100, 101, 102, 107, 112, 116,$
$124, 136, 137, 141, 142, 147, 159$


Proof

It will be proved that the largest integer which cannot be expressed as the sum of distinct pentagonal numbers is $159$.

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 pentagonal numbers.


Basis for the induction

We verify the result up to $P_{19} = 532$.

Then we conclude all $n$ with $160 \le n \le 532$ can be expressed as the sum of distinct pentagonal numbers.

So $\map P n$ is true for all $160 \le n \le 532$.

This is the basis for the induction.


Induction Hypothesis

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

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

This is the induction hypothesis.


Induction Step

This is the induction step:


We find the largest integer $i$ such that $P_i < k \le P_{i + 1}$.

We show that $k - P_{i - 4}$ can be expressed as the sum of distinct pentagonal numbers, and the sum does not involve $P_{i - 4}$.

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


Since $k > 160 = P_{19}$, we must have $i \ge 19$.

Hence $k > k - P_{i - 4} \ge P_i - P_{i - 4} = \paren {3 i - 2} + \paren {3 i - 5} + \paren {3 i - 8} + \paren {3 i - 11} \ge 55 + 52 + 49 + 47 = 202 > 160$.

Thus $k - P_{i - 4}$ can be expressed as the sum of distinct pentagonal numbers by Induction Hypothesis.


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

We have:

\(\ds P_{i - 4} - \paren {k - P_{i - 4} }\) \(\ge\) \(\ds 2 P_{i - 4} - P_{i + 1}\) From $k \le P_{i + 1}$
\(\ds \) \(=\) \(\ds 2 \paren {\frac {\paren {i - 4} \paren {3 i - 13} } 2} - \frac {\paren {i + 1} \paren {3 i + 2} } 2\) Closed Form for Pentagonal Numbers
\(\ds \) \(=\) \(\ds \frac 1 2 \paren {6 i^2 - 50 i + 104 - 3 i^2 - 5 i - 2}\)
\(\ds \) \(=\) \(\ds \frac 1 2 \paren {3 i^2 - 55 i + 102}\)
\(\ds \) \(=\) \(\ds \frac 3 2 \paren {i \paren {i - \frac {55} 3} + 34}\)
\(\ds \) \(\ge\) \(\ds \frac 3 2 \paren {34}\) From $i \ge 19$
\(\ds \) \(=\) \(\ds 51\)
\(\ds \) \(>\) \(\ds 0\)

Therefore we have $P_{i - 4} > k - P_{i - 4}$.


Hence $\map P k$ is true.


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

Thus every integer greater than $159$ can be expressed as the sum of distinct pentagonal 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_Expressible_as_Sum_of_Distinct_Pentagonal_Numbers&oldid=465416"