<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] 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}).$
</s>