1
$\begingroup$

I'm trying to prove binomial theorem by induction, but I'm a little stuck. I would look at online resources as this problem has been done many times, but the version I am trying to prove the binomial theorem in a different form.

$$(1 + x)^n = \sum_{k = 0}^{n} \binom{n}{k} x^k$$

I'm mostly confused as to how I can make the left side be equivalent to a summation, any help is appreciated. Try to hint me along!

$\endgroup$
  • 1
    $\begingroup$ Probably the form most online resources use is $(a+b)^n$. Simply substitute $a = 1, b = x$ everywhere in the proof. $\endgroup$ – user370967 Mar 27 '17 at 20:45
  • 2
    $\begingroup$ Note that $(1+x)^{n+1}=(1+x)\cdot (1+x)^n$ which by your induction hypothesis will be $(1+x)\cdot \left(\sum\limits_{k=0}^n\binom{n}{k}x^k\right)$. Now... some frustrating shifting of indices and combining of terms later you should arrive at the result. Remember your Paschal's identity: $\binom{n}{k-1}+\binom{n}{k}=\binom{n+1}{k}$ $\endgroup$ – JMoravitz Mar 27 '17 at 20:45
  • 1
    $\begingroup$ If you are still stuck, I suggest you use the search function on this site to find duplicate answers, which there surely are dozens of for this question already. $\endgroup$ – JMoravitz Mar 27 '17 at 20:48
  • $\begingroup$ After a couple hours of searching, I found a couple of examples, but I received this problem with little background in algebraically manipulating summations. Using examples of the form $(a + b)^n$ won't work unfortunately, thanks for all your help! $\endgroup$ – Howard P Mar 28 '17 at 15:39
  • $\begingroup$ I did not find a full answer, though $\endgroup$ – Howard P Mar 28 '17 at 16:24
5
$\begingroup$

We show by induction the following is valid for $n\geq 0$ \begin{align*} (1 + x)^n = \sum_{k = 0}^{n} \binom{n}{k} x^k \end{align*}

Base step: $n=0$

We have to show \begin{align*} (1 + x)^0 = \sum_{k = 0}^{0} \binom{0}{k} x^k \end{align*}

Since the left-hand side is $$(1+x)^0=1$$ and the right-hand side is $$\sum_{k = 0}^{0} \binom{0}{k} x^k=\binom{0}{0}x^0=1,$$ both sides are equal and the claim is valid for $n=0$.

Induction hypothesis: $n=N$

We assume the validity of \begin{align*} (1 + x)^N = \sum_{k = 0}^{N} \binom{N}{k} x^k\tag{1} \end{align*}

Induction step: $n=N+1$

We have to show \begin{align*} (1 + x)^{N+1} = \sum_{k = 0}^{N+1} \binom{N+1}{k} x^k \end{align*}

We obtain \begin{align*} (1 + x)^{N+1} &= (1+x)(1+x)^N\tag{2}\\ &=(1+x)\sum_{k = 0}^{N} \binom{N}{k} x^k\tag{3}\\ &=\sum_{k = 0}^{N} \binom{N}{k} x^k+\sum_{k = 0}^{N} \binom{N}{k} x^{k+1}\tag{4}\\ &=\binom{N}{0}x^0+\sum_{k=1}^N\binom{N}{k}x^k+\sum_{k=0}^{N-1}\binom{N}{k}x^{k+1}+\binom{N}{N}x^{N+1}\tag{5}\\ &=\binom{N+1}{0}x^0+\sum_{k=1}^N\binom{N}{k}x^k+\sum_{k=1}^{N}\binom{N}{k-1}x^{k}+\binom{N+1}{N+1}x^{N+1}\tag{6}\\ &=\sum_{k=0}^{N+1}\binom{N+1}{k}x^k\tag{7} \end{align*} and the claim follows.

Comment:

  • In (2) we split the product, since we want to apply the induction hypothesis.

  • In (3) we apply the induction hypothesis (1).

  • In (4) we multiply out.

  • In (5) we separate the first summand $\binom{N}{0}$ from the left sum and the last summand $\binom{N}{N}x^{N+1}$ from the right sum.

  • In (6) we use the binomial identities \begin{align*} \binom{N}{0}=\binom{N+1}{0}=1\qquad\text{and}\qquad\binom{N}{N}=\binom{N+1}{N+1}=1 \end{align*} We also shift the index $k$ of the right sum by one to start from $k=1$. This all is a preparation for the next step to easily collect all the terms in one sum.

  • In (7) we apply the binomial identity \begin{align*} \binom{N}{k}+\binom{N}{k-1}=\binom{N+1}{k} \end{align*} and the two sums can be merged into one sum. We also see the left-most term $\binom{N+1}{0}$ and the right-most term $\binom{N+1}{N+1}$ can be made part of the sum using index $k=0$ and $k=N+1$.

$\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.