Proof by induction of number of solutions to $m$-tuples with non-negative integers that add to a non-negative integer $n$

Asked Dec 01 '22 at 15:23

Active Dec 01 '22 at 15:23

Viewed 29 times

I have the following problem

Prove by induction that there are $S(m,n) = \binom{n+m-1}{m-1}$ solutions to: $$\sum_{i=1}^m x_i = n$$ where $m \geq 1$, each $x_i$ is a non-negative integer as is $n$.

Clearly, the base case $S(1,0)$ is the number of solutions to $x_i = 0$ which is $1$, and the formula verifies this. I started by inducting on $m$, and considered $\sum_{i=1}^{m+1} x_i = n$. If $x_{m+1} = 0$, there are clearly $S(m,n)$ solutions. This is where I don't know how to proceed, what is the argument if $x_{m+1}>0$?

I am familiar with the usual stars-and-bars method, but I would like to prove it this way instead.

asked Dec 01 '22 at 15:23

senri

4

Does this answer your question? proof by induction, the number of ways of grouping unlabelled objects - found using an Approach0 search. Note this answer there states ... – John Omielan Dec 01 '22 at 20:14
(cont.) "The problem is equivalent to finding the number of solutions of equation $a_1 + a_2 + a_3 + ... + a_m = n$ where $a_i >= 0$ for all i." Also, a closely related post is Cardinality of partitions of a number. – John Omielan Dec 01 '22 at 20:17

Proof by induction of number of solutions to $m$-tuples with non-negative integers that add to a non-negative integer $n$

0 Answers0