{{ stepNode.name }}

{{ 'ml-toc-proceed' | message }}

An error ocurred, try again later!

Chapter {{ article.chapter.number }}

{{ article.number }}. # {{ article.displayTitle }}

{{ article.intro.summary }}

{{ 'ml-btn-show-less' | message }} {{ 'ml-btn-show-more' | message }} {{ 'ml-lesson-show-solutions' | message }}

{{ 'ml-lesson-show-hints' | message }}

| {{ 'ml-lesson-number-slides' | message : article.intro.bblockCount}} |

| {{ 'ml-lesson-number-exercises' | message : article.intro.exerciseCount}} |

| {{ 'ml-lesson-time-estimation' | message }} |

Each of the terms $_{n}C_{j}$ are the combinations of $n$ objects taken $j$ at a time. The values of $_{n}C_{j}$ are the same as those in the $nth$ row of Pascal's triangle. Therefore, the binomial expansion can also be written in terms of the Pascal's Triangle's values of the $nth$ row.

To prove this theorem, a method called Mathematical Induction will be used. First the small cases need to be examined. Consider that $n=1.$
Considering this result, the repeating terms can be rewritten to simplify the binomial expansion.

$(x+y)_{1}=x+y $

Since $_{1}C_{0}$ and $_{1}C_{1}$ are both equal to $1,$ the theorem holds for this case. Now consider $n=2.$
$(x+y)_{2}=x_{2}+2xy+y_{2} $

On this case, $_{2}C_{0}$ and $_{2}C_{2}$ are equal $1$ and $_{2}C_{1}$ is equal to $2,$ making this case also true. Following this, it can be assumed that the theorem holds for a natural number $k.$
To prove the theorem, it needs to be shown that the theorem holds for the value of $k+1.$ This can be done by multiplying the case above by $(x+y).$
$(x+y)_{k+1}=(x+y)(x+y)_{k} $

To expand the binomial, multiply $(x+y)$ by the binomial expansion of $(x+y)_{k}.$ This has to be done carefully, as distributing $x$ and $y$ modify the terms on the binomial expansion.
Examining the resulting terms closely, it can be noted that there are terms that can be factored together. For example, consider the following.
$_{k}C_{1}x_{k}y_{1}+_{k}C_{0}x_{k}y_{1}_{k}C_{2}x_{k−1}y_{2}+_{k−1}C_{1}x_{k−1}y_{2} =(_{k}C_{0}+_{k}C_{1})x_{k}y_{1}=(_{k}C_{1}+_{k}C_{2})x_{k−1}y_{2} $

Using these examples, it is possible to find a way to write these terms. Let $r$ be a natural number from $1$ to $k.$ Using this variable, factored terms can be written as follows.
$(_{k}C_{r−1}+_{k}C_{r})x_{k−r+1}y_{r} $

Now the sum between parenthesis will be examined to see if it can be simplified. The expressions for the combinations will be used to do so.
$_{k}C_{r−1}+_{k}C_{r}$

Simplify

SubstituteExpressions

Substitute expressions

$(k−(r−1))!(r−1)!k! +(k−(r))!(r)!k! $

FactorOut

Factor out $k!$

$k!((k−(r−1))!(r−1)!1 +(k−(r))!(r)!1 )$

DistrNegSignSwap

$-(b−a)=a−b$

$k!((k+1−r)!(r−1)!1 +(k−r)!(r)!1 )$

ExpandFrac

$ba =b⋅ra⋅r $

$k!((k+1−r)!(r−1)!rr +(k−r)!(r)!1 )$

$(r−1)!r=r!$

$k!((k+1−r)!(r)!r +(k−r)!(r)!1 )$

ExpandFrac

$ba =b⋅(k+1−r)a⋅(k+1−r) $

$k!((k+1−r)!(r)!r +(k−r)!(r)!(k+1−r)k+1−r )$

$(k−r)!(k+1−r)=(k+1−r)!$

$k!((k+1−r)!(r)!r +(k+1−r)!(r)!k+1−r )$

AddFrac

Add fractions

$k!((k+1−r)!(r)!k+1 )$

Multiply

Multiply

$(k+1−r)!(r)!k!(k+1) $

$k!(k+1)=(k+1)!$

$(k+1−r)!(r)!(k+1)! $

SubstituteExpressions

Substitute expressions

$_{k+1}C_{r}$

Looking at the binomial expansion, it can be noted that the repeated terms are written like the theorem. The remaining terms $x_{k+1}$ and $y_{k+1}$ can be rewritten considering the values of $_{k}C_{0}x_{k+1}$ and ·$_{k}C_{k}x_{0}y_{k+1}.$

Combination | Formula | Simplify |
---|---|---|

$_{k}C_{0}$ | $(k−0)!0!k! $ | $1$ |

$_{k}C_{k}$ | $(k−k)!k!k! $ | $1$ |

$_{k+1}C_{0}$ | $(k+1−0)!0!(k+1)! $ | $1$ |

$_{k+1}C_{k+1}$ | $(k+1−(k+1))!(k+1)!(k+1)! $ | $1$ |

Since of the values on the table are equal to $1,$ these can be interchanged to rewrite the expression one last time.

Therefore, the result holds for in the case that $n=k+1,$ which finish the proof.