29
$\begingroup$

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?

$\endgroup$
4
  • 1
    $\begingroup$ $f(n) = \displaystyle\sum_{k = 0}^{a}\epsilon_k(n+k)^p$ is a polynomial with degree at most $p$. So if you can show that $f(n) = C$ for $p+1$ distinct integers $n$, then $f(n)$ must be constant. $\endgroup$
    – JimmyK4542
    Dec 24, 2014 at 7:21
  • $\begingroup$ I already know that it's constant, the nature of the algorithm described above reduces the degree of the polynomial by one each time, until it reaches degree 0. I'm interested in the explicit form of the constant. $\endgroup$
    – Pauly B
    Dec 24, 2014 at 7:39
  • $\begingroup$ The fifth power identity can have the small sum, $$\sum_{n=1}^{168}\pm (x+n)^5=480$$ given in this post. $\endgroup$ Dec 30, 2014 at 5:21
  • $\begingroup$ Suggestion: Wilson's theory in number theory for congruent modulos. $\endgroup$
    – McTaffy
    Jul 24, 2017 at 15:36

2 Answers 2

13
$\begingroup$

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}}$$

$\endgroup$
2
  • 1
    $\begingroup$ @rpm Yes. this is essentially a generalized finite forward difference. $\endgroup$ Dec 24, 2014 at 8:25
  • $\begingroup$ Thanks ! :) I understand now ! :-) $\endgroup$
    – r9m
    Dec 24, 2014 at 8:29
8
$\begingroup$

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$

$\endgroup$
3
  • $\begingroup$ Why does $(R-1)^nx^n=n!$ ? $\endgroup$
    – Pauly B
    Dec 24, 2014 at 17:18
  • $\begingroup$ @PaulyB: $(R-1)^nx^n$ is just the $n^\text{th}$ forward difference of $x^n$, which is $n!$. $\endgroup$
    – robjohn
    Dec 24, 2014 at 17:25
  • $\begingroup$ @PaulyB: I've added an explanation to my answer to help clarify things. $\endgroup$
    – robjohn
    Dec 24, 2014 at 17:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.