multinomial theorem (proof)

Proof. The below proof of the multinomial theorem uses the binomial theoremMathworldPlanetmath and inductionMathworldPlanetmath on k. In additionPlanetmathPlanetmath, we shall use multi-index notation.

First, for k=1, both sides equal x1n. For the induction step, suppose the multinomial theorem holds for k. Then the binomial theorem and the induction assumptionPlanetmathPlanetmath yield

(x1++xk+xk+1)n = l=0n(nl)(x1++xk)lxk+1n-l
= l=0n(nl)l!|i|=lxii!xk+1n-l
= n!l=0n|i|=lxixk+1n-li!(n-l)!

where x=(x1,,xk) and i is a multi-index in I+k. To completePlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath the proof, we need to show that the sets

A = {(i1,,ik,n-l)I+k+1l=0,,n,|(i1,,ik)|=l},
B = {jI+k+1|j|=n}

are equal. The inclusion AB is clear since


For BA, suppose j=(j1,,jk+1)I+k+1, and |j|=n. Let l=|(j1,,jk)|. Then l=n-jk+1, so jk+1=n-l for some l=0,,n. It follows that that A=B.

Let us define y=(x1,,xk+1) and let j=(j1,,jk+1) be a multi-index in I+k+1. Then

(x1++xk+1)n = n!|j|=nx(j1,,jk)xk+1jk+1(j1,,jk)!jk+1!
= n!|j|=nyjj!.

This completes the proof.

Title multinomial theorem (proof)
Canonical name MultinomialTheoremproof
Date of creation 2013-03-22 13:41:55
Last modified on 2013-03-22 13:41:55
Owner Koro (127)
Last modified by Koro (127)
Numerical id 4
Author Koro (127)
Entry type Proof
Classification msc 05A10