Number of integral solutions for $x_1 + x_2 - x_3 = n$ where $n \geq x_1 , x_2 , x_3 \geq 0$

Question

I have been asked

Integral solutions for $x_1 + x_2 - x_3 = n$ where $n \geq x_1 , x_2 , x_3 \geq 0$.

My approach:

We have, $0 \leq x_3\leq n$
$\Rightarrow n \leq x_1 + x_2 \leq 2n$

Further, by assuming some integer $t$, for which $x_1+x_2+t = n$, we can find the number of integers for $x_1$ and $x_2$ which should take care of the corresponding values of $x_3$.

However, when I solve by taking the case of $n = 20$, my answer does not match with the given, 651.

My book solution:

Number of solution $= \binom{n+1}{1} + \binom{n+2}{1}+\binom{n+3}{1} + \ldots + \binom{2n+1}{1} = \dfrac{(n+1)(3n+2)}{2}$

Any help would be appreciated

Answer 1

Your approach is correct (though: 1) you should have described it more explicitly, and 2) I am reluctant to name $t$ your negative integer: better $-i$), and your book is wrong, because it forgot the conditions $x_2,x_3\le n$.

The number of solutions is $$\sum_{i=0}^n\left|\{(x_1,x_2)\in\Bbb Z^2\mid 0\le x_1,x_2\le n\text{ and }x_1+x_2=n+i\}\right|$$ $$=\sum_{i=0}^n\left|\{x_1\in\Bbb Z\mid 0\le x_1,n+i-x_1\le n\}\right|$$ $$=\sum_{i=0}^n\left|\{x_1\in\Bbb Z\mid i\le x_1\le n\}\right|$$ $$=\sum_{i=0}^n(n-i+1)$$ $$=\sum_{k=1}^{n+1}k$$ $$=\frac{(n+1)(n+2)}2.$$

Answer 2

Here is another approach. Let $x'_3=n-x_3$. When you take $x_1+x_2-x_3=n$, and substitute $x_3\gets n-x_3'$, the result is $$ x_1+x_2+x_3'=2n $$ Furthermore, it is easy to see that as $x_3$ ranges over $\{0,1,\dots,n\}$, so does $x_3'$. Therefore, we want to count solutions to the above where $0\le x_1,x_2,x_3'\le n$. This is a special case of Extended stars-and-bars problem(where the upper limit of the variable is bounded). Using the methods there, we get an answer of $$ \binom{2n+2}2-3\cdot \binom{2n-(n+1)+2}{2} =\frac{(2n+2)(2n+1)}2-3\cdot\frac{(n+1)n}{2} \\\hspace{3.5cm}=\frac{(n+2)(n+1)}{2}. $$ The book's answer of $(n+1)(3n+2)/2$ is wrong.