I tried to kill the central binomial coefficients, but they came back.

Question

Pascal's triangle contains huge numbers. I tried to "tame" it (make the numbers smaller) by "killing" the largest numbers, i.e. the central binomial coefficients: $2,6,20,70,252,924,\dots$.

That is, as I built the rows (each number being the sum of the two numbers above it), whenever a row had a centre number (except the $1$ at the very top), I made the centre number $0$ instead of adding the two numbers above it.

So instead of:

$$ 1\\ 1\quad 1\\ 1\quad \color{red}{2}\quad 1\\ 1\quad 3\quad 3\quad 1\\ 1\quad 4\quad \color{red}{6}\quad 4\quad 1\\ 1\quad 5\quad 10\quad 10\quad 5\quad 1\\ 1\quad 6\quad 15\quad \color{red}{20} \quad 15\quad 6\quad 1\\ 1\quad 7\quad 21\quad 35\quad 35\quad 21\quad 7\quad 1\\ \cdots $$

I got: $$ 1\\ 1\quad 1\\ 1\quad \color{red}{0}\quad 1\\ 1\quad 1\quad 1\quad 1\\ 1\quad 2\quad \color{red}{0}\quad 2\quad 1\\ 1\quad 3\quad 2\quad 2\quad 3\quad 1\\ 1\quad 4\quad 5\quad \color{red}{0} \quad 5\quad 4\quad 1\\ 1\quad 5\quad 9\quad 5\quad 5\quad 9\quad 5\quad 1\\ \cdots $$

I thought I had gotten rid of those nasty central binomial coefficients. But then, curious about the properties of my "tamed" version of Pascal's number, I decided to calculate the sum of each row, and I got:

$$1,2,\color{red}{2},4,\color{red}{6},12,\color{red}{20},40,\color{red}{70},140,\color{red}{252},504,\color{red}{924},\dots$$

Those central binomial coefficents found their way back!

Is there an explanation for this?

Context: Recently I've been interested in Pascal's triangle, asking questions here, here and here.

Answer 1

Let $g_n(x)$ be the generating function of row $n$ of your triangle:

$g_0(x) = 1$, $g_1(x) = 1+x$, $g_2(x) = 1 + x^2$, etc.

