Evaluate: binomial theorem

Question

Show: $$(x+1)^m=\sum_{k=1}^{m}\binom{m}{k}x^k$$

Can somebody help me in showing the above stated problem?

Answer 1

Proceed by induction on $m$. For $m = 0$, the statement holds; now assume true for all values $\leq m$. Then for $m + 1$, we have \begin{align} (x+1)^{m+1} &= (x + 1) (x + 1)^m \\ &= (x + 1)\sum\limits_{k = 0}^m \binom{m}{k}x^k &\text{ by the inductive hypothesis} \\ &=\sum\limits_{k = 0}^m \binom{m}{k}x^{k + 1} + \sum\limits_{k = 0}^m \binom{m}{k}x^{k}\\ &= \sum\limits_{k = 1}^{m+1} \binom{m}{k-1}x^{k} + \sum\limits_{k = 0}^m \binom{m}{k}x^{k} \\ &= x^{m+1} + 1 + \sum\limits_{k = 1}^m \left( \binom{m}{k - 1} + \binom{m}{k} \right) x^k \\ &= x^{m+1} + 1 + \sum\limits_{k = 1}^m \binom{m+1}{k} x^k &\text{ by Pascal's Triangle} \\ &= \sum\limits_{k = 0}^{m+1} \binom{m+1}{k}x^k \end{align} completing the proof.

---

One can also prove this combinatorially. Since this is a polynomial, we need only show that the left-hand-side and right-hand-side are equal for all $x \in \mathbb{N}$. The left-hand-side counts functions from $[m] \to [x + 1]$ where $[m] = \{1,2,\ldots,m\}$. To do so, for each $k = 0,1,\ldots, m$, we can choose $m - k$ elements of $m$ to go to $x + 1$, and then choose a function to $[x]$ for the remaining $k$ remaining members of $m$. Since this is a bijection, the two numbers must be equal, yielding $$ (x + 1)^m = \sum\limits_{k=0}^m \binom{m}{k}x^k. $$

Answer 2

We will adapt a non-inductive, combinatorial proof of the binomial theorem. We seek the expansion of \begin{align*} (x+1)^m &= (x+1)\cdots(x+1) \\ &= a_m x^m + a_{m-1} x^{m-1} + \cdots + a_1 x + a_0 \end{align*} Each integer coefficient can be treated as the number of times the variable of the term appears in a full expansion. Note that each term in the full expansion comes from picking one term from each factor. For example, \begin{align*} (x+1)^3 &= xxx + xx1 + x1x + 1xx + x11 + 1x1 + 11x + 111 \\ &= x^3 + 3x^2(1) + 3x(1)^2 + (1)^3. \end{align*} The number of ways to obtain $x^k$ is exactly the number of ways to reorder $$\underbrace{x,x,\cdots,x}_{k \text{ times}},\underbrace{1,1,\cdots,1}_{m - k \text{ times}}$$ The positions of the $x$'s uniquely determine the position of the 1's, and there are $\binom{m}{k}$ ways to pick spots for the $x$'s. Hence $a_k = \binom{m}{k}$.

Answer 3

You could use induction but maybe we can appeal to a counting argument:

Write $P= (x+1)(x+1)(x+1)\cdots (x+1)$ where there are $m$ instances of $x+1$.

Now, when we expand this, if we respect the order of the multiplication, then an arbitrary term will be a product of $1's$ and $x's$ that satisfies:

the number of instances of $1$+ the number of instances of $x$ must equal $m$.

For example, if $m=4$, we might have $xx11$ which is $x^2$ or maybe $x1x1$ which is also $x^2$. Now, the number of total instances of $x^2$ will give us our coefficient in the expansion when we combine like terms. So we ask how many instances of $x^2$ are there? We can make a list:

$xx11, x1x1, 1x1x, 11xx,1xx1,x11x$

Therefore in our expansion of $(x+1)^{4}$ we will have the term $6x^2$.

To arrive at this number without making the list, we simply observe that to obtain any given member of the list, we are choosing two indistinguishable items to distribute among four places and the number of ways of doing this is exactly $\binom{4}{2}=\frac{4\cdot 3}{2!}=6$.

In general then, if we want the coefficient of the $x^j$ term in the expansion $(x+1)^{m}$, $0\leq j\leq m$ we simply observe that we are distributing $j$ indistinguishable items among $m$ places, and since the number of ways of doing this is $\binom{m}{j}$ we see that the coefficients are as advertised in the formula.