In preparation for an upcoming test I have come across the following problem and I am looking for some help with it just in case a question of its kind comes up on a evaluation. Thanks!
How many positive integer solutions satisfy the condition:$$y_1+y_2+y_3+y_4 < 100$$
On
Hint: If $f(n)$ is the number of positive integer solutions to $y_1 + \ldots + y_4 = n$, then $$\sum_{n=4}^\infty f(n) x^n = (x^1 + x^2 + \ldots)^4 = \left(\frac{x}{1-x}\right)^4 $$
On
Add a slack-variable $y_5$ and note that this is the same as the number of solutions to $$ y_1+\dotsb+y_5=100;\quad y_i\geq1 $$ Using stars and bars there are $$ \binom{100-1}{5-1} $$ solutions.
On
Lets say the question was: $$y_1+y_2+y_3+y_4 = 4$$
There is only $1$ solution: $$1+1+1+1 = 4$$
Now lets assume it was: $$y_1+y_2+y_3+y_4 = 5$$
There are $4$ solutions: $$1+1+1+2=5$$ $$1+1+2+1 = 5$$ $$1+2+1+1 = 5$$ $$2+1+1+1 = 5$$
Next assume it was: $$y_1+y_2+y_3+y_4 = 5 $$
There are $10$ solutions: $$1+1+1+3 = 6$$ $$1+1+2+2 = 6$$ $$1+1+3+1 = 6$$ $$1+2+2+1 = 6$$ $$1+2+1+2 = 6$$ $$1+3+1+1 = 6$$ $$2+1+1+2 = 6$$ $$2+1+2+1 = 6$$ $$2+2+1+1 = 6$$ $$3+1+1+1 = 6$$
There's a pattern:
$$n=4 \implies \binom{3}{3} = 1$$ $$n=5 \implies\binom{4}{3} = 4$$ $$n=6 \implies\binom{5}{3} = 10$$ $$n=7 \implies\binom{6}{3} = 20$$ $$n=8 \implies\binom{7}{3} = 35$$
Then by adding up all the terms up to $98$ you get the answer: $$\sum_{i=3}^{98}\binom{i}{3} =\binom{99}{4}= 3764376$$
Indeed by Hockey-stick identity we have
$$\sum^n_{i=r}{i\choose r}={n+1\choose r+1} \qquad \text{ for } n,r\in\mathbb{N}, \quad n>r$$
The problem is equivalent to put 4 separator between the 99 inner intervals between the 100 objects in such way that, for example starting from the left
such that $$y_1+y_2+y_3+y_4<100$$
that is
$$\binom{99}{4}$$