<s>[INST] Proof Verification $\sum_{k=0}^n \binom{n}{k} = 2^n$ (Spivak's Calculus) $$\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) 
 [/INST] 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.
</s>