In 1951, Arthur B. Brown of Queens College noted that the number 3 can be expressed as the sum of one or more positive integers in four ways (taking the order of terms into account):
3
1 + 2
2 + 1
1 + 1 + 1
As it turns out, any positive integer n can be so expressed in 2n – 1 ways. Brown asked, how can this be proved?
William Moser of the University of Toronto offered this insightful solution:
Imagine the digit 1 written n times in a row. For example, if n = 4:
1 1 1 1
This is a picket fence, with n pickets and n – 1 spaces between them. At each space we can choose either to insert a plus sign or leave it blank. So that gives us n – 1 tasks to perform (i.e., making this choice for each space) and two options for each choice. Thus the total number of expressions for n as a sum is 2n – 1, or, in the case of n = 4, eight:
1 1 1 1 = 4
1 + 1 1 1 = 1 + 3
1 1 + 1 1 = 2 + 2
1 1 1 + 1 = 3 + 1
1 + 1 + 1 1 = 1 + 1 + 2
1 + 1 1 + 1 = 1 + 2 + 1
1 1 + 1 + 1 = 2 + 1 + 1
1 + 1 + 1 + 1 = 1 + 1 + 1 + 1
(Pi Mu Epsilon Journal 1:5 [November 1951], 186.)