The problem:
Find the number of solutions to the equation: $x_1+x_2+...+x_n=k$ when $0\leq x_i\leq m$ and $m+1\leq k\leq 2m+1$.
The answer in the book is ${n+k-1\choose k}-{n\choose 1}{n+k-(m+1)-1\choose k-(m+1)}$.
I understand that the idea is taking all solutions, a number equals to ${n+k-1\choose k}$ and then subtracting "bad" solutions, and that ${n\choose 1}$ is there because we can't have more than a single $i$ so $x_i\geq m+1$, what I can't understand is the last part. I think it works only if the "bad" element equals exactly $m+1$, but what if it equals $m+2$? That way it doesn't seem correct anymore.
Thanks in advance.
A solution of the equation in the nonnegative integers $$x_1 + x_2 + \ldots + x_n = k \tag{1}$$ corresponds to the placement of $n - 1$ addition signs in a row of $k$ ones. For instance, if $n = 4$ and $k = 10$, $$1 1 + + 1 1 1 1 1 + 1 1 1$$ corresponds to the solution $x_1 = 2$, $x_2 = 0$, $x_3 = 5$, $x_4 = 3$. The number of such solutions is $$\binom{k + n - 1}{n - 1} = \binom{k + n - 1}{k}$$ since we must choose which $n - 1$ of the $k + n - 1$ positions required for $k$ ones and $n - 1$ addition signs will be filled with addition signs or, equivalently, which $k$ of the $k + n - 1$ positions will be filled with ones.
We wish to solve equation 1 in the nonnegative integers not larger than $m$ when $m + 1 \leq k \leq 2m + 1$. Thus, we must subtract those solutions in which a variable exceeds $m$. At most one variable may exceed $m$ since $2(m + 1) = 2m + 2 > 2m + 1$.
We may choose a variable that exceeds $m$ in $n$ ways. Suppose that variable is $x_1$. Then $x_1' = x_1 - (m + 1)$ is a nonnegative integer. Substituting $x_1' + m + 1$ into equation 1 equation yields \begin{align*} x_1' + m + 1 + x_2 + \ldots + x_n & = k\\ x_1' + x_2 + \ldots + x_n & = k - (m + 1) \tag{2} \end{align*} Equation 2 is an equation in the nonnegative integers with $$\binom{k - (m + 1) + n - 1}{n - 1} = \binom{k - (m + 1) + n - 1}{k - (m + 1)}$$ solutions. Hence, there are $$\binom{n}{1}\binom{k - (m + 1) + n - 1}{n - 1} = \binom{n}{1}\binom{k - (m + 1) + n - 1}{k - (m + 1)}$$ solutions in which one of the variables exceeds $m$.
Thus, there are $$\binom{k + n - 1}{k} - \binom{n}{1}\binom{k - (m + 1) + n - 1}{k - (m + 1)}$$ admissible solutions.
Notice that in equation 2, $m + 1 \leq x_1 \leq 2m + 1 \implies 0 \leq x_1' \leq m$. It does not imply that $x_1 = m + 1$.
Let's compare this with what would happen if $x_1 = m + 1$. Then we would have \begin{align*} m + 1 + x_2 + \ldots + x_n & = k\\ x_2 + \ldots + x_n & = k - (m + 1) \end{align*} which is an equation in the nonnegative integers with $$\binom{k - (m + 1) + (n - 1) - 1}{(n - 1) - 1} = \binom{k - (m + 1) + (n - 1) - 1}{k - (m + 1)}$$ solutions, which is a smaller number as we would expect.