1
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

Sum the analogous solutions from $4$ to $99$, for instance. You get $$\sum_{k=3}^{98}\binom k3=\binom{99}{4}.$$

$\endgroup$
  • $\begingroup$ If you wanted the sum from 4 to 99 then why on your summation do you have from k = 3 to 98? $\endgroup$ – Jodo1992 Mar 13 '16 at 1:57
  • $\begingroup$ Also how did you make the jump to ${99 \choose 4}$ $\endgroup$ – Jodo1992 Mar 13 '16 at 1:58
  • 1
    $\begingroup$ 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 . $\endgroup$ – Bernard Mar 13 '16 at 2:08
  • $\begingroup$ 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? $\endgroup$ – Jodo1992 Mar 13 '16 at 2:11
  • $\begingroup$ The number of solutions to $x_1+x_2+x_3+x_4=99$ is $\dbinom{98}3$. $\endgroup$ – Bernard Mar 13 '16 at 2:20
15
$\begingroup$

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}$

$\endgroup$
  • $\begingroup$ simplest and very clever answer.+1 The usual route is to sum binomial coefficients as in Bernard's answer. $\endgroup$ – Paramanand Singh Jul 9 '16 at 9:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.