Q:

Prove ${k \choose k} + {k + 1 \choose k} + {k + 2 \choose k} + ... + {n \choose k} = {n + 1 \choose k+1}$

I have the following problem at discrete maths subject on college. 
Let's say that $k, n ∈ {0, 1, 2, 3, ...}$ and $k <= n$.
Prove the following:
${k \choose k} + {k + 1 \choose k} + {k + 2 \choose k} + ... + {n \choose k} = {n + 1 \choose k+1}$

A:

We have $n+1$ people lined up om a row, and want to choose $k+1$ of them to get a prize.  This can be done in $\binom{n+1}{k+1}$ ways.  We do the counting another way.   
We can choose the first person,  and $k$ from the last $n$. There are $\binom{n}{k}$ ways to do this.  
We can skip the first person, choose the second, and pick $k$ from the last $n-1$.
There are $\binom{n-1}{k}$ ways to do this. 
We can skip the first two, choose the third, and $k$ more.  
And so on.  
Finally, we skip the first $(n+1)-(k+1)$, choose the next, and $k$ from the last $k$. There are $\binom{k}{k}$ ways to do this.  
We get the desired sum, backwards.  

A:

The relation in Pascal's Triangle says
$$
\binom{j}{k}=\binom{j+1}{k+1}-\binom{j}{k+1}
$$
Sum in $j$ from $k$ to $n$:
$$
\begin{align}
\sum_{j=k}^n\binom{j}{k}
&=\sum_{j=k}^n\left[\binom{j+1}{k+1}-\binom{j}{k+1}\right]\\
&=\sum_{j=k+1}^{n+1}\binom{j}{k+1}-\sum_{j=k}^n\binom{j}{k+1}\\
&=\binom{n+1}{k+1}-\binom{k}{k+1}\\
&=\binom{n+1}{k+1}
\end{align}
$$

A:

Let $k \in \mathbb{N}$.
Base: $n=k$: $\binom{n}{k}=\binom{n}{n}=1=\binom{n+1}{n+1}=\binom{n+1}{k+1}$.
Hypothesis: $\exists (n-1) \in \mathbb{N}: (n-1) \geq k \land \sum_{i=k}^{n-1} \binom{i}{k} = \binom{n}{k+1} =  \binom{(n-1)+1}{k+1}$
Step: $$\sum_{i=k}^{n} \binom{i}{k} = \binom{n}{k+1} + \binom{n}{k}  = \frac{n!}{(k+1)(n-k-1)!k!}  + \frac{n!}{(n-k)(n-k-1)!k!}  = \frac{(n-k+k+1)n!}{(n-k)!(k+1)!}   = \frac{(n+1)!}{(n-k)!(k+1)!}  = \binom{n+1}{k+1}$$
And the proposition is proved using induction.   
Notice that the Step is actually proof of Pascal's rule.