Combinatorics and Graph Theory · Problem 1.5.5

Fundamentals — David Guichard

Mathematics — Combinatorics · multinomial-theorem

Problem

The Binomial Theorem (1.3.1) can be written

(x+y)^n = \sum_{i+j=n} \binom{n}{i\, j} x^i y^j,

where the sum is over all non-negative integers

i

and

j

that sum to

n

. Prove that for

m \geq 2

(x_1 + x_2 + \cdots + x_m)^n = \sum \binom{n}{i_1\, i_2\, \ldots\, i_m} x_1^{i_1} x_2^{i_2} \cdots x_m^{i_m},

where the sum is over all

i_1, \ldots, i_m

such that

i_1 + \cdots + i_m = n