4
$\begingroup$

I am able to prove the binomial theorem (see $(1))$ by induction. I have also seen the binomial theorem written in another way (see $(2)$) where the summation changes a little bit. I understand how to compute both theorems, but I am having a difficult time proving the second theorem from the first.

Obviously, you could expand the sum from the first theorem and deduce the second one by intuition. However, I am wanting to see the connection as to how the first sum is manipulated into a form of the second one to be able to prove other theorems such as the multinomial theorem or other similar theorems with multiple summations by using induction on the number of variables/index sets/etc.

What do you do to prove the second equation from the first?

$(1)$ $\forall n\in \mathbb{W}$, $(x_1+x_2)^n=\sum_{i=0}^n \frac{n!}{(n-i)!i!}x_1^{n-i}x_2^{i}$.

$(2)$ $\forall n\in \mathbb{W}$, $(x_1+x_2)^n=\sum_{i_1+i_2=n} \frac{n!}{i_1!i_2!}x_1^{i_1}x_2^{i_2}$.

I have tried to follow an answer to a past question similar to this one. However, I was unable to follow it, and I am particularly stuck on this step. Any help would be greatly appreciated!!!


I know that this question has been down for some time, but after reviewing one of the answers, I feel the necessity to prove the below "lemma" to help others who are also curious about this question and myself to see what is going on here a little better even though I did already accept an answer.

"Lemma": $\forall n\in \mathbb{W}, \underbrace{\lbrace (i, n-i) | i\in \mathbb{W}, i\leq n \rbrace}_{=A}=\underbrace{\lbrace (i_1, i_2) | i_1, i_2\in \mathbb{W}, i_1+i_2=n\rbrace}_{=B}$.

Proof: Let $n\in \mathbb{W}$.

$\subseteq$ Assume $x\in A$. [Show $x\in B$.] As $x\in A$, we know $x=(i, n-i)$ for which $i\in \mathbb{W}$ and $i\leq n$. As $i+(n-i)=n$, $i\in \mathbb{W}$, and $0\leq \underbrace{n-i}_{\text{ so } \in \mathbb{W}}$, we know $x\in B$.

$\supseteq$ Assume $x\in B$. [Show $x\in A$.] Thus, $x=(i_1, i_2)$ for which $i_1, i_2\in \mathbb{W}$ and $i_1+i_2=n$. Thus, $x=(i_1, n-i_1)$ as $n-i_1=i_2$. Furthermore, suppose $\underbrace{n-i_1}_{=i_2}<0$ and show a contradiction. This means $i_2<0$. However, $i_2\in \mathbb{W}$ which is our contradiction. This means $n-i_1\geq 0$. Hence, $i_1\leq n$. As $x=(i_1, n-i_1)$ for which $i_1 \in \mathbb{W}$ and $i_1\leq n$, we know $x\in A$. //

$\endgroup$
  • $\begingroup$ What is $\mathbb W$? Is it $\mathbb N$? $\endgroup$ – AccidentalFourierTransform Feb 14 '18 at 19:04
  • $\begingroup$ It is: $\mathbb{W}=\mathbb{N}\cup \lbrace 0 \rbrace$. $\endgroup$ – W. G. Feb 14 '18 at 20:12
  • $\begingroup$ Oh, so $\mathbb W=\mathbb N$ ;-) $\endgroup$ – AccidentalFourierTransform Feb 14 '18 at 20:18
  • $\begingroup$ Lol! I refuse to call it that. $\endgroup$ – W. G. Feb 14 '18 at 20:29
  • $\begingroup$ @AccidentalFourierTransform Was about to write something like that haha $\endgroup$ – Jannik Pitt Feb 14 '18 at 20:46
6
$\begingroup$

First, we rename $i$ to $i_1$, giving us $$ (x_1+x_2)^n = \sum_{i_1=0}^n \frac{n!}{(n-i_1)!i_1!}x_1^{n-i_1}x_2^{i_1}$$ Now we introduce the index $i_2$ and define $i_2=n-i_1$. A substitution like this is equivalent to summing one term -- just the $i_2=n-i_1$ term, no other values of $i_2$ are included -- so I'll write it as a sum: $$ (x_1+x_2)^n = \sum_{i_1=0}^n \sum_{i_2=n-i_1} \frac{n!}{i_2!i_1!}x_1^{i_2}x_2^{i_1}$$ Now I just rearrange the equation under the second sum: $$ (x_1+x_2)^n = \sum_{i_1=0}^n \sum_{i_1+i_2=n} \frac{n!}{i_2!i_1!}x_1^{i_2}x_2^{i_1}$$ If we combine the two sums into one sum, we can write: $$ (x_1+x_2)^n = \sum_{0\leq i_1 \leq n, i_1+i_2=n} \frac{n!}{i_2!i_1!}x_1^{i_2}x_2^{i_1}$$ Note that given the $i_1+i_2=n$ condition, the $i_1 \leq n$ condition is equivalent to a $0 \leq i_2$ condition, so we can write $$ (x_1+x_2)^n = \sum_{0\leq i_1, 0 \leq i_2, i_1+i_2=n} \frac{n!}{i_2!i_1!}x_1^{i_2}x_2^{i_1}$$ which is (2).

$\endgroup$
  • $\begingroup$ This was helpful! Thank you! $\endgroup$ – W. G. Feb 14 '18 at 19:31
4
$\begingroup$

The actual equations are the same, the only thing that's different is the index set you're summing over. So you only need to prove that these two sets are equal:

$$ \left \{ (i, n - i) | i \in \mathbb N, i \leq n \right \} $$

and

$$ \left \{ (i_1, i_2) | i_1, i_2 \in \mathbb N, i_1 + i_2 = n \right \} $$

It's clear that all members of the first set are in the second. And since you're not dealing with negative numbers, all members of the second set are in the first. So the index sets are equal.

$\endgroup$
  • $\begingroup$ This was helpful too. Thank you for your help! $\endgroup$ – W. G. Feb 14 '18 at 20:22
  • $\begingroup$ This is the best answer in my opinion, nice and simple. $\endgroup$ – Jannik Pitt Feb 14 '18 at 20:46
1
$\begingroup$

We obtain \begin{align*} \color{blue}{\sum_{i=0}^n\frac{n!}{(n-i)!i!}x_1^{n-i}x_2^i} &=\sum_{{i+j=n}\atop{i,j\geq 0}}\frac{n!}{j!i!}x_1^jx_2^i\tag{1}\\ &\color{blue}{=\sum_{{i_1+i_2=n}\atop{i_1,i_2\geq 0}}\frac{n!}{i_1!i_2!}x_1^{i_1}x_2^{i_2}}\tag{2} \end{align*}

Comment:

  • In (1) we introduce a new index variable $j$.

  • In (2) we replace $j$ with $i_1$ and $i$ with $i_2$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.