### Notes
For constants $$n,k$$, the number of non-negative integer solutions to $$\sum_{i=1}^n x_i = k$$ is $$\binom{k+n-1}{k}$$
Sum rule: add up sizes of disjoint sets to get size of union
Bijection rule: you can count a set by counting a different set of the same size
Subset/combination rule: the number of ways to choose k out of n items is $$\binom{n}{k}=\frac{n!}{k!(n-k)!}$$
3+x2+x3...+xn=k is equivalent to x2+x3...+xn=k-3
### Demo 2
Let $$n \ge 2$$ and $$k \ge 3$$. Count the number of non-negative integer solutions to $$\sum_{i=1}^n x_i = k$$ where $$x_1 \le 3$$.
### Alternate Solution
The set of *all* non-negative integer solutions (not just ones where $$x_1 \le 3$$) can be split into disjoint subsets where:
1. $$x_1\le 3$$ (these are the solutions we are trying to count)
1. $$x_1> 3$$ (these are "invalid" solutions)
The total number of solutions is $$\binom{k+n-1}{k}$$.
To count the number of invalid solutions, consider a new variable $$x_*=x_1-4$$. Then the invalid solutions $$x_1+x_2+...+x_n=k$$ correspond exactly to the non-negative solutions of $$x_*+x_2+...+x_n=k-4$$. By the notes, there are $$\binom{(k-4)+n-1}{k-4}=\binom{k+n-5}{k-4}$$ such solutions.
By the sum rule, the number of valid solutions is $$\binom{k+n-1}{k}-\binom{k+n-5}{k-4}$$.
### Solution
The set of solutions can be split into disjoint subsets where:
1. $$x_1 = 3$$
1. $$x_1 = 2$$
1. $$x_1 = 1$$
1. $$x_1 = 0$$
The solutions where $$x_1=3$$ are precisely the solutions where the remaining $$n-1$$ variables sum to $$k-3$$. By the notes, there are $$\binom{(k-3)+(n-1)-1}{k-3}=\binom{k+n-5}{k-3}$$ such solutions.
By the same reasoning, the remaining cases have $$\binom{k+n-4}{k-2},\binom{k+n-3}{k-1},\binom{k+n-2}{k}$$ solutions.
Finally, the total number of solutions is (by the Sum rule) $$\binom{k+n-5}{k-3}+\binom{k+n-4}{k-2}+\binom{k+n-3}{k-1}+\binom{k+n-2}{k}$$.