# How to prove that any natural number $n \geq 34$ can be written as the sum of distinct triangular numbers?

Sloane's A053614 implies that $2, 5, 8, 12, 23$, and $33$ are the only natural numbers $n \geq 1$ which cannot be written as the sum of distinct triangular numbers (i.e., numbers of the form $\binom{k}{2}$, beginning $1,3,6,10,15,\ldots$).

Question: How to prove that any natural number $n \geq 34$ can be written as the sum of distinct triangular numbers?

We have

• $34=\binom{8}{2}+\binom{4}{2}$,
• $35=\binom{8}{2}+\binom{4}{2}+\binom{2}{2}$,
• $36=\binom{9}{2}$,
• $37=\binom{9}{2}+\binom{2}{2}$,
• $38=\binom{8}{2}+\binom{5}{2}$,

and so on.

Sloane's A061208 links to a math olympiad question (page 207) which asks to prove this for $n \leq 1997$, but the given proof is not in English, so I neither understand it, nor can I be sure if it works for all $n$.

• The result is not general, essentially explicitly giving the answer for $n \le 2819$. The final line of the solution refers to Erdős for a general approach. – Sharkos Aug 3 '15 at 8:34
• The approach of Pierre Bornzstein in the linked pdf can't be generalized. He just examines all the cases. It starts with the smallest integers and uses the previous decomposition to get the following ones. – user37238 Aug 3 '15 at 8:54

This follows from a theorem of Richert:

Theorem Suppose that $k \ge 2, N \ge 0, M \ge0$ satisfy

• Whenever $N<x \le N + M$, $x$ is a sum of distinct elements of some of the first $k$ elements of a set $S = \{s_1, s_2, \ldots\}$, where $s_1 < s_2 < \cdots$.

• $M \ge s_{k+1}$

• $2 s_i \ge s_{i+1}$

Then every integer greater than $N$ is a sum of distinct elements of $S$.

Take $k=8, N=33, M=45$ to obtain the desired result.

Proof of Theorem To prove the theorem, let $I_p = \{N+1, N+2, \ldots, N + s_{p+1}\}$. Then by assumption, all elements of $I_k$ are the sum of the first $k$ elements $s_1, \ldots, s_k$.

But now observe that if this is true for some general $p$, then $$I_p \cup \{m + s_{p+1} : m \in I_p\}$$ contains $I_{p+1}$, as a consequence of $s_{p+2} \le 2 s_{p+1}$. Hence all elements of $I_{p+1}$ are sums of the $s_1, \ldots, s_{p+1}$.

Hence inductively the result follows by considering $\bigcup_{p\ge k} I_k$, which contains all integers larger than $N$, and contains only elements which are distinct sums of $s_i$.

• Can you explain in your theorem what is the sequence $(s_n)_{n\in \mathbb{N}}$? – user37238 Aug 3 '15 at 8:55
• Done! Thanks for catching that. I think I've labelled the indices in the last part correctly now too. Let me know if I haven't! – Sharkos Aug 3 '15 at 8:56
• Interestingly, the same question with primes (so using Bertrand's postulate) popped up today as well, I think – Hagen von Eitzen Aug 3 '15 at 9:02