An interesting property of binomial coefficients that I couldn't prove

Question

So when I was trying to prove the argument in this link I've come up with something.

When you extract the left term from the right term, you get the term under them. What is interesting is that as you can see it follows a pattern similar to binomial coefficients such $1,2,1 - 1,3,3,1 - 1,4,6,4,1$ etc. and when $k=0$ in the first layer, all terms are equal to $0$ and when $k=1$ in the second layer all terms are equal to $0$, and when $k = 2$ in the third layer all terms are equal to $0$ and so on.

$1^k-0^k \qquad\qquad 2^k-1^k \qquad\qquad 3^k-2^k \qquad\qquad 4^k-3^k$ $\qquad 2^k-2.1^k+0^k \qquad 3^k-2.2^k+1^k \qquad 4^k-2.3^k+2^k$ $\quad\quad\quad 3^k-3.2^k+3.1^k-0^k \quad\quad 4^k-3.3^k+3.2^k-1^k$ $\qquad \qquad \qquad 4^k-4.3^k+6.2^k-4.1^k+0^k$

So, I really couldn't figure out why. If I can prove it I will be able to prove the argument in the link I posted.

Answer 1

This is what happens when you apply finite differences to any sequence. Here is some useful notation. If $a_n$ is a sequence, its forward difference is the sequence

$$\Delta a_n = a_{n+1} - a_n.$$

(The notation should not be read as "$\Delta$ of $a_n$," but as "the $n^{th}$ term of the sequence $\Delta a$.") For example, if $a_n = n^2$, then

$$\Delta a_n = (n+1)^2 - n^2 = 2n + 1.$$

The reason this notation is so useful is that it can be iterated: we can inductively define

$$\Delta^k a_n = \Delta^{k-1} a_{n+1} - \Delta^{k-1} a_n$$

and these are the differences of the differences. For example,

$$\Delta^2 a_n = (a_{n+2} - a_{n+1}) - (a_{n+1} - a_n) = a_{n+1} - 2 a_{n+1} + a_n$$

and

$$\Delta^3 a_n = a_{n+3} - 3 a_{n+2} + 3 a_{n+1} - a_n.$$

In general, it turns out that

$$\Delta^k a_n = \sum_{i=0}^k (-1)^i {k \choose i} a_{n+k-i}$$

and this is the binomial coefficient pattern you observe. You can prove this by induction, but to my mind, the cleanest way to prove it - the way that lets you "see it at a glance" - is to use the concept of operators.

"Forward difference" is an operator: it eats up a sequence and spits out a sequence, kind of like differentiation, which eats up a function and spits out another function. Operators form a ring, an infinite-dimensional generalization of rings of matrices, and in particular you can add and multiply them (addition is pointwise, multiplication is composition).

The $k^{th}$ forward difference operator is then literally the product $\Delta^k$ of $k$ copies of the forward difference operator in this ring. The significance of this observation is that $\Delta$ can be written as a difference of two operators, the identity operator $I$, which does nothing:

$$I a_n = a_n$$

and the forward shift operator, which shifts a sequence forward:

$$S a_n = a_{n+1}.$$

The precise relationship is that $\Delta = S - I$, and using the binomial theorem we can now write

$$\Delta^k = (S - I)^k = \sum_{i=0}^k {k \choose i} (-1)^i S^{k-i}$$

which is exactly the desired result.

Answer 2

Nice observation -- you have found one of the fundamental properties of finite differences.

Let me rewrite your question in a more "functional" way:

Fix an abelian group $A$, written additively. (For instance, $A$ can be $\mathbb{Z}$ or $\mathbb{Q}$ or $\mathbb{C}$. Either choice works for your question, so if you are not on friendly terms with groups, you can just set $A = \mathbb{Z}$.)

Let $\mathbb{N} = \left\{0,1,2,\ldots\right\}$.

For every $n \in \mathbb{N}$, the set $A^n$ consists of all $n$-tuples of elements of $A$. Let $A^*$ denote the disjoint union $\bigsqcup\limits_{n \in \mathbb{N}} A^n$ of these sets. Thus, $A^*$ is the set of all finite sequences of elements of $A$.

Now, we define a map $\Delta : A^* \to A^*$ by \begin{align} \Delta \left(a_1, a_2, \ldots, a_n\right) = \left(a_2 - a_1, a_3 - a_2, \ldots, a_n - a_{n-1}\right) . \end{align} (For $n = 0$, the right hand side has to be understood as the empty sequence $\left(\right)$; thus, $\Delta \left(\right) = \left(\right)$.)

