# Difference between revisions of "Multinomial Theorem"

(→Proof) |
(→Proof by Induction) |
||

Line 12: | Line 12: | ||

== Proof == | == Proof == | ||

− | ==Proof by Induction== | + | ===Proof by Induction=== |

+ | Proving the Multinomial Theorem by Induction | ||

+ | |||

+ | For a positive integer <math>k</math> and a non-negative integer <math>n</math>, | ||

+ | <cmath>(x_1 + x_2 + x_3 + ... + x_{k-1} + x_k)^n = \sum_{b_1 + b_2 + b_3 + ... + b_{k-1} + b_k= n}{\binom{n}{b_1, b_2, b_3, ..., b_{k-1}, b_k} \prod_{j=1}^{k}{x_j^{b_j}}}</cmath> | ||

+ | |||

+ | [b]Proof:[/b] | ||

+ | When <math>k=1</math> the result is true, and when <math>k=2</math> the result is the binomial theorem. Assume that <math>k \ge 3</math> and that the result is true for <math>k=p</math> When <math>k=p+1</math> | ||

+ | <cmath>(x_1 + x_2 + x_3 + ... + x_{p-1} + x_p)^n = (x_1 + x_2 + x_3 + ... + x_{p-1} + (x_p +x_{p+1})^n</cmath> | ||

+ | Treating <math>x_p + x_{p+1}</math> as a single term and using the induction hypothesis: | ||

+ | <cmath>\sum_{b_1 + b_2 + b_3 + ... + b_{p-1} + B = n}{\binom{n}{b_1, b_2, b_3, ..., b_{p-1}, B} \cdot (x_p + x_{p+1})^B \cdot \prod_{j=1}^{p-1}{x_j^{b_j}}}</cmath> | ||

+ | By the Binomial Theorem, this becomes: | ||

+ | <cmath>\sum_{b_1 + b_2 + b_3 + ... + b_{p-1} + B = n}{\binom{n}{b_1, b_2, b_3, ..., b_{p-1}, B}} (\prod_{j=1}^{p-1}{x_j^{b_j}}) \cdot \sum_{b_p + b_{p+1} = B}{\binom{B}{b_p} \cdot x_p^{b_p} x_{p+1}^{b_{p+1}}}</cmath> | ||

+ | Since <math>\binom{n}{b_1, b_2, b_3, ... ,b_p, B}\binom{B}{b_p} = \binom{n}{b_1, b_2, b_3, ... ,b_p, b_{p+1}}</math>, this can be rewritten as: | ||

+ | <cmath>\sum_{b_1 + b_2 + ... b_p + b_{p+1}= n}{\binom{n}{b_1, b_2, b_3, ..., b_p, b_{p+1}}\prod_{j=1}^{k}{x_j^{b_j}}}</cmath> | ||

+ | |||

=== Combinatorial proof === | === Combinatorial proof === | ||

Keep on moving... | Keep on moving... |

## Revision as of 13:44, 10 October 2017

The **Multinomial Theorem** states that
where is the multinomial coefficient .

Note that this is a direct generalization of the Binomial Theorem: when it simplifies to

## Contents

## Proof

### Proof by Induction

Proving the Multinomial Theorem by Induction

For a positive integer and a non-negative integer ,

[b]Proof:[/b] When the result is true, and when the result is the binomial theorem. Assume that and that the result is true for When Treating as a single term and using the induction hypothesis: By the Binomial Theorem, this becomes: Since , this can be rewritten as:

### Combinatorial proof

Keep on moving...
*This article is a stub. Help us out by expanding it.*

## Problems

### Intermediate

- The expression

is simplified by expanding it and combining like terms. How many terms are in the simplified expression?

(Source: 2006 AMC 12A Problem 24)

### Olympiad

*This problem has not been edited in. If you know this problem, please help us out by adding it.*

*This article is a stub. Help us out by expanding it.*