0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Actually $\binom{n}{k}$ is the "typical" representation, and it is understood to represent the (integer) $\frac{n!}{k!(n-k)!}$. $\endgroup$ – 727 Aug 16 '15 at 19:39
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is there no way to prove the relationship between Pascal's triangle and binomial coefficients other than induction where we assume the correct formula from the beginning? $\endgroup$ – user81363 Aug 16 '15 at 20:47
  • 1
    $\begingroup$ To clarify where I am coming from: I completely understand the intuitive explanation behind the factorial representation if we're talking about "combinations" as the way to choose items. But I am wondering how we can prove the connection between the triangle and the binomial formula other than going "well the values are the same, they must be equivalent, and we can prove this after the fact with induction given that we know the answer." If that's the way it is, I can accept that -- but I am wondering if there's another way. $\endgroup$ – user81363 Aug 16 '15 at 20:50
  • $\begingroup$ @user81363 It really depends on how much prior information you're assuming. Also, you're never just given the triangle. Rather, you are given the first entry, and a set of rules for constructing the rest. So you really can just think of it as a triangular array constructed in a recursive way, independent of any connections to the Binomial Theorem, combinations, or any other of the myriad of additional properties it exhibits. And the stock, standard way to prove properties of recursively-built sequences or arrays is to use induction. Deeper connections are established independently. $\endgroup$ – 727 Aug 16 '15 at 21:02
  • $\begingroup$ @user81363 After your comment I thought I might peruse the Wikipedia page to see if here might be something close to what I think you might be looking for. About 1/4 of that way into the section "Binomial Expansions", there is a sentence that begins with "To see how the binomial theorem relates to the simple construction of Pascal's triangle ... ". I thought this might be promising in your case? en.wikipedia.org/wiki/Pascal%27s_triangle#Binomial_expansions (Apologies in advance if I'm simply reposting something that you have already read.) $\endgroup$ – 727 Aug 16 '15 at 21:09
  • $\begingroup$ "And the stock, standard way to prove properties of recursively-built sequences or arrays is to use induction." So if all you had was the recursive relationship to explain the coefficients, how then do you go from that to "let's assume formula $n!/(k!(n-k)!)$"? $\endgroup$ – user81363 Aug 16 '15 at 21:20
3
$\begingroup$

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}$$

$\endgroup$
1
$\begingroup$

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}.$$

$\endgroup$
1
$\begingroup$

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}$

$\endgroup$
  • $\begingroup$ Spoiler Alert: If you want to prove (1) using a counting argument, it has already been done. See the answer provided by @drhab . $\endgroup$ – CopyPasteIt May 5 '17 at 0:32
0
$\begingroup$

$\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)!} $$

$\endgroup$
  • $\begingroup$ I am asking how you get from Pascal's Triangle's representation to the factorial representation $\endgroup$ – user81363 Aug 16 '15 at 19:40
  • $\begingroup$ As in, pretend all you knew was Pascal's Triangle and that you didn't know it represented "how many ways you can choose k objects among n identical ones" $\endgroup$ – user81363 Aug 16 '15 at 19:41
  • $\begingroup$ Then make your question precise. If you want, it is clear why the Pascal identity holds, without recalling its "factorial representation": the number of ways you can choose $k$ objects among $n$ ones is the same as choosing $k-1$ among the first $n-1$ (and the last one) plus the number of ways of choosing $k$ among the first $n-1$ (and not the last one). So, what's the point here? $\endgroup$ – Paolo Leonetti Aug 16 '15 at 19:44
  • $\begingroup$ @user81363 are you asking something along the lines of "Let $a_{n,k}$ be the $k$-th entry in the $n$-th row of a triangular array (where we are counting from $0$), with the property that $a_{n,0} = a_{n,n+1} = 1$ for all $n$, and $a_{n,k} = a_{n-1,k-1}+a_{n-1,k}$ for $1 \leq k \leq n$, with $a_{0,0} = 1$. Show that $a_{n,k} = \frac{n!}{k!(n-k)!}$."? $\endgroup$ – 727 Aug 16 '15 at 19:47
  • 1
    $\begingroup$ In that case, it would be enough a mechanic induction; but since he asked for an intuitive solution, I have chosen its real interpretation.. $\endgroup$ – Paolo Leonetti Aug 16 '15 at 19:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.