For example, $\Delta\left(2,6,4,4\right) = \left(6-2,4-6,4-4\right) = \left(4,-2,0\right)$. Clearly, $\Delta$ always makes a sequence shorter by $1$, unless it was empty to begin with.

In your picture, $\Delta$ is the map that transforms each row into the next row. Thus, your two claims are the following:

Theorem 1. If $k \in \mathbb{N}$, $n \in \mathbb{N}$ and $A = \mathbb{Z}$, then the sequence $\Delta^{k+1}\left(1^k, 2^k, \ldots, n^k\right)$ consists solely of zeroes.

Theorem 2. If $k \in \mathbb{N}$, $n \in \mathbb{N}$, $\left(a_1, a_2, \ldots, a_n\right) \in A^n$ and $p \in \left\{1,2,\ldots,n-k\right\}$, then the $p$-th entry of the sequence $\Delta^k \left(a_1, a_2, \ldots, a_n\right)$ is $\sum\limits_{i=0}^k \left(-1\right)^{k-i} \dbinom{k}{i} a_{p+i}$.

Theorem 1 was what the OP on reddit came up with, while Theorem 2 is your "pattern similar to binomial coefficients".

Proving Theorem 2

Proof of Theorem 2. Before we prove Theorem 2, let me explain my convention for binomial coefficients: For any two integers $k$ and $i$, I define $\dbinom{k}{i}$ to be $ \begin{cases} \dfrac{k\left( k-1\right) \cdots\left( k-i+1\right) }{i!}, & \text{if }i\geq0;\\ 0, & \text{if }i<0 \end{cases} $. You may have a different definition of binomial coefficients in mind, but it should agree with mine at least in the cases that matter for Theorem 2 (i.e., in the cases where $0\leq i\leq k$). My definition (really the definition in Graham/Knuth/Patashnik and most other places) has the neat advantage that the classical recurrence relation $\dbinom{K}{i-1} +\dbinom{K}{i}=\dbinom{K+1}{i}$ holds for any two integers $K$ and $i$ (and not just for $K\geq 0$ and $i\geq 1$).

We shall prove Theorem 2 by induction over $k$.

The induction base (i.e., the case $k=0$) is clear: The $p$-th entry of the sequence $\Delta^{0}\left( a_{1},a_{2},\ldots,a_{n}\right) $ is $a_{p}$ (since $\Delta^0 = \operatorname{id}$), and thus equal to the sum $\sum\limits_{i=0}^{0}\left( -1\right) ^{0-i} \dbinom{0}{i}a_{p+i}$ (which is just a complicated way to say $a_{p}$).

Now to the induction step. Fix a $K\in\mathbb{N}$. Assume that Theorem 2 holds for $k=K$. We must prove that Theorem 2 holds for $k=K+1$ as well.

Fix $n\in\mathbb{N}$, $\left( a_{1},a_{2},\ldots,a_{n}\right) \in A^{n}$ and $p\in\left\{ 1,2,\ldots,n-\left( K+1\right) \right\} $. Then, both $p$ and $p+1$ belong to $\left\{ 1,2,\ldots,n-K\right\} $. Hence, we can apply Theorem 2 to $k=K$ (because we assumed that Theorem 2 holds for $k=K$), and thus obtain that

(1) the $p$-th entry of the sequence $\Delta^{K}\left( a_{1},a_{2} ,\ldots,a_{n}\right) $ is $\sum\limits_{i=0}^{K}\left( -1\right) ^{K-i}\dbinom{K}{i}a_{p+i}$.

But we can also apply Theorem 2 to $K$ and $p+1$ instead of $k$ and $p$ (again since we assumed that Theorem 2 holds for $k=K$), and thus obtain that

(2) the $\left( p+1\right) $-th entry of the sequence $\Delta^{K}\left( a_{1},a_{2},\ldots,a_{n}\right) $ is $\sum\limits_{i=0}^{K}\left( -1\right) ^{K-i}\dbinom{K}{i}a_{p+1+i}$.

Let us rewrite (1) and (2) in forms more suitable for us (essentially "pushing them closer to the inductive goal"). From (1), we know that

$\left( \text{the }p\text{-th entry of the sequence }\Delta^{K}\left( a_{1},a_{2},\ldots,a_{n}\right) \right) $

