# Thread: Inductive Proof: Multinomial Theorem

1. ## Inductive Proof: Multinomial Theorem

I've spent a lot of time on the multinomial theorem and I'm still having a bit of trouble with it. I fully understand the theorem, what it yields and why, but I don't grasp the inner workings of the inductive proof. Is there anyone out there that could give a complete narrative to the proof of the multinomial theorem on wikipedia.org? Multinomial theorem - Wikipedia, the free encyclopedia

Thank you!

2. Originally Posted by tcRom
I've spent a lot of time on the multinomial theorem and I'm still having a bit of trouble with it. I fully understand the theorem, what it yields and why, but I don't grasp the inner workings of the inductive proof. Is there anyone out there that could give a complete narrative to the proof of the multinomial theorem on wikipedia.org? Multinomial theorem - Wikipedia, the free encyclopedia

Thank you!
wikipedia proof is a mess and it's not even complete because the base of induction is assumed to be m = 1, which is incorrect! the base of induction is actually m = 2, because

in reducing the case m + 1 to m we use "binomial theorem". (of course, for completeness we can mention the trivial case m = 1, but that cannot be considered as the base!)

before getting into the proof, we first need a very simple fact:

$\displaystyle \boxed{1} \ .$ suppose $\displaystyle 0 \leq k, j_1, \cdots, j_m \leq n$ and $\displaystyle j_1 + \cdots + j_m=k.$ then: $\displaystyle \binom{n}{k} \binom{k}{j_1, \cdots, j_m}=\binom{n}{j_1, \cdots , j_m, n-k}.$

Proof: by definition: $\displaystyle \binom{n}{k} \binom{k}{j_1, \cdots, j_m}=\frac{n!}{k!(n-k)!} \times \frac{k!}{j_1! \cdots j_m!}=\frac{n!}{j_1! \cdots j_m! (n-k)!}$

$\displaystyle =\binom{n}{j_1 \cdots , j_m, n-k}.$ note that since $\displaystyle j_1 + \cdots + j_m=k,$ we have: $\displaystyle j_1 + \cdots + j_m + n-k= n. \ \ \ \square$

now we can prove the multinomial theorem by induction over m assuming that we know binomial theorem. suppose $\displaystyle m \geq 2$ and multinomial theorem is true for m. for m + 1 we have:

$\displaystyle (x_1 + \cdots + x_m + x_{m+1})^n=\sum_{0 \leq k \leq n} \binom{n}{k}x_{m+1}^{n-k}(x_1 + \cdots + x_m)^k \ \ \ \ \text{binomial theorem}$

$\displaystyle =\sum_{0 \leq k \leq n} \binom{n}{k} x_{m+1}^{n-k} \sum_{0 \leq j_1, \cdots, j_m \leq k, \ j_1 + \cdots j_m = k} \binom{k}{j_1, \cdots, j_m} x_1^{j_1} \cdots x_m^{j_m} \ \ \ \text{induction hypothesis}$

$\displaystyle =\sum_{0 \leq k \leq n, \ 0 \leq j_1, \cdots, j_m \leq k, \ j_1 + \cdots j_m = k} \binom{n}{j_1, \cdots, j_m,n-k} x_1^{j_1} \cdots x_m^{j_m} x_{m+1}^{n-k}. \ \ \ \ \ \text{using} \ \ \boxed{1}$

now in the above put $\displaystyle n-k=j_{m+1},$ then since $\displaystyle 0 \leq k \leq n,$ we'll have $\displaystyle 0 \leq j_{m+1} \leq n.$ also since $\displaystyle j_1 + \cdots + j_m = k,$ we'll have $\displaystyle j_1 + \cdots + j_m + j_{m+1}=n.$ finally $\displaystyle 0 \leq j_1, \cdots , j_m \leq k$

becomes $\displaystyle 0 \leq j_1, \cdots , j_m \leq n - j_{m+1},$ which is equivalent to $\displaystyle 0 \leq j_1, \cdots, j_m, j_{m+1} \leq n,$ because $\displaystyle j_1+ \cdots + j_m + j_{m+1}=n.$ therefore the above sum is equal to:

$\displaystyle \sum_{0 \leq j_1, \cdots, j_{m+1} \leq n, \ j_1 + \cdots + j_{m+1} = n} \binom{n}{j_1, \cdots , j_{m+1}} x_1^{j_1} \cdots x_{m+1}^{j_{m+1}}. \ \ \ \ \square$

3. Originally Posted by NonCommAlg
(...we can mention the trivial case m = 1, but that cannot be considered as the base!)
To verify... This is because using m = 1 yields a single term to the nth power and is useless for what we're doing. Da?

Originally Posted by NonCommAlg
$\displaystyle =\binom{n}{j_1 \cdots , j_m, n-k}.$ note that since $\displaystyle j_1 + \cdots + j_m=k,$ we have: $\displaystyle j_1 + \cdots + j_m + n-k= n. \ \ \ \square$
How is it that $\displaystyle j_1 + \cdots + j_m + n-k= n$ and $\displaystyle j_1 + \cdots + j_m=k$? I get lost on this part and continue to have trouble with it later on; and I know it's basic, which makes me want to cry cause I don't get it !

Originally Posted by NonCommAlg
now in the above put $\displaystyle n-k=j_{m+1},$ ... also since $\displaystyle j_1 + \cdots + j_m = k,$ we'll have $\displaystyle j_1 + \cdots + j_m + j_{m+1}=n$...
Here's the later on. I fail to see where these come from.

I really appreciate the great help that you've been. It seems like no matter how much time I put into this stuff, I still have so much more to go (I can't imagine how Bernoulli et al. felt about it)... It's a good thing I enjoy math

Thank you NonCommAlg!