Number of distinct terms in the expansion of $(\sum_{i=1}^m x_i)^n$ where n,m are positive integers

24 Views Asked by At

First, I need to establish by induction on n that a general term in the expansion will be of the form:
$$\prod_{j=1}^m x_j^{i_j}$$ where $i_1,i_2,\cdots,i_m$ are non-negative integers with the property: $$\sum_{k=1}^m i_k=n$$.
For n=2, the result can be verified easily. For n=h, let the statement be true.
For n=h+1, each general term of expansion for n=h will be, $$\prod_{j=1}^m x_j^{i_j}$$ with $$\sum_{k=1}^m i_k=h$$.
As a result the general term of expansion for n=h+1 is, $$(\prod_{j=1}^m x_j^{i_j})x_j$$ for some j such that $$(\sum_{k=1}^m i_k)+1=h+1$$ This concludes the first part of proof. The number of distinct terms in the expansion can be found by finding all possible vector-valued solutions $$(i_1,i_2,\cdots,i_m)$$ of the equation $$\sum_{k=1}^m i_k=n$$. This is nothing but $$ n+m-1 \choose m-1$$. I guess I messed up in the induction part. Please let me know the faults and drawbacks of the proof.