Letc(n)be the number of ways of writingnas a sum, where order matters. So we have

3 = 3, 3 = 1 + 2, 3 = 2 + 1, 3 = 1 + 1 + 1

thusc(3) = 4.

According to the author it is "easily verified" that

Could someone please tell me how to easily verify this, because I have no idea!