1
$\begingroup$

This question is taken from chapter 2 of M.Spivak's "Calculus":

3e (i) Prove that $\sum_{j=0}^n\binom{n}{j} = \binom{n}{0} + \cdots + \binom{n}{n} = 2^n$

I understand that an easy way to show the desired result is obtained by considering $(1 + 1)^n$; in expanding the product $$\underbrace{(1 + 1) \cdots (1 + 1)}_{\text{ n factors}}$$ as a sum, there exist $2^n$ ways to choose $1$ (which is the only term to choose from each $(a + b)$ when $a = 1 = b$). However, I have a different proof of such result and would like to confirm its validity; my main concern is with the inductive hypothesis: am I assuming more than I should?

Proof: Let $P(n)$ stand for the statement

The sum of all elements in the $(n + 1)th$ row of Pascal's triangle is equal to $2^n$

which we write as $\sum_{j=0}^{n} \binom{n}{j} = 2^n$.

We use induction on $n$ - the row of Pascal's triangle.

Base case: in the 1st row there exists only one element $$\binom{0}{0} = 1 = 2^0$$

Inductive step: Suppose that the result holds for all $\binom{n}{p}$ where $0 \le j \le n$, i.e. the sum of all elements of the $(n + 1)th$ row of Pascal's triangle yield $2^n$. Then \begin{align} \sum_{j=0}^{n +1} \binom{n + 1}{j} & = \binom{n + 1}{0} + \binom{n + 1}{1} + \cdots + \binom{n + 1}{n} + \binom{n + 1}{n + 1} \\ & = \binom{n + 1}{0} + \left[ \left( \binom{n}{0} + \bbox[yellow]{\binom{n}{1}} \right) + \left( \bbox[yellow]{\binom{n}{1}} + \binom{n}{2} \right) + \cdots + \left( \binom{n}{n - 2} + \bbox[yellow]{\binom{n}{n - 1}} \right) + \left( \bbox[yellow]{\binom{n}{n -1}} + \binom{n}{n} \right) \right] + \binom{n+1}{n+1} && \tag{1}\label{1} \\ & = \binom{n+1}{0} + \left[ \sum_{j=0}^n \binom{n}{j} + \left( \binom{n}{1} + \cdots + \binom{n}{n-1} \right) \right] + \binom{n+1}{n+1} \\ & = \binom{n}{0} + \sum_{j=0}^n \binom{n}{j} + \left( \binom{n}{1} + \cdots + \binom{n}{n-1} \right) + \binom{n}{n} \tag{2}\label{2} \\ & = \sum_{j=0}^n \binom{n}{j} + \sum_{j=0}^n \binom{n}{j} \\ & = 2 \times \sum_{j=0}^n \binom{n}{j} \\ & = 2 \times 2^n = 2^{n+1} \end{align}

Thus, the sum of all elements of the $(n + 2)th$ row is equal to $2^{n+1}$ as required. Hence, by induction on $n$, the result holds for all $n$ rows of Pascal's triangle. $\tag*{$\square$}$


$(\ref{1}$) because $\binom{n+1}{j} = \binom{n}{j-1} + \binom{n}{j}$; each of $\binom{n}{j}$ has a duplicate for $1 \le j \le n-1$

$(\ref{2}$) because $\binom{n}{0} = \binom{n+1}{0} = 1 = \binom{n+1}{n+1} = \binom{n}{n}$

$\endgroup$
  • $\begingroup$ If the question was whether or not this is fine, I will say it looks mostly fine except that the formatting wasn't beautiful. $\endgroup$ – Simply Beautiful Art Jan 10 '17 at 19:25
  • 1
    $\begingroup$ the simplest proof is to just recognize that both expressions enumerate the number of subsets of an $n$ element set. $\endgroup$ – Jorge Fernández Hidalgo Jan 10 '17 at 19:25
  • 1
    $\begingroup$ @JorgeFernándezHidalgo that is, the cardinality of the power set of a set with $n$ elements right? That didn't occur to me; it seems that it is indeed the simplest and most comprehensive proof! Thank you $\endgroup$ – bender Jan 10 '17 at 19:29
  • $\begingroup$ @SimpleArt that is the question. I apologize for the format; I tried my best, but the proof itself is too extensive $\endgroup$ – bender Jan 10 '17 at 19:31

Your Answer

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

Browse other questions tagged or ask your own question.