# Number of solutions to summation

1. Mar 12, 2009

### praharmitra

What is the general formula for a1 + a2 + a3 + .... + an = A, where all the variables a_i and A are non-negative integers.

2. Mar 12, 2009

### qntty

There isn't an easier way to add numbers than to add them, unless the numbers are special in some way (eg, part of a arithmetic/geometric series)

3. Mar 13, 2009

### praharmitra

ahhhh... sorry, completely scrwed up the question. I meant,

What is the general formula for the Number Of Solutions Tn to a1 + a2 + a3 + ... + an = k, where all variables are non-negative integers?

:P, sorry for the mistake.

However, I have a solution, but I am convinced that i had read an easier formula somewhere.

This is my argument

1. a = k, with only one variable, has only one solution. So T1 = 1

2. a + b = k, has k + 1 solutions, as a can take any value from 0 to k, and the corresponding b will be fixed. T2 = k + 1

$$T_{2} = \sum_{k ' = 0} ^k 1$$

3. a + b + c = k

a + b can take any value from 0 to k, and corresponding c will be fixed. Suppose a + b = k'. Then from the above argument no. 2, no. of solutions are k' + 1. Thus to get total no. of solutions of a+b+c = k, we must sum k' over all possible k's

$$T_{3} = \sum_{k' = 0} ^k (k' + 1)$$

$$= T_{3} = \sum_{k'' = 0} ^k \sum_{k' = 0} ^{k''} 1$$

4. for a+b+c+d = k, we can divide it into a+b+c = k', then into a+b = k'', and solve it similarly like above.

Thus in general we'll have n-1 such summations over variables k', k'', k''' etc..., i.e

$$T_{n} = \sum_{k^{n-1} = 0} ^k \sum_{k^{n-2} = 0} ^{k^{n-1}}............ \sum_{k'' = 0} ^{k'''} \sum_{k' = 0} ^{k^{''}} 1$$

However, I am sure I have read an easier formula somewhere. Could someone list that down?

4. Mar 13, 2009

### yyat

Last edited by a moderator: Apr 24, 2017