Another Short Problem

I was looking at other competitions that I would consider doing in college, and I found out about the International Mathematics Competition for University Students. (http://www.imc-math.org/). I could enter as part of a university team (provided I get chosen for said team), or, failing that, I could go as an individual student. My curiosity piqued, I looked at the problems for the previous year of the competition, available here: http://www.imc-math.org.uk/imc2012/IMC2012-day1-questions.pdf

The first question was pretty trivial, and I got it immediately, I decided to post it here, and then go to bed. (This was a good way to make me feel a bit better about myself after my lack of success with the Putnam questions).


For every positive integer n, let p(n) denote the number of ways to express
n as a sum of positive integers. For instance, p(4) = 5 because
4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1.
Also define p(0) = 1.
Prove that p(n) − p(n − 1) is the number of ways to express n as a sum of integers
each of which is strictly greater than 1.

This means that we have to prove that there are p(n-1) ways to express n as a sum of positive integers, with the restriction that you must include a 1 in the sum.

However, this is obviously true, as take such a sum, and subtract the 1. The remaining integers sum to n-1, and can be anything. And there are precisely p(n-1) ways to get a sum of n-1. So we are done.

The rest of the problems from this contest actually seem really cool, so I will do more of them in the future.