Results 1 to 3 of 3

Math Help - Inductive Proof: Multinomial Theorem

  1. #1
    Junior Member
    Joined
    Jul 2008
    Posts
    38

    Smile 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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by tcRom View Post
    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:

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

    Proof: by definition: \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)!}

    =\binom{n}{j_1 \cdots , j_m, n-k}. note that since j_1 + \cdots + j_m=k, we have: 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 m \geq 2 and multinomial theorem is true for m. for m + 1 we have:

    (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}

    =\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}

    =\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 n-k=j_{m+1}, then since 0 \leq k \leq n, we'll have 0 \leq j_{m+1} \leq n. also since j_1 + \cdots + j_m = k, we'll have j_1 + \cdots + j_m + j_{m+1}=n. finally 0 \leq j_1, \cdots , j_m \leq k

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

    \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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jul 2008
    Posts
    38
    Quote Originally Posted by NonCommAlg View Post
    (...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?

    Quote Originally Posted by NonCommAlg View Post
    =\binom{n}{j_1 \cdots , j_m, n-k}. note that since j_1 + \cdots + j_m=k, we have: j_1 + \cdots + j_m + n-k= n. \ \ \ \square
    How is it that j_1 + \cdots + j_m + n-k= n and 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 !

    Quote Originally Posted by NonCommAlg View Post
    now in the above put n-k=j_{m+1}, ... also since j_1 + \cdots + j_m = k, we'll have 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!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Inductive proof
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: December 8th 2009, 01:11 AM
  2. help me with Inductive Proof #1
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 16th 2009, 10:16 AM
  3. Inductive Proof help!
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 25th 2009, 09:38 AM
  4. Challenging multinomial theorem question?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 14th 2009, 02:51 AM
  5. Inductive proof
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 28th 2008, 06:24 PM

Search Tags


/mathhelpforum @mathhelpforum