Solve $x_1+x_2+x_3+...+x_6<10$ if $x_i $ are non -negative integers

Question

So I've got to solve $x_1+x_2+...+x_6<10$, if $x_i$ are non-negative integers. In class, we learned to do it as such: Since $(x_1+x_2+..+x_6)$ is a positive quantity there must be a positive integer $x_7$ such as $(x_1+x_2+..+x_6) + x_7 = 10$ . Then, we say that this equation is equivalent to this equation : $y_1+ y_2+..+y_6+y_7=9$ where $y_i \mapsto x_i for i to [0,6]$ and $y_7=x_7-1$ . My question is about the mapping of $y_7$ . Did we choose it to be $y_7=x_7-1$ because we know for sure that x7 must be at least 1? So we said, $x_7 - 1>=0 \rightarrow y_7 \mapsto x_7-1$? If for example we put that $y_7 = x_7-2$ and we solve the equation $y_1+ y_2+..+y_6+y_7=8$ shouldn't we get the same result? I am trying to figure out for sure , which is the the technique behind those mappings.

Answer 1

You set $y_7 = x_7 - 1$ because we know that $x_7 \ge 1$; we don't know $x_7 \ge 2$ so setting $y_7 = x_7 - 2$ will miss the solutions in which $x_7 = 1$.

To put it differently: because $x_1, \dots, x_6$ are integers, their sum is an integer, so we can go from $$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 < 10$$ to $$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 \le 9$$ to $$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 = 9$$ where everything is a nonnegative integer.

Answer 2

There is another technique to solve this problem:

Consider the following $\ \ \displaystyle x_1 + x_2 + x_3 + x_4 + x_5 + x_6 \leq 9.$

As $\ \ \displaystyle \{x_1 , x_2 , x_3 , x_4 , x_5 , x_6\} \in \mathbb {Z}^{\geq 0}$.

Now for general solution of $\ \ \displaystyle x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = n \ \ $ is given by $\ \ \displaystyle \binom {n+5}{5} \ \ $. (This can be easily seen through stars and bars method.)

Hence we need to evaluate $$\ \ \displaystyle \sum_{n = 0}^{9}\binom {n+5}{5} = \binom {15}{6} = 5005\ \ $$

Answer 3

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ By $\ds{\underline{definition}}$, the answer is given by $\ds{\sum_{x_{1} = 0}^{\infty}\cdots\sum_{x_{6} = 0}^{\infty} \bracks{x_{1} + \cdots + x_{6} < 10}}$ which is equivalent to evaluate the contribution $\ds{\sum_{x_{1} = 0}^{\infty}\cdots\sum_{x_{6} = 0}^{\infty} \bracks{x_{1} + \cdots + x_{6} = s}}$ for a given sum $\ds{s = 0,1,2,\ldots,9}$ and add all those contributions to the final answer. Namely, $$ \sum_{s = 0}^{9}\braces{\sum_{x_{1} = 0}^{\infty}\cdots \sum_{x_{6} = 0}^{\infty}\bracks{x_{1} + \cdots + x_{6} = s}} $$

---

With $\ds{\bracks{x_{1} + \cdots + x_{6} = s} = \bracks{z^{s}}z^{x_{1} + \cdots + x_{6}}}$, \begin{align} &\bbox[5px,#ffd]{\sum_{x_{1} = 0}^{\infty}\cdots\sum_{x_{6} = 0}^{\infty} \bracks{x_{1} + \cdots + x_{6} < 10}} = \sum_{s = 0}^{9}\sum_{x_{1} = 0}^{\infty}\cdots\sum_{x_{6} = 0}^{\infty} \bracks{z^{s}}z^{x_{1} + \cdots + x_{6}} \\[5mm] = &\ \sum_{s = 0}^{9}\bracks{z^{s}}\pars{\sum_{x = 0}^{\infty}z^{x}}^{6} = \bracks{z^{0}}\sum_{s = 0}^{9}{1 \over z^{s}} \pars{1 \over 1 - z}^{6} \\[5mm] = &\ \bracks{z^{0}}{1/z^{10} - 1 \over 1/z - 1}\,\pars{1 - z}^{-6} = \bracks{z^{0}}\pars{1 - z}^{-6}\pars{{1 \over z^{9}}\, {1 - z^{10} \over 1 - z}} \\[5mm] = & \bracks{z^{9}}\pars{1 - z}^{-7} = {-7 \choose 9}\pars{-1}^{9} = {15 \choose 9} = \bbx{\large 5005} \\ & \end{align}