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

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.

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$