Proof of $\sum_{k=n-1}^{n+p-1} {k \choose p}={n+p \choose p}$ using the equation $x_1 + x_2 + \dots + x_n = p$

Question

So we consider the following equation: $$x_1 + x_2 + \dots + x_n = p$$ We dnote the set of solutions (lists of $\{0, \dots ,p \}$) by $A(n,p)$. If we write $p=1+1+\dots+1$ then the problem can be reduced to putting p indistinguishable balls in $n$ ordered containers, or in other words, how many ways there are to arrange the inner $n-1$ walls of our containers and the $p$ digits. Thus $$|A(n,p)|={n+p-1\choose p}$$ I'm trying to use this to prove the equation $$\sum_{k=n-1}^{n+p-1} {k \choose p}={n+p \choose p}$$ The RHS is the cardinality of $A(n+1, p)$, and we can count its elements by looking at the possible values of $x_{n+1}$, this give: $$\sum_{x_{n+1}=0}^{p}|A(n, p-x_{n+1})|=\sum_{x_{n+1}=0}^{p}{n+p-x_{n+1}-1\choose p-x_{n+1}}$$ But my book writes it as: $$\sum_{x_{n+1}=0}^{p}{n+p-x_{n+1}-1\choose p}$$ Where is the error? Thanks in advance.

Answer 1

Your book's equation $$ \sum_{k=n-1}^{n+p-1}\binom{k}{\color{red}p}=\binom{n+p}{p} $$ is incorrect. However, $$ \sum_{k=n-1}^{n+p-1}\binom{k}{\color{#080}{n-1}}=\binom{n+p}p $$ is correct. With this, everything works smoothly: \begin{align} \binom{n+p}{p} &=A(n+1,p) \\&=\sum_{x_{n+1}=0}^p A(n,p-x_{n+1}) \\&=\sum_{x_{n+1}=0}^p \binom{n+(p-x_{n+1})-1}{p-x_{n+1}} \\\\&(\text{reindex summation by }{k=n+p-x_{n+1}-1})\\ \\&=\sum_{k=n-1}^{n+p-1}\binom{k}{k-(n-1)} \\&=\sum_{k=n-1}^{n+p-1}\binom{k}{n-1}. \end{align}