Let $[n+1]$ be the set defined by $[n+1]=\{1,2,\ldots,n+1\}$.
Call a subset of $[n+1]$ with $r+1$ distinct elements an $(r+1)$-subset. How many $(r+1)$-subsets of $[n+1]$ have $(k+1)$ as their largest element?
This seem fairly facile, so I am concerned that I am doing it wrong. By definition, $[n+1]$ is a bounded set. If $(r+1)$ is a subset of $[n+1]$, then $(r+1)$ is bounded as well. Denote that bound as $k+1$ s.t. $k \geq r_0 \forall r_0 \in (r+1)$.
Is anything wrong here?
Additionally, I am supposed to deduce that
$$\sum^n_{k=r}{k\choose r}={n+1\choose r+1}.$$
I have no idea where to start for this one.
EDIT: Using the hints given by Hagen von Eitzen, I claim that the total number of subsets of $[n+1]$ that have $(k+1)$ as their largest element is $k$. Note that an $(r+1)$-element subset of $[n+1]$ is an $(r+1)$-element subset of $[n+1]$ that has $k+1$ as maximal elelment for exactly one k∈{r,…,n}.
I am fairly sure that I can prove this by induction. Can someone suggest anything for the second half and whether I did the first half correctly?
Hint: If you remove the known element $k+1$ from such a subset it becomes an arbitrary $r$-element subset of $[k]$.
Second Hint: An $(r+1)$-element subset of $[n+1]$ is an $(r+1)$-element subset of $[n+1]$ that has $k+1$ as maximal elelment for exactly one $k\in\{r,\ldots,n\}$.