Q:

Number of solutions to the equation $x_1 + x_2 + \ldots + x_n = k$ when $0 \leq x_i \leq m$ and $m + 1 \leq k \leq 2m + 1$

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:

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.

