How can I prove the formula for calculating successive entries in a given row of Pascal's triangle?

I've found in Wikipedia the formula for calculating an individual row in Pascal's Triangle: $$v_c = v_{c-1}\left(\frac{r-c}{c}\right).$$ where $r = \mathrm{row}+1$, $c$ is the column starting from $0$ on left and $v_0 = 1$.

Now, I've tried to do by hand and it works, but I don't understand how to find this magic formula when I don't have access to Wikipedia...:)

-
i didn't know exactly what are best tags for this post –  nkint Mar 4 '11 at 21:00
@Arturo: thanks for editing, english is not my main language! –  nkint Mar 4 '11 at 21:09

How much do you know about the entries in Pascal's Triangle? Do you know their relation to the coefficients of the binomial expansion?

The $n+1$st row of Pascal's Triangle gives you the coefficients of the binomial $(a+b)^n$. That is, if the row is $$k_0\quad k_1\quad k_2\quad\cdots\quad k_n$$ that means that if you multiply out $(a+b)^n$, you will get $$k_0a^n + k_1a^{n-1}b + k_2a^{n-2}b^2 + \cdots + k_nb^n.$$

The coefficients are given by the binomials: $k_i = \binom{n}{i}$, where $$\binom{n}{i} = \frac{n!}{i!(n-i)!}$$ with $!$ symbolising the factorial, $r!=1\times 2\times\cdots \times r$. It is not hard to work out that $$\binom{n}{m} = \frac {n(n-1)(n-2)\cdots(n-m+1)}{m(m-1)(m-2)\cdots 1}.$$ That is, in the numerator you multiply the integers from $n$ down to $n-m+1$ ($m$ factors), and in the denominator you multiply the integers from $m$ down to $1$ (also $m$ factors).

So, suppose you already know the value $v_{c-1}$ in row $R$. This is $$\binom{R-1}{c-1} = \frac{(R-1)(R-2)\cdots(R-c)}{(c-1)(c-2)\cdots 1}.$$ The next value, $v_{c}$, is $\binom{R-1}{c}$, which is: \begin{align*} v_c&=\binom{R-1}{c}\\ & = \frac{(R-1)(R-2)\cdots(R-c-1)}{c(c-1)(c-2)\cdots 1}\\ &= \frac{(R-1-c)\Bigl((R-1)(R-2)\cdots(R-c)\Bigr)}{c\Bigl((c-1)(c-2)\cdots 1\Bigr)}\\ &= \frac{R-1-c}{i}\left(v_{c-1}\right). \end{align*} Now, remember this was in row $R$. So letting $r = \mathrm{row}-1 = R-1$, we get $$v_c = \binom{r}{c} = v_{c-1}\left(\frac{r-c}{c}\right),$$ exactly the formula given.

Added. In retrospect, this was very silly of me. If you knew that the $i$th (starting with $0$) entry in the $R$th row is given by $\binom{R}{i}$, then why would you need to remember this other formula?

So, why is the entry given by $\binom{R}{i}$? First: $\binom{R}{i}$ counts the number of ways in which you can choose $i$ things from $R$ possibilities. So, for example, $\binom{4}{2}$ tells you in how many ways you can choose two things out of four possible ones: if the four options are 1, 2, 3, and 4, you could pick 1 and 2; or 1 and 3; or 1 and 4; or 2 and 3; or 2 and 4; or 3 and 4; that is, there are six possible ways of picking two out of four. So $\binom{4}{2}=6$.

Why does the formula I gave above give the right count? If you have $R$ things to choose from, you have $R$ ways to pick out the first choice; then $R-1$ ways to pick out the second; then $R-2$ to pick out the third, and so on. You end up with $R(R-1)(R-2)\cdots(R-i+1)$ ways of choosing $i$ things. However, each choice was counted many times. In the example I gave above, I don't count "1 and 2" as different from "2 and 1". How many ways did I count each choice? Of the $i$ choices I made, I could have selected any of the $i$ things first; then any of the remaining $i-1$ second; then any of the remaining $i-2$ as my third choice, etc. That is, each choice of $i$ things can be made in $i(i-1)(i-2)\cdots (2)(1)$ ways. So, each choice was counted that many times; to get the right count, we divide the original count by the factor by which we overcounted, so $$\binom{R}{i}=\frac{R(R-1)(R-2)\cdots(R-i+1)}{i(i-1)\cdots 2\times 1}.$$ This is the formula I gave above.

