1
$\begingroup$

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.)

$\endgroup$
  • 2
    $\begingroup$ $2^n=(1+1)^n=$ ... $\endgroup$ – Michael Hoppe Jul 24 '18 at 8:04
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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*}

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