Discrete Mathematics
Show that the number of distinct sequences of positive integers which add up to n is exactly 2n. Note that we do not place any restrictions on the length of the sequence, just that each term is a positive integer and the total sum of all terms is n. Hint: how many choices are there for the first term in such a sequence, and once it is made, what must be true about the sum of the remaining terms? Derive a recursive formula and then prove inductively.