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