Proving binomial coefficient formula based on Pascal's triangle I am trying to practice proving things, and I came across one I wasn't sure about.
We already know that $\binom{n}{k}$ is the sum of the two corresponding "parent" entities in Pascal's triangle, which we can define as $\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$ with $\binom{n}{0} = 1$.
But how can we go from that to the typical representation $\frac{n!}{k!(n-k)!}$ in an easily understood and intuitive way?
 A: If you choose $k$ persons out of $n$ (for convenience standing in a row), then you can choose all $k$ out of the most left $n-1$ persons or you can choose the person at the right together with $k-1$ persons out of the remaining $n-1$ persons: $$\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}$$
A: As per your latest comment below Paolo's answer, I am going to assume that you are asking: 
"Prove that the $k$-th entry of the $n$-th row of Pascal's Triangle (which we will call $a_{n,k}$) is equal to $\frac{n!}{k!(n-k)!}$ (note that we are beginning our counting at $0$ for both $n$ and $k$)."
To wit, we have $a_{0,0} = 1$, with $a_{n,0} = a_{n,n} = 1$ for all $n$ and $a_{n,k} = a_{n-1,k-1}+a_{n-1,k}$ for $1 \leq k \leq n-1$ (this is the defining and most glaringly obvious property of Pascal's Triangle).
As Paolo stated in the comments, this will be straightforward induction.
As $\frac{0!}{0!(0-0)!} = \frac{0!}{0!0!} = \frac{1}{1\cdot 1} = 1$, I'm sure we can all agree that the base case checks out.
Now we assume that $a_{i,j} = \frac{i!}{j!(i-j)!}$ for $1 \leq j \leq i-1$ for all $i$ less than some fixed $n > 1$ (we needn't worry about the "outer" entries, as they are fixed at $1$, which is the value of $\frac{m!}{0!(m-0)!}=\frac{m!}{m!(m-m)!}$ for all $m \in \mathbb{N}$). 
For $1 \leq k \leq n-1$ we have
\begin{align}
a_{n,k} &= a_{n-1,k-1}+a_{n-1,k} 
\\ &= \frac{(n-1)!}{(k-1)!((n-1)-(k-1))!}+\frac{(n-1)!}{k!((n-1)-k)!}
\\ &= \frac{(n-1)!}{(k-1)!(n-k)!}+\frac{(n-1)!}{k!(n-k-1)!}
\\ &= \frac{k(n-1)!}{k!(n-k)!}+\frac{(n-k)(n-1)!}{k!(n-k)!}
\\ &= \frac{k(n-1)!+(n-k)(n-1)!}{k!(n-k)!}
\\ &= \frac{(k+n-k)(n-1)!}{k!(n-k)!} = \frac{n(n-1)!}{k!(n-k)!} = \frac{n!}{k!(n-k)!}
\end{align}
I know this isn't "intuitive" per se (it really depends on that word means to you), but it is fairly straightforward.
A: The easiest way to prove the formula with factorials is to prove this second fundamental relation:

If $n,k\ge 1$, then $\;\dbinom nk=\dfrac nk\dbinom{n-1}{k-1}.$

This relation is obtained by comparing the binomial developments of both sides of the equality:
$$\bigl((1+x)^n\bigr)'=n(1+x)^{n-1}.$$
A: Here is an algebraic demonstration.
Assume Pascal's triangle creates the binomial coefficients on the $n^{th}$ row.
We can then look at
$(1 + x)^n = \sum_{k = 0}^{n} \binom{n}{k} x^k$
and state that the coefficients match up with Pascal's triangle.
Now multiply both sides by $(1 + x)$.
The left side is the binomial raised to the $(n+1)$ power.
The right side becomes
$\sum_{k = 0}^{n} \binom{n}{k} x^k + \sum_{k = 0}^{n} \binom{n}{k} x^{k+1}$
or
$\binom{n}{0}x^0 + \sum_{k = 1}^{n} [\binom{n}{k}+\binom{n}{k-1}] x^{k} +  \binom{n}{n}x^{n+1}$
But this will lay out exactly on the next row of Pascal's triangle.
Incidentally, this shows that
(1) $\binom{n+1}{k} = \binom{n}{k}+\binom{n}{k-1}$
A: $\binom{n}{k}$ is just a symbol representing in how many ways you can choose $k$ objects among $n$ identical ones. Reason one moment about its meaning: suppose you do $n$ consecutive draws (so in $n!$ ways) and you choose the first $k$ ones. In how many ways you choose the first $k$ ones? As the product of the number of permutations of chosen ones, and not chosen ones, i.e. $k!(n-k)!$. That's how you get
$$
\binom{n}{k}=\frac{n!}{k!(n-k)!}
$$
A: I think I understand what you want. You don't really want a proof of the Pascal recurrence, you already know the answer to that. Instead, you want a tool that can help you solve similar recurrences and want to see it in action on the Pascal recurrence. Here is an attempt at such a tool:
We know that the Pascal recurrence is: $g(n,k)=g(n-1,k-1)+g(n-1,k)$
Define the generating function:
$$G_n(x) = \sum\limits_{k=0}^\infty g(n,k) x^k$$
$$=g(n,0) + \sum\limits_{k=1}^\infty g(n,k)x^k$$
$$=g(n,0)+\sum\limits_{k=1}^\infty (g(n-1,k-1)+g(n-1,k))x^k$$
$$=g(n,0)+\sum\limits_{k=1}^\infty g(n-1,k-1)x^k + \sum\limits_{k=1}^\infty g(n-1,k)x^k$$
$$=g(n,0)+x \sum\limits_{k=1}^\infty g(n-1,k-1)x^{k-1} + \sum\limits_{k=1}^\infty g(n-1,k)x^k$$
It is at this point we invoke the starting condition: $g(n,0)=1$, allowing us to absorb the first term into the third term. For the second term, re-index $k-1$ to $k$. This gives us:
$$G_n(x)=xG_{n-1}(x)+G_{n-1}(x) = G_{n-1}(1+x)$$
Again invoking the base case we get: $G_0(x)=1$
It becomes easy to see then that:
$$G_n(x)=(1+x)^n$$
We have just connected the Pascal recurrence to the Binomial theorem and corresponding coefficients. Note that this approach is similar to exercise 12-4 of the book, "Introduction to Algorithms" by Cormen et.al.
Here, this method is applied to another similar recurrence: https://math.stackexchange.com/a/3718807/155881
