\[{n \choose 0} = {n \choose n} = 1 \] is true because there's only one way of choosing no things, or all the things. \[{n \choose 1} = {n \choose n-1} = n \] is true because either we're including a single element, or precluding a single element, and there are $n$ such elements to include or preclude.
\[{n \choose k} = {n \choose n-k}\] is true because choosing $k$ elements to take from $n$ is equivalent to choosing $n-k$ elements to leave behind.
\[{n \choose k} = {n-1 \choose k} + {n-1 \choose k-1}\] is true because we can either leave the first element and choose $k$ from the remaining $n-1$, or we can take the first element, in which case we still need $k-1$ more from the remaining $n-1$.
Deriving the formula:
There are $n \times (n-1) \times \dots \times (n-k+1)$ choices altogether.
Each choice is counted $k!$ times because there are $k!$ orderings of $k$ elements ($k$ choices for the first, $k-1$ choices for the second...) and each ordering is counted exactly once. We compensate by dividing by $k!$.
So we get \[\frac{\prod_{r=n-k+1}^n r}{k!}\] which can be more simply written as \[\frac{n!}{k!(n-k)!}\]
Then the symmetry between $k$ and $n-k$ follows since $n-(n-k)=k$, the results with $k$ being 0 and 1 and hence $n$ and $n-1$ follow by substitution, and the addition formula follows like so: \[\begin{align*} {n-1 \choose k-1} + {n-1 \choose k} &= \frac{(n-1)!}{(k-1)!(n-k)!} + \frac{(n-1)!}{k!(n-k-1)!} \\ &= \frac{(n-1)!}{(k-1)!(n-k)(n-k-1)!} + \frac{(n-1)!}{k(k-1)!(n-k-1)!} \\ &= \frac{(n-1)!}{(k-1)!(n-k-1)!}\left(\frac{1}{n-k} + \frac{1}{k}\right) \\ &= \frac{(n-1)!}{(k-1)!(n-k-1)!}\left( \frac{k + (n-k)}{k(n-k)}\right) \\ &= \frac{(n-1)!n}{(k-1)!(n-k-1)!k(n-k)} \\ &= \frac{n!}{k!(n-k)!} \\ &= {n \choose k} \end{align*}\]
The binomial coefficients arise because in the expansion of $(a+b)(a+b)\dots(a+b)$ we get one $a^k b^{n-k}$ for each set of $k$ $a$'s we can pick out from the $n$ brackets.
The first sum can be algebraically shown by repeated application of the addition rule above: \[\begin{align*} {n \choose r} &= {n-1 \choose r-1} + {n-1 \choose r} \\ &= {n-1 \choose r-1} + {n-2 \choose r-1} + {n-2 \choose r} \\ &= \dots \end{align*}\] continuing until we get to ${r-1 \choose r} = 0$. Then we make the substition $n' = n-1$ and $r' = r-1$ to make it a bit neater.
Alternatively, we're picking $r+1$ of the numbers $\{1\dots n+1\}$. Let's pick our smallest number first to be $k+1$, and then pick the remaining $r$ numbers from the $n-k$ larger numbers. Once we've done this for every possible $k$ we've made all the possible choices.
The second sum adds up the number of ways of choosing any number of elements from $n$ elements. To work out how many this is, just go through each element at a time and decide to take it or leave it: two choices for each element is $2^n$ choices.
Alternatively, go back to Pascal's Triangle: apply the addition rule to every term of the sum on the LHS (just define the awkward ones to be zero). You should find that you get every term on the previous row exactly twice each, so the row sums double every time, so you get $2^n$.
Alternatively, expand $(a+b)^n$ with the binomial formula and then set $a=b=1$.
For the third sum, have a look at Binomial. Alternatively, take $2n$ things and cut them into two groups of size $n$. Then you choose 0 from one and $n$ from the other, or 1 from one and $n-1$ from the other, etc. to get: \[{2n \choose n} = {n \choose 0}{n \choose n} + {n \choose 1}{n \choose n-1} + \dots\] Then apply the symmetry formula to see that ${n \choose k}{n \choose n-k} = {n \choose k}^2$.