$= \sum\limits_{i=0}^{K}\left( -1\right) ^{K-i}\dbinom{K}{i}a_{p+i}$

$= \sum\limits_{i=0}^{K+1}\left( -1\right) ^{K-i}\dbinom{K}{i} a_{p+i} - \left( -1\right) ^{K - \left(K+1\right)} \underbrace{\dbinom{K}{K+1}}_{=0} a_{p+K+1}$

$= \sum\limits_{i=0}^{K+1}\left( -1\right) ^{K-i}\dbinom{K}{i} a_{p+i} - \underbrace{\left( -1\right) ^{K - \left(K+1\right)} 0 a_{p+K+1}}_{=0}$

(3) $= \sum\limits_{i=0}^{K+1}\left( -1\right) ^{K-i}\dbinom{K}{i} a_{p+i}$.

From (2), we have

$\left( \text{the }\left( p+1\right) \text{-th entry of the sequence }\Delta^{K}\left( a_{1},a_{2},\ldots,a_{n}\right) \right) $

$= \sum\limits_{i=0}^{K}\left( -1\right) ^{K-i}\dbinom{K}{i}a_{p+1+i}$

$= \sum\limits_{i=-1}^{K}\left( -1\right) ^{K-i}\dbinom{K} {i}a_{p+1+i}-\left( -1\right) ^{K - \left(-1\right)} \underbrace{\dbinom{K}{-1}} _{=0}a_{p+1+\left( -1\right) }$

$= \sum\limits_{i=-1}^{K}\left( -1\right) ^{K-i}\dbinom{K} {i}a_{p+1+i}-\underbrace{\left( -1\right) ^{K - \left(-1\right)} 0 a_{p+1+\left( -1\right) }}_{=0}$

$= \sum\limits_{i=-1}^{K}\left( -1\right) ^{K-i}\dbinom{K} {i}a_{p+1+i}$

$=\sum\limits_{i=0}^{K+1}\underbrace{\left( -1\right) ^{K-\left( i-1\right) }}_{=\left( -1\right) ^{\left( K+1\right) -i}}\dbinom{K} {i-1}\underbrace{a_{p+1+\left( i-1\right) }}_{=a_{p+i}}$

(here, we substituted $i-1$ for $i$ in the sum)

(4) $=\sum\limits_{i=0}^{K+1}\left( -1\right) ^{\left( K+1\right) -i} \dbinom{K}{i-1}a_{p+i}$.

Now, $\Delta^{K+1}\left( a_{1},a_{2},\ldots,a_{n}\right) =\Delta\left( \Delta^{K}\left( a_{1},a_{2},\ldots,a_{n}\right) \right) $. Thus, the $p$-th entry of the sequence $\Delta^{K+1}\left( a_{1},a_{2},\ldots ,a_{n}\right) $ equals

$\left( \text{the }\left( p+1\right) \text{-th entry of the sequence }\Delta^{K}\left( a_{1},a_{2},\ldots,a_{n}\right) \right) $

$-\left( \text{the }p\text{-th entry of the sequence }\Delta^{K}\left( a_{1},a_{2},\ldots,a_{n}\right) \right) $

$= \sum\limits_{i=0}^{K+1}\left( -1\right) ^{\left( K+1\right) -i} \dbinom{K}{i-1}a_{p+i} -\sum\limits_{i=0} ^{K+1}\underbrace{\left( -1\right) ^{K-i}}_{=-\left( -1\right) ^{\left( K+1\right) -i}}\dbinom{K}{i}a_{p+i}$

(by (4) and (3))

$=\sum\limits_{i=0}^{K+1}\left( -1\right) ^{\left( K+1\right) -i} \dbinom{K}{i-1}a_{p+i}+\sum\limits_{i=0}^{K+1}\left( -1\right) ^{\left( K+1\right) -i}\dbinom{K}{i}a_{p+i}$

$=\sum\limits_{i=0}^{K+1}\left( -1\right) ^{\left( K+1\right) -i}\underbrace{\left( \dbinom{K}{i-1}+\dbinom{K}{i}\right) }_{=\dbinom {K+1}{i}}a_{p+i}$

$=\sum\limits_{i=0}^{K+1}\left( -1\right) ^{\left( K+1\right) -i} \dbinom{K+1}{i}a_{p+i}$.

