Proof Verification $\sum_{k=0}^n \binom{n}{k} = 2^n$ (Spivak's Calculus)

Question

$$\sum_{k=0}^n \binom{n}{k} = 2^n$$ I'll use induction to solve prove this. Then

$$\sum_{k=0}^n \binom{n}{k} = 2^n = \binom{n}{0} + \binom{n}{1} + ... + \binom{n}{n - 1} + \binom{n}{n}$$

First prove with n = 1

$$\binom{1}{0} + \binom{1}{1} = 2^1$$

Since $$\binom{1}{0} = \binom{1}{1} = 1$$

it's true.

Now suppose that is true with $n$ if is true with $n + 1$

Then, multiply both sides by two

$$2(2^n) = 2(\binom{n}{0} + \binom{n}{1} + ... + \binom{n}{n - 1} + \binom{n}{n})$$

$$2^{n+1} = 2\binom{n}{0} + 2\binom{n}{1} + ... + 2\binom{n}{n - 1} + 2\binom{n}{n}$$

$$2\binom{n}{0} + 2\binom{n}{1} + ... + 2\binom{n}{n - 1} + 2\binom{n}{n} = \binom{n}{0} + \binom{n}{0} + \binom{n}{1} + \binom{n}{1} + ... + \binom{n}{n} + \binom{n}{n} $$

The first term have two equal term, then, you sum the last one with the first one of the next term, and you'll get this

$$\binom{n}{0} + \binom{n}{1} +... + \binom{n}{n-1} + \binom{n}{n}$$

If we use this equation (Already proved)

$$\binom{n}{k-1} + \binom{n}{k} = \binom{n+1}{k} $$

Of course, we'll have two term without sum, one $\binom{n}{0}$ and $\binom{n}{n}$

We can write these two term like this

$$\binom{n}{0} = \binom{n}{n} = \binom{n+1}{0} = \binom{n+1}{n+1}$$

Then, we get

$$2^{n+1} = \binom{n+1}{0} + \binom{n+1}{1} + ... + \binom {n+1}{n+1}$$

And it's already proved. Note: Just if we take $0! = 1$

I have to prove these too.

$\sum_{k}^n \binom{n}{m} = 2^{n-1}$ If $m$ is even. And $\sum_{j}^n \binom{n}{j} = 2^{n-1}$ If $j$ is odd. Then, I just said that

If $$\sum_{m}^n \binom{n}{m} + \sum_{j}^n \binom{n}{j} = \sum_{k=0}^n \binom{n}{k} $$

Then

$$2^{n - 1} + 2^{n - 1} = 2^n$$

Which is true, then, I already prove this. And I have a last one.

$$\sum_{i=0}^n (-1)^i\binom{n}{i} = 0$$

if n is odd. Then

$$\binom{n}{0} - \binom{n}{1} + ... + \binom{n}{n-1} - \binom{n}{n} = 0$$

And that's can be solve knowing that $$\binom{n}{k} = \binom{n}{n - k}$$

And if n is even

$$\binom{n}{0} - \binom{n}{1} + ... - \binom{n}{n-1} + \binom{n}{n} = 0$$

That means that every negative term if when n is odd, then, we can use our two last prove to prove it

If $$\sum_{m}^n \binom{n}{m} - \sum_{j}^n \binom{n}{j} = 0$$

Then

$$2^{n-1} - 2^{n-1} = 0$$

Which is true.

And that's it, I want to know if my proves are fine and are rigorous too and what is the meaning of every combinatorics prove .

I want to know too better approaches to prove these (Or forms more intuitive)

Answer 1

A better mathematician than you or I once struggled as mightily with this question as you have, and I told him to expand $(1+1)^n$ with the binomial expansion.

Answer 2

here is another approach:

Consider a set with $n$ objects. There are $\binom nk$ ways to choose $k$ of them. That way gives $\sum_{i=0}^n\binom ni$ ways to choose objects from the set. On the other hand, we can choose to choose each item or not.That gives $2^n$. And of course they are equal, since they both represent the number of ways to choose some objects from the set.

The second and the third one are actually the same (can you see why?). Using Pascal's triangle $\sum_{2|i}^n\binom ni=\sum_{2\nmid i}^n\binom ni$ since they both equal to the sum of the line above them. (which is $2^{n-1}).$

Answer 3

These are corollaries of the Binomial Theorem, which states that $$(x + y)^n = \sum_{k = 0}^{n} \binom{n}{k} x^{n - k}y^k$$

If we set $x = y = 1$, we obtain $$2^n = (1 + 1)^n = \sum_{k = 0}^{n} 1^{n - k}1^k = \sum_{k = 0}^{n} \binom{n}{k}$$ which means that the number of subsets of a set with $n$ elements is $2^n$.

If we set $x = 1$ and $y = -1$, we obtain $$0^n = [1 + (-1)]^n = \sum_{k = 0}^{n} 1^{n - k}(-1)^{k} = \sum_{k = 0}^{n} (-1)^k\binom{n}{k}$$ Notice that each term in which $k$ is even is positive and each term in which $k$ is odd is negative. Hence, $$\sum_{k = 0}^{\lfloor \frac{n}{2} \rfloor} \binom{n}{2k} - \sum_{k = 0}^{\lfloor \frac{n}{2} \rfloor} \binom{n}{2k + 1} = 0 \tag{1}$$ which means the number of subsets with an even number of elements is equal to the number of subsets with an odd number of elements.

Since every subset has an even number of elements or an odd number of elements, $$\sum_{k = 0}^{\lfloor \frac{n}{2} \rfloor} \binom{n}{2k} + \sum_{k = 0}^{\lfloor \frac{n}{2} \rfloor} \binom{n}{2k + 1} = \sum_{k = 0}^{n} \binom{n}{k} = 2^n \tag{2}$$ Adding equations 1 and 2 yields $$2\sum_{k = 0}^{\lfloor \frac{n}{2} \rfloor} \binom{n}{2k} = 2^n \implies \sum_{k = 0}^{\lfloor \frac{n}{2} \rfloor} \binom{n}{2k} = 2^{n - 1}$$ which means the number of subsets with an even number of subsets is $2^{n - 1}$.

Since the number of subsets with an odd number of elements is equal to the number of subsets with an even number of elements, the number of subsets with an odd number of elements is $$\sum_{k = 0}^{\lfloor \frac{n}{2} \rfloor} \binom{n}{2k + 1} = 2^{n - 1}$$