It seems [empirically: I don't have a proof] these satisfy the recurrence

$$4 x (1+x) n g_n(x) - 4 x n g_{n + 1}(x) - (n+3)(1+x) g_{n+2}(x) + (n + 3) g_{n+3}(x) = 0 $$

The sum of row $n$ is then $g_n(1)$, which satisfies

$$ 8 n g_n(1) - 4 n g_{n+1}(1) - 2 (n+3) g_{n+2}(1) + (n+3) g_{n+3}(1) = 0 $$

and the solution of this with initial conditions $g_0(1) = 1$, $g_1(1) = 2$, $g_2(1) = 2$ is

$$ g_{2n}(1) = {2n \choose n},\ g_{2n+1}(1) = 2 {2n \choose n} $$

EDIT: OK, here's a proof. Let $h_k(x)$ be $g_k(x)$ with the signs of the coefficients of $x^i$ for $i > k/2$ changed. Thus $$ \eqalign{h_1(x) &= 1-x \cr h_2(x) &= 1 - x^2\cr h_3(x) &= 1 + x - x^2 - x^3\cr h_4(x) &= 1 + 2 x - 2 x^3 - x^4\cr} $$ The coefficient of $x^{k}$ in $h_n(x)$ is $-$ the coefficient of $x^{n-k}$ there. It can then be seen that the coefficients of $h_n$ form the entries of a "Pascal's triangle" starting with the row $(1,-1)$; there's no need to kill the central coefficients because the symmetry makes them automatically $0$. Thus $h_n(x) = (1-x) (1+x)^{n-1}$. So the coefficient of $x^k$ in $g_n(x)$ is ${n-1 \choose k} - {n-1 \choose k-1}$ for $k < n/2$ (with ${n-1 \choose -1} = 0$) and ${n-1 \choose k-1} - {n-1 \choose k}$ for $k > n/2$. Adding these up, taking advantage of telescoping, we have $$ \eqalign{g_{2n}(1) &= 2 \sum_{k=0}^{n-1} \left({2n-1 \choose k} - {2n-1 \choose k-1}\right) = 2{2n-1 \choose n-1} = {2n \choose n}\cr g_{2n+1}(1) &= 2 \sum_{k=0}^{n} \left({2n \choose k} - {2n \choose k-1}\right) = 2{2n \choose n}\cr}$$

Answer 2

Define $\left[\begin{matrix}n\\r\\\end{matrix}\right]$ to be the number in the $n$th row, $r$th from the left, in the "tamed" Pascal's triangle. (The top row is row $0$; the leftmost number in each row is the $0$th number from the left.)

Define proposition $H_n:\left[\begin{matrix}n\\r\\\end{matrix}\right]=\left(\begin{matrix}n-1\\r\\\end{matrix}\right)-\left(\begin{matrix}n-1\\r-1\\\end{matrix}\right)$ for $1\le r\le \lfloor\frac{n}{2}\rfloor$.

---

When $n=2$, we have $\left[\begin{matrix}2\\1\\\end{matrix}\right]=0=\left(\begin{matrix}1\\1\\\end{matrix}\right)-\left(\begin{matrix}1\\0\\\end{matrix}\right)$, so $H_2$ is true.

Assume $H_k$ is true for some $k\ge2$.

$\left[\begin{matrix}k\\r\\\end{matrix}\right]=\left(\begin{matrix}k-1\\r\\\end{matrix}\right)-\left(\begin{matrix}k-1\\r-1\\\end{matrix}\right)$ for $1\le r\le \lfloor\frac{k}{2}\rfloor\text{ by assumption}$

$\begin{align} \left[\begin{matrix}k+1\\r\\\end{matrix}\right] &=\left[\begin{matrix}k\\r\\\end{matrix}\right]+\left[\begin{matrix}k\\r-1\\\end{matrix}\right]\text{for $1\le r\le \lfloor\frac{k}{2}\rfloor$ by definition of tamed Pascal's triangle}\\ &=\left(\color{red}{\left(\begin{matrix}k-1\\r\\\end{matrix}\right)}-\color{red}{\left(\begin{matrix}k-1\\r-1\\\end{matrix}\right)}\right) + \left(\color{blue}{\left(\begin{matrix}k-1\\r-1\\\end{matrix}\right)}-\color{blue}{\left(\begin{matrix}k-1\\r-2\\\end{matrix}\right)}\right)\text{for $2\le r\le\lfloor\frac{k}{2}\rfloor$, by assumption}\\ &=\left(\color{red}{\left(\begin{matrix}k-1\\r\\\end{matrix}\right)}+\color{blue}{\left(\begin{matrix}k-1\\r-1\\\end{matrix}\right)}\right) - \left(\color{red}{\left(\begin{matrix}k-1\\r-1\\\end{matrix}\right)}+\color{blue}{\left(\begin{matrix}k-1\\r-2\\\end{matrix}\right)}\right)\text{by rearranging}\\ &=\left(\begin{matrix}k\\r\\\end{matrix}\right)-\left(\begin{matrix}k\\r-1\\\end{matrix}\right)\text{by definition of Pascal's triangle} \end{align}$

We have shown that $H_k\implies\left[\begin{matrix}k+1\\r\\\end{matrix}\right]=\left(\begin{matrix}k\\r\\\end{matrix}\right)-\left(\begin{matrix}k\\r-1\\\end{matrix}\right)$ for $\color{orange}{2}\le r\le \color{orange}{\lfloor\frac{k}{2}\rfloor}$.

We're trying to get $H_{k+1}:\left[\begin{matrix}k+1\\r\\\end{matrix}\right]=\left(\begin{matrix}k\\r\\\end{matrix}\right)-\left(\begin{matrix}k\\r-1\\\end{matrix}\right)$ for $\color{orange}{1}\le r\le \color{orange}{\lfloor\frac{k+1}{2}\rfloor}$.

$\left[\begin{matrix}k+1\\1\\\end{matrix}\right]=k-1=\left(\begin{matrix}k\\1\\\end{matrix}\right)-\left(\begin{matrix}k\\1-1\\\end{matrix}\right)$ so the equation is true for $r=1$.

If $k$ is even then $\lfloor\frac{k}{2}\rfloor=\lfloor\frac{k+1}{2}\rfloor$, so we get $H_{k+1}$.

If $k$ is odd then $\left[\begin{matrix}k+1\\\lfloor\frac{k+1}{2}\rfloor\\\end{matrix}\right]=0=\left(\begin{matrix}k\\\lfloor\frac{k+1}{2}\rfloor\\\end{matrix}\right)-\left(\begin{matrix}k\\\lfloor\frac{k+1}{2}\rfloor-1\\\end{matrix}\right)$ so we still get $H_{k+1}$.

$\therefore$ By the principle of mathematical induction, $H_n$ is true for all integers $n\ge2$.

---

Using this result, we have:

$\begin{align} \sum\limits_{r=0}^n\left[\begin{matrix}n\\r\\\end{matrix}\right] &=2\times\sum\limits_{r=0}^{\lfloor n/2\rfloor}\left[\begin{matrix}n\\r\\\end{matrix}\right]\text{by symmetry}\\ &=2\times\left(\left[\begin{matrix}n\\0\\\end{matrix}\right]+\sum\limits_{r=1}^{\lfloor n/2\rfloor}\left[\begin{matrix}n\\r\\\end{matrix}\right]\right)\text{taking out $r=0$}\\ &=2\times\left(\left[\begin{matrix}n\\0\\\end{matrix}\right]+\sum\limits_{r=1}^{\lfloor n/2\rfloor}\left(\left(\begin{matrix}n-1\\r\\\end{matrix}\right)-\left(\begin{matrix}n-1\\r-1\\\end{matrix}\right)\right)\right)\text{by using the previous result}\\ &=2\times\left(\begin{matrix}n-1\\\lfloor n/2\rfloor\\\end{matrix}\right)\text{ by telescoping}\\ \end{align}$

If $n=2m$ where $m\in\mathbb{Z^+}$, then $\sum\limits_{r=0}^n\left[\begin{matrix}n\\r\\\end{matrix}\right]=\left(\begin{matrix}2m\\m\\\end{matrix}\right)$.

If $n=2m+1$ where $m\in\mathbb{Z^+}$, then $\sum\limits_{r=0}^n\left[\begin{matrix}n\\r\\\end{matrix}\right]=2\times\left(\begin{matrix}2m\\m\\\end{matrix}\right)$.

Answer 3

I came up with a simple combinatorical proof, in the spirit of the proof of the formula for the Catalan numbers. While this answer is much longer than the previous ones posted, I personally like the intuition of this more visual solution quite a lot.

I will only focus on the right side of the triangle, and show that the sum of the numbers in the right side of the $2n$-th row is $2n \choose n$.

Looking at the leftmost entry of the right side of the $2n$-th row, as you guys noted, we see the Catalan number $C_n$. This is because there are $C_n$ possible paths from the top to this square.

The Catalan numbers are often visualized with the following diagram, where $C_n$ is the number of paths from the top left corner to the bottom right corner, that do not go below the diagonal (and only go right and down).

This is in fact the same as looking at the paths on the triangles above after rotating our heads by $45$ degrees, and stretching the picture a little bit.

In the diagram, we can also find the sum of the right side of the $2n$-th row, which is $2n\choose n$, as the number of paths from the top left corner to the bottom right corner, by only taking steps to the right, or downwards (now we do allow going below the diagonal).

Now, what does the other numbers in the right side of the $2n$-th row correspond to? We can illustrate them in the same way - paths that do not cross the diagonal, but take more steps to the right than downwards. This was mentioned in a comment by @Phicar too. More precisely, the number that is $k$ places to the right of $C_n$ in our "Pascal triangle" corresponds to the number of paths starting from $L$ in the following diagram, going $n+k$ steps to the right, and $n-k$ steps down, without going below the diagonal, arriving at $P_k$.

Now, comes the question - Why does the number of paths from $L$ to $P_0$ equals to the sum of the number of paths from $L$ to any of the points $P_i$, without crossing below the red diagonal?

We will find a bijection between the first type of paths to the second type of paths. Write each path as a binary sequence with $2n$ bits, where $1$ corresponds to taking a step to the right, and $0$ corresponds to taking a step downwards. We want to find a bijective function from the set of binary sequences of length $2n$, with exactly $n$ ones and $n$ zeroes, to the set of binary sequences of length $2n$ with such that if you break the sequence to two at any point, and look at the first part, you get a sequence with more ones than zeroes (this corresponds to not going below the diagonal).

If one counts the number of paths from $L$ to $P_0$, that cross the diagonal, but do not cross the next diagonal (marked in yellow in the next diagram), he will notice that it is exactly number of paths to from $L$ to $P_1$ that do not cross the red diagonal. Similarly, the number of paths from $L$ to $P_0$ that cross the yellow diagonal, but not the next diagonal, equals to the number of paths from $L$ to $P_2$, that do not cross the red diagonal, and so on and so on (where the number of paths going all the way to the left bottom point is exactly the number of paths going to $P_3$: just one path). This gives an hint, that maybe the function that we're looking for should flip $k$ bits from $0$ to $1$, for paths that go $k$ steps below the diagonal.

This led me to the following function: Read the binary sequence bit by bit. If at any point, you read a zero such that the sequence so far had more zeroes than ones, flip this zero to a one, and keep on reading through the sequence. In the language of paths on the diagram - go with the path, and whenever you are supposed to go down below the diagonal, switch this move to a right-move, then keep on going (and flip again if you cross again). Another way to state this is - flip the first step that crosses the red diagonal, the first step that crosses the yellow diagonal, and so on.

The inverse function is pretty similar. Say you have a path that ends at $P_k$. Then its bit sequence has $2k$ more ones than zeroes. Read the sequence of bits backwards, and whenever you see a $1$-bit, such that the sequence so far has more ones than the number of zeroes plus $k$, then flip this one to a zero, and keep on going.

Verifying that these two functions are inverses of each other finishes the proof. Here is a diagram showing a blue path from $L$ to $P_0$, and the new green path from $L$ to $P_2$ that the function generates after flipping the bits. The steps marked with purple arrows are precisely the ones that got "flipped" by the function, and the ones that will be flipped back by the inverse function.

If you got this far - I really enjoyed finding this answer, and I hope that you enjoyed reading it!