Generalisation of $(n+3)^2-(n+2)^2-(n+1)^2+n^2=4$

Question

After seeing the neat little identity $(n+3)^2-(n+2)^2-(n+1)^2+n^2=4$ somewhere on MSE, I tried generalising this to higher consecutive powers in the form $\sum_{k=0}^a\epsilon_k(n+k)^p=C$, where $C$ is a constant and $\epsilon_k=\pm1$. I discovered a relatively simple algorithm to generate these patterns: simply take $(n+2^p-1)^p$ and subtract $(n+2^p-2)^p$ (using $n\to n-1$) to get a polynomial of degree $p-1$. Take this difference and subtract $(n+2^p-3)^p-(n+2^p-4)^p$ (using $n\to n-2$) to get a polynomial of degree $p-2$. Repeat this process until $n^p$ is reach. The first few examples of this are $$ \begin{align} n^0&=1\\ (n+1)^1-n^1&=1\\ (n+3)^2-(n+2)^2-(n+1)^2+n^2&=4\\ (n+7)^3-(n+6)^3-(n+5)^3+(n+4)^3-(n+3)^3+(n+2)^3+(n+1)^3-n^3&=48 \end{align} $$ Upon doing this for the next several powers and checking OEIS, it would appear the constant corresponding to the power $p$ is $$\large C_p=2^{\frac{p(p-1)}2} p!$$ However, this is an observation only, and I have no idea how to go about proving this. The only thing I notice is that $\frac{p(p-1)}{2}=\sum\limits_{k=1}^{p-1}k$, but I don't know how to use this fact. Does any one know how to prove this observation?

Answer 1

Let $X = \mathbb{R}^{\mathbb{Z}}$ be the space of real valued sequences defined over $\mathbb{Z}$. Let $R : X \to X$ be the operator on $X$ replacing the terms of a sequence by those on their right. More precisely,

$$X \ni (\ell_n)_{n\in\mathbb{Z}} \quad\mapsto\quad ( (R\ell)_n = \ell_{n+1} )_{n\in\mathbb{Z}} \in X$$ The identities you have can be rewritten as

$$\begin{array}{rcl} (R - 1)n^1 &=& 1\\ (R^2-1)(R-1) n^2 &=& 4\\ (R^4 - 1)(R^2-1)(R-1) n^3 &=& 48\\ &\vdots&\\ (R^{2^{p-1}}-1)(R^{2^{p-2}}-1)\cdots(R^{2^0}-1) n^{p} &\stackrel{?}{=}& C_p = ???\tag{*1} \end{array}$$

Notice for any polynomial $f(n)$ of degree $p$ and leading coefficient A,

$$f(n) = A n^p + A' n^{p-1} + ( \text{something of degree }< p-1 )$$ We have

$$\begin{align} (R^{2^{p-1}} - 1) f(n) &= A\left((n+2^{p-1})^p - n^p \right) + A'\left((n+2^{p-1})^{p-1} - n^{p-1}\right) + \cdots\\ &= A p2^{p-1} n^{p-1} + ( \text{mess with degree }< p-1 )\\ \end{align} $$ This means $(R^{2^{p-1}}-1)f(n)$ will be a polynomial with degree $p-1$ and leading coefficient $A \cdot p 2^{p-1}$. Repeat applying this to the last equation in $(*1)$ $p$ times, we find the LHS of the last equation is equal to a polynomial with degree $0$. i.e. $C_p$ is indeed a constant. Furthermore, $$C_p = 1 (p 2^{p-1} )((p-1) 2^{p-2}) \cdots (2 \cdot 2^{1}) (1 \cdot 2^{0}) = p! 2^{(p-1)+(p-2)+\cdots + 1} = p!2^{\frac{p(p-1)}{2}}$$

Answer 2

Note that since $R$ and $1$ commute, $$ R^{2^k}-1=\left[\sum\limits_{j=0}^{2^k-1}R^j\right](R-1)\tag{1} $$ Therefore, $$ \begin{align} \prod_{k=0}^{n-1}\left(R^{2^k}-1\right)x^n &=\left[\prod_{k=0}^{n-1}\sum_{j=0}^{2^k-1}R^j\right](R-1)^nx^n\tag{2a}\\ &=\left[\prod_{k=0}^{n-1}\sum_{j=0}^{2^k-1}R^j\right]n!\tag{2b}\\ &=\left[\prod_{k=0}^{n-1}2^k\right]n!\tag{2c}\\[6pt] &=2^{n(n-1)/2}\,n!\tag{2d} \end{align} $$ Explanation:
$\text{(2a)}$: apply $(1)$
$\text{(2b)}$: the $n^\text{th}$ forward difference of $x^n$ is $n!$
$\text{(2c)}$: on a constant sequence, $R^j=1$
$\text{(2d)}$: $\sum\limits_{k=0}^{n-1}k=n(n-1)/2$