Intereting Posts

Compute $\sum_{k=0}^{\infty}\frac{1}{2^{k!}}$
What is the mathematical notation for a random number in a certain range?
Where does the word “torsion” in algebra come from?
How to show $\zeta (1+\frac{1}{n})\sim n$
Show that $f(x)=\frac{x}{1+|x|}$ is uniformly continuous.
$H$ is a maximal normal subgroup of $G$ if and only if $G/H$ is simple.
A characterization of functions from $\mathbb R^n$ to $\mathbb R^m$ which are continuous
The algebraic closure of a finite field and its Galois group
Can spectrum “specify” an operator?
Equivalence of measures and $L^1$ functions
If $\int f(x) \sin{x} \cos{x}\,\mathrm dx = \frac {1}{2(b^2 – a^2)} \log f(x) +c $. Find $f(x)$
I want to calculate the limit of: $\lim_{x \to 0} \left(\frac{2^x+8^x}{2} \right)^\frac{1}{x} $
For all square matrices $A$ and $B$ of the same size, it is true that $(A+B)^2 = A^2 + 2AB + B^2$?
Why is sorting pancakes NP hard?
Understanding minimum polynomials and characteristic polynomials

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…:)

- How to factor $a^n - b^n$?
- Solving $|x-2| + |x-5|=3$
- Find all the values of $(1+i)^{(1-i)}$
- Binary expansion Unique
- How to solve inequalities with absolute values on both sides?
- Gaussian proof for the sum of squares?

- Determining whether there are solutions to the cubic polynomial equation $x^3 - x = k - k^3$ other than $x = -k$ for a given parameter $k$
- Factoring $ac$ to factor $ax^2+bx+c$
- How to prove $\frac{1}{x}=\frac{1}{a}+\frac{1}{b}+\frac{1}{c}+2\sqrt{\frac{1}{ab}+\frac{1}{ac}+\frac{1}{bc}}$
- Prove: $(a + b)^{n} \geq a^{n} + b^{n}$
- How does one actually show from associativity that one can drop parentheses?
- Easy way to find roots of the form $qi$ of a polynomial
- Prove that $\sum\limits_{k=0}^r\binom{n+k}k=\binom{n+r+1}r$ using combinatoric arguments.
- How to prove $(f \circ\ g) ^{-1} = g^{-1} \circ\ f^{-1}$? (inverse of composition)
- $xy=1 \implies $minimum $x+y=$?
- Value of $\sum\limits_n x^n$

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).

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

*Originally written for a nearly identical, and subsequently closed, question. I included the proof here as I don’t see any other post doing it the exact same way*

This is a result of the definition of the Binomial Coefficients… In symbolic form,

$${n \choose k} = \prod_{i=1}^k \frac{n+1-i}{i}$$

Just stop at $k-1$ and you get your result (with a bit of manipulation) In case you forget this, we can prove it quickly as such:

We start with the factorial definition,

$${n \choose k} = \frac{n!}{k!(n-k)!}$$

We can write this as

$${n \choose k} = \frac{n(n-1)(n-2)\cdots(2)}{k!(n-k)(n-k-1)\cdots(2)}$$

Clearly the numerator includes all terms of the denominator and then some, so we can do some canceling to get

$${n \choose k} = \frac{n(n-1)(n-2)\cdots(n-(k-1))}{k!}$$

Note that we can now directly write this in the form

$$\prod_{i=1}^k \frac{n+1-i}{i}$$

To see why, notice that the denominator multiplies all integers from $1$ to $k$ (in increasing order), and thus the denominator is $k!$

The numerator can be written as $n-(i-1)$, which will multiply all integers from $n$ to $(n-(k-1))$ (in decreasing order), and thus the numerator matches the fraction above.

- Interpolating function for a nested radical $y_x=\sqrt{a+y_{x-1}}$
- Mere coincidence? (prime factors)
- Why isn't there a continuously differentiable surjection from $I \to I \times I$?
- Unilateral Laplace Transform vs Bilateral Fourier Transform
- Can “being differentiable” imply “having continuous partial derivatives”?
- What is the cardinality of the set of all functions from $\mathbb{Z} \to \mathbb{Z}$?
- Why are continuous functions not dense in $L^\infty$?
- $(z_{2n})_{n\in \mathbb{N}}$ and $(z_{2n+1})_{n\in \mathbb{N}}$ converges to same limit. Show $(z_n)_{n\in \mathbb{N}}$ converges to the same limit.
- strictly positive in unital $C*$ algebra
- Quasicomponents and components in compact Hausdorff space
- Scalar Product for Vector Space of Monomial Symmetric Functions
- $A = B^2$ for which matrix $A$?
- Prove that if $\gcd(a,b)=1$, then $\gcd(a\cdot b,c) = \gcd(a,c)\cdot \gcd(b,c)$.
- The drawer has M different colored socks. What is the least amount of socks I that I need to draw to guarntee N pairs
- What is importance of the Bunyakovsky conjecture?