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 2^{n – 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 2^{n – 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.)