# How many positive integer solutions are there to $x_1+x_2+x_3+x_4<100?$

How many positive integer solutions are there to $x_1+x_2+x_3+x_4<100?$

I know how to approach the problem if it were How many positive integer solutions are there to $x_1+x_2+x_3+x_4=100$, it would be

${n-1 \choose k-1} = {100-1 \choose 4-1} = {99 \choose 3} = 156,849$

But the fact that it's now including all solutions $<100$ is throwing me off. How would I solve this?

Sum the analogous solutions from $4$ to $99$, for instance. You get $$\sum_{k=3}^{98}\binom k3=\binom{99}{4}.$$
• Also how did you make the jump to ${99 \choose 4}$ – Jodo1992 Mar 13 '16 at 1:58
• It'a a well-known formula on binomial coefficients: $$\sum_{j=k}^n\binom jk=\binom{n+1}{k+1}$$ which is a generalisation of Pascal's formula . – Bernard Mar 13 '16 at 2:08
• Oh! I didn't know that existed. Thank you! One more thing though, I still don't see why you are using $n = 98$ when I'm looking for the sums up to $99$. Could you explain this? – Jodo1992 Mar 13 '16 at 2:11
• The number of solutions to $x_1+x_2+x_3+x_4=99$ is $\dbinom{98}3$. – Bernard Mar 13 '16 at 2:20
For this, you have to introduce a dummy variable say $x_5 > 0$ such that the sum becomes equal to $100$. Then find the number of integral solutions , i.e. when: $x_1 +x_2+ x_3+x_4+x_5=100$ which is nothing but ${99 \choose 4}$