Thus, Theorem 2 holds for $k=K+1$. This completes the induction, and Theorem 2 is proven. $\blacksquare$

Proving Theorem 1

To prove Theorem 1, it turns out to be easier to work in greater generality.

If $d\geq-1$ is an integer, then a sequence $\left( a_{1},a_{2},\ldots ,a_{n}\right) \in A^{\ast}$ is said to be $d$-polynomial if there exist elements $c_{0},c_{1},\ldots,c_{d}$ of $A$ such that every $p\in\left\{ 1,2,\ldots,n\right\} $ satisfies

$a_{p}=p^{0}c_{0}+p^{1}c_{1}+\cdots+p^{d}c_{d}$.

(We write the $p^{i}$ on the left of the $c_{i}$ because, when multiplying an element of an additive group by an integer, one usually writes the integer on the left. But this is just a matter of taste. The intuition for "$d$-polynomial sequence" is "sequence of the first $n$ values of a polynomial of degree $\leq d$ with coefficients in $A$".)

A $0$-polynomial sequence $\left( a_{1},a_{2},\ldots,a_{n}\right) $ is a constant sequence (because it satisfies $a_p = \underbrace{p^0}_{=1} c_0 = c_0$ for every $p$). A $1$-polynomial sequence is an arithmetic progression. A $\left( -1\right) $-polynomial sequence is a sequence all of whose entries are $0$ (because for $d=-1$, the sum $p^{0}c_{0}+p^{1} c_{1}+\cdots+p^{d}c_{d}$ is an empty sum, and thus evaluates to $0$). Of course, every $d$-polynomial sequence is also $e$-polynomial for every $e\geq d$.

Clearly, if $k\in\mathbb{N}$, $n\in\mathbb{N}$ and $A=\mathbb{Z}$, then the sequence $\left( 1^{k},2^{k},\ldots,n^{k}\right) $ is $k$-polynomial. (Indeed, every $p\in\left\{ 1,2,\ldots,n\right\} $ satisfies $p^{k} =p^{0}c_{0}+p^{1}c_{1}+\cdots+p^{k}c_{k}$, where $\left( c_{0},c_{1} ,\ldots,c_{k}\right) =\left( 0,0,\ldots,0,1\right) $.) Therefore, Theorem 1 follows from the following result:

Theorem 3. If $k\in\mathbb{N}$, and if $\mathbf{a}$ is any $k$-polynomial sequence, then the sequence $\Delta^{k+1}\left( \mathbf{a}\right) $ consists solely of zeroes.

This, in turn, will be derived from the following lemma:

Lemma 4. If $k\in\mathbb{N}$, and if $\mathbf{a}$ is any $k$-polynomial sequence, then the sequence $\Delta\left( \mathbf{a}\right) $ is $\left( k-1\right) $-polynomial.

Proof of Lemma 4. Let $k\in\mathbb{N}$, and let $\mathbf{a}$ be any $k$-polynomial sequence. Write $\mathbf{a}$ as $\mathbf{a}=\left( a_{1} ,a_{2},\ldots,a_{n}\right) $. Thus, $\Delta\left( \mathbf{a}\right) =\left( a_{2}-a_{1},a_{3}-a_{2},\ldots,a_{n}-a_{n-1}\right) $.

The sequence $\left( a_{1},a_{2},\ldots,a_{n}\right) =\mathbf{a}$ is $k$-polynomial. Thus, there exist elements $c_{0},c_{1},\ldots,c_{k}$ of $A$ such that every $p\in\left\{ 1,2,\ldots,n\right\} $ satisfies

(11) $a_{p}=p^{0}c_{0}+p^{1}c_{1}+\cdots+p^{k}c_{k}$.

Consider these elements.

Now, define $k$ elements $d_{0},d_{1},\ldots,d_{k-1}$ of $A$ by $d_{j} =\sum\limits_{i=j+1}^{k}\dbinom{i}{j}c_{i}$. I claim that every $p\in\left\{ 1,2,\ldots,n-1\right\} $ satisfies

(12) $a_{p+1}-a_{p}=p^{0}d_{0}+p^{1}d_{1}+\cdots+p^{k-1}d_{k-1}$.

Once this is proven, it will clearly follow that the sequence $\Delta\left( \mathbf{a}\right) $ is $\left( k-1\right) $-polynomial (because $\Delta\left( \mathbf{a}\right) =\left( a_{2}-a_{1},a_{3}-a_{2} ,\ldots,a_{n}-a_{n-1}\right) $), and so Lemma 4 will be proven.

