How many different ways can you write the number 6 as the sum if natural numbers? with proof.

you just neeed to organise your results in such a way that its impossible you missed any
possibilities with:
six 1's is max ones
five 1's
four 1's
three 1's
two 1's
one 1
number of 2's with zero 1's max is three
number of 3's with zero 1's and zero 2's
there are no results with a 4 or a 5 without a 1 or a 2
there is one result with a six.
no result with any higher number
by
0 doesn't count, right?

Let's call N(x) the number of ways to write x

* N(1) = 1
* trivial case
* N(2) = 1 + N(1)
* the 2 itself
* sum a 1, then add 1
* = N(1) + N(1) = 2·N(1)
* N(3) = 1 + N(1) + N(2)
* the 3 itself
* sum a 1, then add 2
* sum a 2, then add 1
* = N(2)+N(2) = 2·N(2)
* N(4) = 1 + N(1) + N(2) + N(3)
* the 4 itself
* sum a 1, then add 3
* sum a 2, then add 2
* sum a 3, then add 1
* = N(3)+N(3) = 2·N(3)
* N(5) = 1 + N(1) + N(2) + N(3) + N(4)
* the 5 itself
* sum a 1, then add 4
* sum a 2, then add 3
* sum a 3, then add 2
* sum a 4, then add 1
* = N(4)+N(4) = 2·N(4)
* etc.

So N(x) = 2·N(x-1), or N(x) = 2^(x-1)

It's not a proof but maybe it'll help

0 like 0 dislike