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.
A: Lemma: ${n+1\choose k+1}={n\choose k+1}+{n\choose k} $
Proof: Fix an element in $n+1$ elements.
If you will not choose it you have ${n\choose k+1}$ choices.
If you will choose it you have ${n\choose k} $ choices.Thus ,we are done.
If you apply this lemma untill you reach $k+1$,you will get;
$${k+1\choose k+1}+{k+1\choose k}+{k+2\choose k}+...{n\choose k}={n+1\choose k+1}$$
Since,${k+1\choose k+1}={k\choose k}$ we are done.
A: I have solved this question using the basic binomial theorem of Grade 11 Mathematics (The grade I am in right now...) Hope you understand it.
We are trying to find the coefficient of $x^k$ in the expansion of
$$f(x)=(1+x)^k+(1+x)^{k+1}+\cdots+(1+x)^n$$
This will give us
$${k\choose k}+{k+1\choose k}+\cdots +{n\choose k}$$
So let's find $f(x)$. This is a GP, so
$$
\begin{split}
f(x)&=\frac{(1+x)^k[(1+x)^{n-k+1}-1]}{(1+x)-1}\\
&=\frac{(1+x)^{n+1}-(1+x)^k}{x}\\
\end{split}
$$
Now we need to find the coefficient of $x^k$ in the above expansion of $f(x)$. Equivalently, this is the coefficient of $x^{k+1}$ in
$$(1+x)^{n+1}-(1+x)^k$$
which is clearly equal to ${n+1\choose k+1}$ by the binomial theorem. Therefore
$${k\choose k}+{k+1\choose k}+\cdots +{n\choose k}={n+1\choose k+1}$$
Note: Original Answer at https://i.stack.imgur.com/Cd9Ir.jpg