One small wrinkle: what happens when $i=0$? Well, in how many ways you make no choices? Just one: don't do anything. So $\binom{R}{0}=1$ always.

And, why is this "number of ways to pick" related to the coefficients of $(a+b)^n$? Imagine that you need to do the product. Write them down one after the other, as if you were writing down a sum: \begin{align*} a &+b\\ a &+b\\ a &+b\\ &\vdots\\ a &+ b\\ a &+b \end{align*} You need to do all the possible products of each element with the elements of the other rows.

How many times will you get $a^n$? Just once, because the only way to get $a^n$ is by multiplying all the $a$s together. How many times will you get $a^{n-1}b$? Well, you get $a^{n-1}b$ if you pick one $b$ in one row, and multiply it by all the $a$s in the other rows. You have $n$ different choices for the one $b$, so there are $\binom{n}{1}$ ways of getting $a^{n-1}b$. How many ways can you get $a^{n-2}b^2$? You have to pick two which rows will provide you with the two $b$s. There are $n$ possibilities, you need to pick $2$, so it's $\binom{n}{2}$ ways.

And so on. How many times will you get $a^{n-i}b^i$? You need to pick $i$ rows to provide you with the $b$s, and there are $\binom{n}{i}$ ways to pick them.

So when we write out $(a+b)^n$, the monomial $a^{n-i}b^i$ will show up $\binom{n}{i}$ times. So that's the coefficient.

This means that the $i$th entry in the $(n+1)$st row of Pascal's triangle is $\binom{n}{i}$, which agrees with what we said above.

And now that you know this, this is really the easy formula to remember, not the "magic formula" form Wikipedia.

-

Sometimes memorizing a formula is easiest, sometimes it's easier to derive the formula as needed than memorize it (too many plus or minus 1's), but sometimes just remembering a concrete pattern works. For example, if you want to compute the row for

$${6 \choose m}$$

which is

$$1,6,15,20,15,6,1$$

start with 1 and multiply by $\frac{6}{1}$. Then to get the next one multiply by $\frac{5}{2}$, the next $\frac{4}{3}$... and so on, the numerator going down by one each time, the denominator up by one each time.

$$1 \ \ \frac{6}{1} \ \ 6 \ \ \frac{5}{2} \ \ 15 \ \ \frac{4}{3} \ \ 20 \ \ \frac{3}{4} \ \ 15 \ \ \frac{2}{5} \ \ 6 \ \ \frac{1}{6} \ \ 1$$

Note that the sequence is reversible because by the time you get to the middle of the sequence the fractions themselves are the inverse of their mirrored item.

Try it for 14:

$$1 \ \ \frac{14}{1} \ \ 14 \ \ \frac{13}{2} \ \ 91 \ \ \frac{12}{3} \ \ 364 \ \ \frac{11}{4} \ \ 1001 \ \ \frac{10}{5} \ \ 2002 \ \ \frac{9}{6} \ \ 3003 \ldots$$

The numbers always cancel, either by the fraction itself or with some factors of the value so far. This is actually a good way to compute binomial coefficients exactly by computer in keeping all the intermediate computations as low as possible (instead of using the factorials).

-
good tricky and mnemonic way! –  nkint Mar 6 '11 at 14:13

Just a very short derivation:
If $\binom r i$ are the i'th entries in the r'th row, then this means $\frac {r!}{i! (r-i)!}$ for the i'th entry. Two consecutive entries are then connected by $$\frac {r!}{(i+1)! (r-(i+1))!} = \frac {r!}{(i+1)*i! \frac{(r-i)!}{r-i}} = \frac {r!}{i! (r-i)!}*\frac{r-i}{i+1}$$

-