For every $p\in\left\{ 1,2,\ldots,n-1\right\} $, we have

$a_{p+1}=\left( p+1\right) ^{0}c_{0}+\left( p+1\right) ^{1}c_{1} +\cdots+\left( p+1\right) ^{k}c_{k}$ (by (11), applied to $p+1$ instead of $p$)

$=\sum\limits_{i=0}^{k}\underbrace{\left( p+1\right) ^{i}}_{\substack{=\sum _{j=0}^{i}\dbinom{i}{j}p^{j}\\\text{(by the binomial formula)}}}c_{i}$

$=\sum\limits_{i=0}^{k}\sum\limits_{j=0}^{i}\dbinom{i}{j}p^{j}c_{i}=\sum\limits_{j=0}^{k}\sum _{i=j}^{k}\dbinom{i}{j}p^{j}c_{i}=\sum\limits_{j=0}^{k}p^{j}\underbrace{\left( \sum\limits_{i=j}^{k}\dbinom{i}{j}c_{i}\right) }_{=\sum\limits_{i=j+1}^{k}\dbinom{i} {j}c_{i}+\dbinom{j}{j}c_{j}}$

$=\sum\limits_{j=0}^{k}p^{j}\left( \sum\limits_{i=j+1}^{k}\dbinom{i}{j}c_{i} +\underbrace{\dbinom{j}{j}}_{=1}c_{j}\right) =\sum\limits_{j=0}^{k}p^{j}\left( \sum\limits_{i=j+1}^{k}\dbinom{i}{j}c_{i}+c_{j}\right) $

Subtracting $a_{p}=p^{0}c_{0}+p^{1}c_{1}+\cdots+p^{k}c_{k}=\sum\limits_{j=0}^{k} p^{j}c_{j}$ from this equality, we obtain

$a_{p+1}-a_{p}=\sum\limits_{j=0}^{k}p^{j}\left( \sum\limits_{i=j+1}^{k}\dbinom{i}{j} c_{i}+c_{j}\right) -\sum\limits_{j=0}^{k}p^{j}c_{j}$

$=\sum\limits_{j=0}^{k}p^{j}\left( \sum\limits_{i=j+1}^{k}\dbinom{i}{j}c_{i}+c_{j} -c_{j}\right) $

$=\sum\limits_{j=0}^{k}p^{j}\sum\limits_{i=j+1}^{k}\dbinom{i}{j}c_{i}$

$=\sum\limits_{j=0}^{k-1}p^{j}\underbrace{\sum\limits_{i=j+1}^{k}\dbinom{i}{j}c_{i}} _{=d_{j}}+p^{k}\underbrace{\sum\limits_{i=k+1}^{k}\dbinom{i}{k}c_{i}} _{\substack{=0\\\text{(since this is an empty sum)}}}$

$=\sum\limits_{j=0}^{k-1}p^{j}d_{j}+\underbrace{p^{k}0}_{=0}=\sum\limits_{j=0}^{k-1} p^{j}d_{j}=p^{0}d_{0}+p^{1}d_{1}+\cdots+p^{k-1}d_{k-1}$.

This proves (12), and, with it, proves Lemma 4. $\blacksquare$

Proof of Theorem 3. Let $k\in\mathbb{N}$. Let $\mathbf{a}$ be any $k$-polynomial sequence. Then,

(13) for every $i\in\left\{ 0,1,\ldots,k+1\right\} $, the sequence $\Delta^{i}\left( \mathbf{a}\right) $ is $\left( k-i\right) $-polynomial.

(Indeed, (13) can be proven by straightforward induction over $i$. The induction base is obvious, and the induction step from $i=I$ to $i=I+1$ uses Lemma 4, applied to $k-I$ and $\Delta^{I}\left( \mathbf{a}\right) $ instead of $k$ and $\mathbf{a}$.)

Now, applying (13) to $i=k+1$, we conclude that the sequence $\Delta ^{k+1}\left( \mathbf{a}\right) $ is $\left( k-\left( k+1\right) \right) $-polynomial, i.e., is $\left( -1\right) $-polynomial. Thus, this sequence consists solely of zeroes (since so does every $\left( -1\right) $-polynomial sequence). Theorem 3 is proven. $\blacksquare$

And, as we said above, from Theorem 3 follows Theorem 1. $\blacksquare$