Prove that any positive integer can be written as sum of distinct numbers from $1,2,3,4,5,10,20,\ldots$

Question

The sequence $1,2,3,4,5,10,20,40,\ldots$ starts as an arithmetic series, but after the first five terms, it becomes a geometric series. The problem is to prove by induction that any positive integer can be written as a sum of distinct numbers from this sequence.

I came up with the following solution, but I'm not satisfied. I'd like some help to better formalize my proof and also identify potential flaws.

Proof. Fix a positive integer $n$. Suppose that every positive integer $k < n$ can be written as a sum of distinct numbers from $s=(1,2,3,4,5,10,20,40,\ldots)$. We prove that this claim holds for $n$. There are two cases:

• If $0 < n < 6$, then the result follows by the definition of $s$.
• If $n \geq 6$, then, by the induction hypothesis, we know that $n - 5 > 0$ can be written as a sum of distinct numbers from $s$. By adding 5 to $n - 5$, two things can happen: either 5 is already a term in the sum or it is not. If it is not, then we are done. Otherwise, add the two 5's to get a 10. If 10 is already a term in the sum, add the two 10's, and so on. By repeating this process, we guarantee that the terms in the sum are distinct and that we are only adding multiple of 5, which are always present in $s$.

QED

The way I wrote the last case is, of course, quite informal. In addition, it feels to me that there is another proof by induction lurking in the last case, but I was not able to formalize it properly. Could you help me improve this proof? (And if there are any flaws, please do point them out.)

Answer 1

This may be an alternative to your induction step, for $n \ge 6$:

If $n\in s$, then that's a way to represent $n$ as a sum of one term.

Otherwise, pick the largest number $k\in s$ that satisfies $k < n < 2k$. By the induction hypothesis, $n-k$ can be represented as a sum that doesn't contain $k$. (Because $0< n-k < k$)

---

These two cases can be further merged, by adding the $n=0$ case to the base cases and to the induction hypothesis.

The induction step only requires having some $k\in s$ such that $k\le n < 2k$, i.e. the next larger element after $k$ should be at most $2k$, regardless of whether $2k\in s$. So for example, this proof still works by skipping one of $3$ or $4$ in the sequence $s$.

Answer 2

You might get the desired induction by noticing that after the first four entries, every number in the sequence is $5\cdot 2^n$ for non-negative integer $n$. So you might prove that if every positive integer less than $5\cdot 2^n$ can be represented, then every positive integer less than $5\cdot 2^{n+1}$ can be represented. The base case would be $5\cdot 2^0.$

Answer 3

I didn't see anything wrong with your approach, although it did seem off the beaten track. Personally, I would construct a proof by induction that parallels the proof by induction that any number can be written in binary format.

This is because, once you eliminate the least non-negative residue, $\pmod{5},~$ and then divide by $~5,~$ you are (in effect) working with binary digits.

So, I will construct a proof by induction that all positive integers can be expressed in binary. Then, I will alter it to apply to your problem.

For $~n \in \Bbb{Z^+}, ~$ define the set $~S_n~$ to denote
$~\{ ~x \in \Bbb{Z_{\geq 0}} ~: ~x < 2^n ~\}.$

I want to prove that for all $~n \in \Bbb{Z^+},~$ that every element of $S_n$ can be written in binary.

Clearly $~0~$ and $~1~$ can be written in binary.
Therefore, the assertion is true for $~n = 1.$
Assume that the assertion is true for $~n = N.$

Clearly, each element in $~S_N~$ will be written with no more than $~N~$ binary digits.

Therefore, the assertion must then be true for $~S_{N+1},~$ because each of the elements in $~S_{N+1}\backslash S_N,~$ can be expressed by taking one of the elements in $~S_N,~$ and (in effect) adding $~1 \times 2^N~$ to it.

This means that the elements in $~S_{N+1} \backslash S_N,~$ are expressed in binary by taking the corresponding element in $~S_N~$ and adding a $1$ in the position that represents $~2^N.$

Therefore, if the assertion is true for $~S_N,~$ then the assertion is true for $~S_{N+1}.$

---

Now, I will refine the previous argument, so that it applies to your problem.

Let the set $~T~$ denote $\{0,1,2,3,4\}.$

Let $~U~$ denote the infinite set $\{0,1,2,3,4,5,10,20,40,\cdots\}.$

Since every element in $~T~$ is in $~U~$, each element in $~T~$ has a satisfactory expression.

To Prove
Each positive integer $~n~$ can be expressed as the sum of selected elements in $~U\backslash \{0\},~$ where each element in $~U\backslash \{0\},~$ can only appear once in the sum.

Since $~T\backslash \{0\} ~\subseteq ~U \backslash\{0\},$ each element in $~T\backslash \{0\}~$ has a satisfactory expression. Further, for positive integers $~> 4,~$ it is sufficient to show that there is a satisfactory expression by taking the elements from $~U,~$ rather than $~U\backslash\{0\}.$

This is because if the positive integer is $~> 4,$ and if the expressed sum of terms contains the term $~0,~$ then that term can be omitted from the expression without altering the sum.

For example, since $~0 + 5 + 10 = 15,$ you also have that $5 + 10 = 15.$

---

For each $~n ~\in \Bbb{Z^+},$
let $~A_n~$ denote the set $\{ ~n \in \Bbb{Z_{\geq 0}} ~: ~\left\lfloor ~\dfrac{n}{5} ~\right\rfloor < 2^n ~\}.$

For example:

• $A_1 = \{0,1,2,3,4,5,6,7,8,9\}.$

• $A_2 = \{0,1,2,3,\cdots,19\}.$

• $A_3 = \{0,1,2,3,\cdots,39\}.$

• $~\cdots~$

From the previous discussion, it is sufficient to prove that for all $~n \in \Bbb{Z^+},~$ there is a satisfactory expression for each element in $~A_n,~$ where the elements in the sum are taken from the set $~U.$

This is clearly true for $~n=1,~$ since each element in $~A_1,~$ has such a satisfactory expression.

Suppose that the assertion is true for $~n = N.$ This means that each element in $~A_N~$ has a satisfactory expression, and that the largest element being used from $~U~$ for any such expression must be $~< 5 \times 2^N.$

Now consider the elements in $~A_{N+1} \backslash A_N.$ Clearly, for each such element $~r,~$ there is an element $~s \in A_n~$ such that $~r - s = 5 \times 2^N.$

This implies that the expression for $~r~$ can be constructed by taking the expression for $~s~$ and adding the term $~5 \times 2^N.$

This implies that each element in $~A_{N+1}~$ has such a satisfactory expression.

Therefore, if the assertion is true for $~n = N,~$ then the assertion must also be true for $~n = N+1.$