# Numbers not Expressible as Sum of Distinct Pentagonal Numbers

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