Give a combinatorial proof for
$${n\choose k} = {n+k-1\choose k} - \sum_{j=1}^{n}(-1)^{j+1}{n\choose j}{n+k-(2j+1)\choose k}$$
For hint, we can denote $A_i$ denote the set of distributions of stars to kids such that kid i gets at least 2 stars.
My approach
LHS is the count for giving k stars to n students.
RHS is ...??? (looks like intersection principle, but I'm no sure)
Thank you!!!
Method 1: Inclusion-exclusion
There are two ways of viewing distributions of $k$ stars to $n$ students. The first is simply to distribute $k$ stars, $1$ per student:
$$\begin{array}{c|c|c|c|c|c|c|c|}\text{student}&1&2&3&\cdots &n-2&n-1&n\\\hline \text{distribution}&\star &&\star &\cdots &\star &\star &\end{array}$$
and there are $\binom{n}{k}$ ways to do this.
The other way to view distributions is by using the separating bars as a second set of identical objects, the above distribution looks like this:
$$\begin{array}{c|c|c|c|c|c|}\star &&\star &\cdots &\star &\star \end{array}$$
Now, there are clearly $n+k-1$ objects here: $k$ stars and $n-1$ bars. That means there are $\binom{n+k-1}{k}$ arrangements of these. But many of those will have several stars between two bars or on ends, thus representing distributions not counted by $\binom{n}{k}$.
What we need to do is count arrangements of stars and bars so that there is no more than $1$ star between any two bars or on ends.
We call set $A_i$ the set of the arrangements where student $i$ has more than $1$ star. It is clear that:
$$S_1=|A_i|=\binom{n+k-2-1}{k-2}$$
because, if student $i$ has at least $2$ stars there are $k-2$ remaining to arrange with the $n-1$ bars.
Similarly for the set of arrangements where students $i_1$ and $i_2$ both have at least 2 stars each:
$$S_2=|A_{i_1}\cap A_{i_2}|=\binom{n+k-2(2)-1}{k-2(2)}$$
and in general for $j$ students each having at least two stars:
$$S_j=|A_{i_1}\cap\cdots \cap A_{i_j}|=\binom{n+k-2j-1}{k-2j}$$
So, using the principle of inclusion-exclusion, the size of the set containing none of the elements of $A_{1}\cup\cdots \cup A_{n}$ is:
$$|(A_{1}\cup\cdots \cup A_{n})'|=\sum_{j=0}^{n}(-1)^j\binom{n}{j}S_j$$
which is $\binom{n}{k}$.
Here $S_0=\binom{n+k-1}{k}$ is the size of the set of all arrangements of $n-1$ bars and $k$ stars.
So we have, finally:
$$|(A_{1}\cup\cdots \cup A_{n})'|=\sum_{j\ge 0}(-1)^j\binom{n}{j}\binom{n+k-2j-1}{k-2j}=\binom{n}{k}$$
which is not quite what you have in the question but checks out nonetheless.
The upper limit on $j$ in the summation is taken care of by defining $\binom{a}{b}=0$ for $b\gt a$ and for $b\lt 0$.
Method 2:Generating Functions
The generating function for distributing $k$ stars to $n$ students with each student getting at most $1$ star is $(1+x)^n$ since each of the $n$ students may successively receive a star ('$x$') or not ('$1$'). Thus the $x^k$ coefficient is:
$$\binom{n}{k}=[x^k](1+x)^n$$
Alternatively, since $1+x$ is a finite geometric series it can be written:
$$1+x=\frac{1-x^2}{1-x}$$
so that:
$$\begin{align}(1+x)^n&=\left(\frac{1-x^2}{1-x}\right)^n\\[2ex]&=(1-x^2)^n(1-x)^{-n}\\[2ex]&=\left(\sum_{j=0}^{n}(-1)^j\binom{n}{j}x^{2j}\right)\left(\sum_{k\ge 0}\binom{n+k}{k}x^k\right)\\[2ex]&=\sum_{k\ge 0}\left(\sum_{j\ge 0}(-1)^j\binom{n}{j}\binom{n+k-2j-1}{k-2j}\right)x^k\end{align}$$
then we also have:
$$[x^k](1+x)^n=\sum_{j\ge 0}(-1)^j\binom{n}{j}\binom{n+k-2j-1}{k-2j}$$
hence, again:
$$\binom{n}{k}=\sum_{j\ge 0}(-1)^j\binom{n}{j}\binom{n+k-2j-1}{k-2j}$$