Dgdrxrt

The problem:

Find the number of solutions to the equation: $x_1+x_2+...+x_n=k$ when $0leq x_ileq m$ and $m+1leq kleq 2m+1$.

The answer in the book is $n+k-1choose k-nchoose 1n+k-(m+1)-1choose k-(m+1)$.

I understand that the idea is taking all solutions, a number equals to $n+k-1choose k$ and then subtracting "bad" solutions, and that $nchoose 1$ is there because we can't have more than a single $i$ so $x_igeq 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 tag1$$
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
$$binomk + n - 1n - 1 = binomk + n - 1k$$
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
beginalign*
x_1' + m + 1 + x_2 + ldots + x_n & = k\
x_1' + x_2 + ldots + x_n & = k - (m + 1) tag2
endalign*
Equation 2 is an equation in the nonnegative integers with
$$binomk - (m + 1) + n - 1n - 1 = binomk - (m + 1) + n - 1k - (m + 1)$$
solutions. Hence, there are
$$binomn1binomk - (m + 1) + n - 1n - 1 = binomn1binomk - (m + 1) + n - 1k - (m + 1)$$
solutions in which one of the variables exceeds $m$.

Thus, there are
$$binomk + n - 1k - binomn1binomk - (m + 1) + n - 1k - (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
beginalign*
m + 1 + x_2 + ldots + x_n & = k\
x_2 + ldots + x_n & = k - (m + 1)
endalign*
which is an equation in the nonnegative integers with
$$binomk - (m + 1) + (n - 1) - 1(n - 1) - 1 = binomk - (m + 1) + (n - 1) - 1k - (m + 1)$$
solutions, which is a smaller number as we would expect.