There is an infinite grid of numbers. The first row contains all the natural numbers in ascending order. Any other number in this grid is the sum of those numbers from the row above it which do not exceed the number above it.

Given two positive integers n and k such that n ≥ k, where in the grid can we find the binomial coefficient C(n, k)?

[SOLVED]

2 comments

Ilan Mayer solved this puzzle:

From the definition of the grid,

\begin{align*} g(r, m) &= g(r, m - 1) + g(r - 1, m) \text{ for } r \gt 1 \text{ and } m \gt 1 \\ g(1, m) &= m \\ g(r, 1) &= 1 \end{align*}

Thus, the general formula for the elements of the grid is

\[ g(r, m) = \binom{r + m - 1}{r - 1} \]

This can be proven by induction.

For the first row, \(g(1, m) = m = \binom{m}{m - 1}\). For the first column, \(g(r, 1) = 1 = \binom{n}{0}\). If the general formula is true for \(g(r, m - 1)\) and \(g(r - 1, m)\), then

\begin{align*} g(r, m) &= g(r, m - 1) + g(r - 1, m) \\ &= \binom{r + m - 2}{m - 2} + \binom{r + m - 2}{m - 1} \\ &= \frac{(r + m - 2)!}{r! (m - 2)!} + \frac{(r + m - 2)!}{(r - 1)! (m - 1)!} \\ &= \frac{(r + m - 2)!}{(r - 1)! (m - 2)!} \left(\frac{1}{r} + \frac{1}{m - 1}\right) \\ &= \frac{(r + m - 2)!}{(r - 1)! (m - 2)!} \cdot \frac{r + m - 1}{r(m - 1)} \\ &= \frac{(r + m - 1)!}{r! (m - 1)!} \\ &= \binom{r + m - 1}{m - 1} \end{align*}

If \(g(r, m) = \binom{n}{k}\), then

\begin{align*} \binom{r + m - 1}{m - 1} &= \binom{n}{k} \\ r = n - k, m &= k + 1 \end{align*}

For \(n \lt k\), \(\binom{n}{k} = g(n - k, k + 1)\).
For \(n = k\), \(\binom{n}{k} = 1 = g(1, 1)\).

Susam Pal from cotpi added:

Let the number in the \(r\)th row and \(c\)th column of the grid be \(f(r, c)\). We can show that every row contains a strictly monotonically increasing sequence of positive integers. This can be done by proving that \(f(r, c) \lt f(r, c + 1)\) for integers \(r \geqslant 1\) and \(c \geqslant 1\). This is clearly true for the first row since \(f(r, c) = c\) and \(f(r, c + 1) = c + 1\). If we assume that this is true for \((r - 1)\)th row, we get,

\begin{align*} & 0 \lt f(r - 1, c + 1) \\ & \Rightarrow \sum_{i=1}^c f(r - 1, i) \lt \sum_{i=1}^{c} f(r - 1, i) + f(r - 1, c + 1) \\ & \Rightarrow \sum_{i=1}^c f(r - 1, i) \lt \sum_{i=1}^{c} f(r - 1, c + 1) \\ & \Rightarrow f(r - 1, c) \lt f(r - 1, c + 1) \end{align*}

So, as per the description of the grid in the problem statement, for \(r \gt 1\) and \(c \gt 1\), \begin{align*} f(r, c) &= \sum_{i=1}^c f(r - 1, i)\\ &= \sum_{i=1}^{c - 1} f(r - 1, i) + f(r - 1, c) \\ &= f(r, c - 1) + f(r - 1, c) \\ \end{align*}

Also,

\begin{align*} f(1, c) &= 1 \\ f(r, 1) &= r \end{align*}

Using the principle of mathematical induction, it can be shown that \(f(r, c) = \binom{r + c - 1}{r}\). This is certainly true for \(r = 1\) since \(f(1, c) = c = \binom{c}{1} \). This is true for \(c = 1\) as well because \(f(r, 1) = 1 = \binom{r}{r}\). Let us assume that it is true for \(r = r' - 1\) as well as \(c = c' - 1\) where \(r'\) and \(c'\) are positive integers.

\begin{align*} f(r', c') &= f(r', c' - 1) + f(r' - 1, c') \\ &= \binom{r' + c' - 2}{r'} + \binom{r' + c' - 2}{r' - 1} \\ &= \binom{r' + c' - 1}{r'} \\ \end{align*}

Hence, by the principle of mathematical induction, \(f(r, c) = \binom{r + c - 1}{r}\) for any positive integer \(r\).

So, if we are trying to find \(\binom{n}{k}\), we want to find \(r\) and \(c\) such that \(f(r, c) = \binom{n}{k}\).

\begin{align*} f(r, c) &= \binom{n}{k} \\ \binom{r + c - 1}{r} &= \binom{n}{k} \\ r = k, c &= n - k + 1 \end{align*}

Since, \(\binom{r + c - 1}{r} = \binom{r + c - 1}{c - 1}\), we also get:

\begin{align*} f(r, c) &= \binom{n}{k} \\ \binom{r + c - 1}{c - 1} &= \binom{n}{k} \\ r = n - k, c &= k + 1 \end{align*}

So, \(\binom{n}{k}\) can be found at \(k\)th row and \((n - k + 1)\)th column for \(k \leqslant n\) as well as \((n - k)\)th row and \((k + 1)\)th column for \(k \lt n\).

Credit

This is an original puzzle from cotpi.

Further reading

The following is a list of resources on related topics:

Post a comment

RSS