Editing Binomial theorem (section)

== Proofs ==

=== Combinatorial proof ===
Expanding {{math|1=(''x'' + ''y'')<sup>''n''</sup>}} yields the sum of the {{math|2<sup>''n''</sup>}} products of the form {{math|1=''e''<sub>1</sub>''e''<sub>2</sub> ... ''e''<sub>''n''</sub>}} where each {{math|''e''<sub>''i''</sub>}} is {{mvar|''x''}} or&nbsp;{{mvar|y}}. Rearranging factors shows that each product equals {{math|''x''<sup>''n''&minus;''k''</sup>''y''<sup>''k''</sup>}} for some {{mvar|k}} between {{math|0}} and&nbsp;{{mvar|n}}. For a given {{mvar|k}}, the following are proved equal in succession:
* the number of terms equal to {{math|1=''x''<sup>''n''−''k''</sup>''y''<sup>''k''</sup>}} in the expansion
* the number of {{mvar|n}}-character {{math|''x'',''y''}} strings having {{mvar|y}} in exactly {{mvar|k}} positions
* the number of {{mvar|k}}-element subsets of {{math|1={{mset|1, 2, ..., ''n''}}}}
* <math>\tbinom{n}{k},</math> either by definition, or by a short combinatorial argument if one is defining <math>\tbinom{n}{k}</math> as <math>\tfrac{n!}{k! (n-k)!}.</math>
This proves the binomial theorem.

==== Example ====
The coefficient of {{math|''xy''<sup>2</sup>}} in
<math display="block">\begin{align}
   (x+y)^3 &= (x+y)(x+y)(x+y) \\
   &= xxx + xxy + xyx + \underline{xyy} + yxx + \underline{yxy} + \underline{yyx} + yyy \\
   &= x^3 + 3x^2y + \underline{3xy^2} + y^3
\end{align}</math>
equals <math>\tbinom{3}{2}=3</math> because there are three {{math|''x'',''y''}} strings of length 3 with exactly two {{mvar|y}}'s, namely,
<math display="block">xyy, \; yxy, \; yyx,</math>
corresponding to the three 2-element subsets of {{math|{{mset|1, 2, 3}}}}, namely,
<math display="block">\{2,3\},\;\{1,3\},\;\{1,2\}, </math>
where each subset specifies the positions of the {{mvar|y}} in a corresponding string.

=== Inductive proof ===
[[mathematical induction|Induction]] yields another proof of the binomial theorem. When {{math|1=''n'' = 0}}, both sides equal {{math|1}}, since {{math|1=''x''<sup>0</sup> = 1}} and <math>\tbinom{0}{0}=1.</math>  Now suppose that the equality holds for a given {{mvar|n}}; we will prove it for {{math|1=''n'' + 1}}.  For {{math|1=''j'', ''k'' ≥ 0}}, let {{math|1=[''f''(''x'', ''y'')]<sub>''j'',''k''</sub>}} denote the coefficient of {{math|1=''x''<sup>''j''</sup>''y''<sup>''k''</sup>}} in the polynomial {{math|1=''f''(''x'', ''y'')}}.  By the inductive hypothesis, {{math|1=(''x'' + ''y'')<sup>''n''</sup>}} is a polynomial in {{mvar|x}} and {{mvar|y}} such that {{math|1=[(''x'' + ''y'')<sup>''n''</sup>]<sub>''j'',''k''</sub>}} is <math>\tbinom{n}{k}</math> if {{math|1=''j'' + ''k'' = ''n''}}, and {{mvar|0}} otherwise.  The identity
<math display="block"> (x+y)^{n+1} = x(x+y)^n + y(x+y)^n</math>
shows that {{math|1=(''x'' + ''y'')<sup>''n''+1</sup>}} is also a polynomial in {{mvar|x}} and {{mvar|y}}, and
<math display="block"> [(x+y)^{n+1}]_{j,k} = [(x+y)^n]_{j-1,k} + [(x+y)^n]_{j,k-1},</math>
since if {{math|1=''j'' + ''k'' = ''n'' + 1}}, then {{math|1=(''j'' − 1) + ''k'' = ''n''}} and {{math|1=''j'' + (''k'' − 1) = ''n''}}. Now, the right hand side is
<math display="block"> \binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k},</math>
by [[Pascal's identity]].<ref>[http://proofs.wiki/Binomial_theorem Binomial theorem] – inductive proofs {{webarchive |url=https://web.archive.org/web/20150224130932/http://proofs.wiki/Binomial_theorem |date=February 24, 2015 }}</ref> On the other hand, if {{math|1=''j'' + ''k'' ≠ ''n'' + 1}}, then {{math|1=(''j'' – 1) + ''k'' ≠ ''n''}} and {{math|1=''j'' + (''k'' – 1) ≠ ''n''}}, so we get {{math|1=0 + 0 = 0}}. Thus
<math display="block">(x+y)^{n+1} = \sum_{k=0}^{n+1} \binom{n+1}{k} x^{n+1-k} y^k,</math>
which is the inductive hypothesis with {{math|1=''n'' + 1}} substituted for {{mvar|n}} and so completes the inductive step.