Representing integers as a sum
A quick selection from Proof and the Art of Mathematics
Let us investigate how many ways we can represent a given number as a sum.
This is a quick excerpt from chapter 5 of my book Proof and the Art of Mathematics, an introduction to the art and craft of proof-writing for aspiring mathematicians who want to learn how to write proofs.
Proof and the Art of Mathematics has been awarded the 2024 Daniel Solow Author’s Award by the Mathematical Association of America, awarded for outstanding and impactful contributions to mathematics education.
Theorem. Every positive integer n can be expressed as a sum of one or more positive integers in precisely 2n-1 many ways.
For example, the number 4 can be expressed in the following eight ways:
For the purpose of this theorem, we allow the sum to have only one term, if desired, or many terms, and we pay attention to the order of the summands, but we do not use parentheses or pay attention to associativity.
Proof: Place n ones down in a row, like a picket fence:
There are n − 1 spaces between the ones. For each such space, let us imagine placing either a + sign in it or leaving it empty, in all the various possible ways to do this. Since there are n − 1 spaces and two choices for each space, there are precisely 2n-1 many different ways to place these signs. Each such placement gives rise to a distinct way to represent n as a sum, if we interpret each contiguous block of ones as a single summand, so that
for example, represents 1 + 3 + 2. And conversely, every representation of n as a sum corresponds to such a marking. So there are 2n-1 ways to represent n as a sum. □
A fence-post error is a common kind of mathematical error conflating fence posts with the spaces between them, such as in a list of numbers, an array, or an interval of time, and arises because there is one fewer space between the fence posts than there are fence posts. For example, if you arrive at a hotel on Sunday and leave the following Saturday, then you were present at the hotel on all seven days of the week, but you stayed only six nights. There are five integers from 8 to 12, even though these numbers differ by only four. If you were president of the club from the beginning of 2014 to the end of 2016, then you were president for three years: 2014, 2015, and 2016.
In exercise 11, the reader will give an alternative proof of theorem 1 by induction.
Selection from chapter’s end:
Exercises
11. Give an alternative proof of the theorem by induction. [Hint: Consider how to generate representations of n + 1 from representations of n.]
I encourage readers of Infinitely More to post their solution to the exercise in the comments.
I did it in terms of partial sums. For example the sum
1 + 2 + 5 + 2
corresponds to the partial sums 1, 3, 8, 10.
The largest partial sum is always n. The other partial sums can be any subset of {1, 2, ..., n-1}. Hence there are 2^(n-1) possible sums.