1

I've seen the standard combinatorial and algebraic proofs that $\sum_{k=0}^n {n \choose k}=2^n$, where the algebraic proof uses induction and Pascal's identity: $${n\choose k}+{n\choose k+1}={n+1\choose k+1}$$

My question is: is there any algebraic proof of the sum $\sum_{k=0}^n {n \choose k}=2^n$ that doesn't use that identity and induction? More specifically, is there some factoring trick (or some other method) that would allow you to directly show that, for example, $\frac{4!}{4!0!}+\frac{4!}{3!1!}+\frac{4!}{2!2!}+\frac{4!}{1!3!}+\frac{4!}{4!0!}=2^4$ (that would generalize to other values of n)?

(My first thought was to just 'unwind' the inductive proof, but that just leads to $1+1+...+1$ with $2^n$ terms, which isn't very enlightening.)

nhg
  • 11
  • 1

2 Answers2

1

Combinatorial argument:

$\displaystyle\binom nk$ counts the number of ways to write numbers made of $k$ zeroes and $n-k$ ones. Hence the sum on all $k$ counts the number of $n$-bits binary numbers.

$$000\,|\,001,010,100\,|\,011,101,110\,|\,111$$

0

We can apply the binomial theorem and obtain

\begin{align*} \color{blue}{\sum_{k=0}^n\binom{n}{k}}=\sum_{k=0}^n\binom{n}{k}1^k1^{n-k}=(1+1)^n\color{blue}{=2^n} \end{align*}

Markus Scheuer
  • 108,315