Question: Fix $d,m\in\mathbb{N}$ with $0\leq m\leq d$ and define $$P(x)=\sum_{i=0}^da_i\left(\prod_{j=i}^{d+i-1}(x+j)\right),$$ where each $a_i$ is a constant, $a_m=0$. Suppose that, after expansion, $P(x)=c-x$ for some constant $c$. Show that $c=\frac{m}{d}-d$.

I obtained a rough solution by evaluating $P\left(-(d+k)\right)$ for each $0\leq k\leq m$, which yields $m+1$ linear relations on $a_0,\dots, a_{m-1}$ and $c$, from which one can then solve by scaling and subtracting. However, I am hoping for a cleaner, more succinct answer (in fact, one might even be able to use the above approach in a neater way than I did).

  • $\begingroup$ Where is this question from? $\endgroup$ – darij grinberg Sep 1 '20 at 15:16
  • $\begingroup$ @darijgrinberg this arose from a geometry problem I’ve been thinking about for a while, it’s not from any source (at least not that I know of!) $\endgroup$ – Romain S Sep 1 '20 at 15:19
  • 3
    $\begingroup$ I'm afraid I don't have anything overly nice either, but maybe you can improve on it. My ansatz is that $a_i = \left(-1\right)^i \left(\lambda \dbinom{d}{i} + \mu \dbinom{d-1}{i}\right)$ for all $i$, where $\lambda$ and $\mu$ are two constants that need to be determined. Indeed, this is the general form of $a_i$ for which $P\left(x\right)$ is linear in $x$. (This follows from some linear algebra and finite difference yoga -- let me know if you need more details.) Now you should be able to find $\lambda$ and $\mu$ from the conditions $a_m = 0$ and $P\left(x\right) = c-x$. $\endgroup$ – darij grinberg Sep 1 '20 at 15:24
  • $\begingroup$ What is the geometry problem, though? $\endgroup$ – darij grinberg Sep 1 '20 at 15:24
  • 1
    $\begingroup$ @darijgrinberg If you want to write that up, if it is a complete solution, I will accept it since I doubt there is a much sleeker way to do it... This problem actually came up when considering the intersection of planes along a curve, but the source of the problem is not helpful to solving this, in this case, unfortunately... $\endgroup$ – Romain S Sep 1 '20 at 16:53

Here is a detailed write-up of the solution sketched in @darijgrinberg 's comment.

Summary of solution: the problem can be restated as saying that the $a_i$'s are the coordinates of $P(x)=c-x$ in a certain basis. So we only need to compute the coordinates of $1$ and $x$ in this basis to obtain the $a_i$ in terms of $c$.

Detailed solution : let $\beta_{d,k}(x)=\prod_{j=k}^{d+k-1}(x+j)$ (so that $P=\sum_{k=0}^d a_k\beta_{d,k}(x)$) and ${\cal B}_d=(\beta_{d,0},\beta_{d,1},\ldots,\beta_{d,d})$.

Lemma 1. ${\cal B}_d$ forms a basis of ${\mathbb R}_d[x]$, the space of polynomials of degree $\leq d$.

Proof of lemma 1. It will suffice to show that the members of ${\cal B}_d$ are linearly independent. So suppose that $\sum_{k=0}^d \lambda_k \beta_{d,k}=0$ for some scalars $\lambda_0,\lambda_1,\ldots,\lambda_k$. Evaluating at $-d$, we see that $\lambda_0=0$. Next, evaluating at $-(d+1)$, we see that $\lambda_1=0$, etc.

Our goal is now to compute the coordinates of $1$ and $x$ in the basis ${\cal B}_d$. The idea is to iterate the difference operator $\Delta$ defined by $\Delta(Q)=Q(x+1)-Q(x)$ for a polynomial $Q$. We will use two well-known facts on $\Delta^{i}(Q)$ which are straightforward to check by induction on $i$ once stated.

Fact 1. $\Delta^{i}(Q)=\sum_{k=0}^{i}(-1)^{i-k}\binom{i}{k}Q(x+k)$.

Fact 2. If the two leading monomials of $Q$ are $ax^d+bx^{d-1}$ and $i\leq d-1$, then the two leading monomials of $\Delta^i(Q)$ are $(i!\binom{d}{i}a)x^{d-i}+(\frac{i}{2}(i+1)!\binom{d}{i+1}a+i!\binom{d-1}{i}b)x^{d-i-1}$.

Combining the two facts for $i=d$, we deduce

$$ (d!)a=\Delta^d(Q)=\sum_{k=0}^{d}(-1)^{d-k}\binom{d}{k}Q(x+k). \label{1}\tag{1} $$

And for $i=d-1$, we deduce similarly

\begin{align} &((d!)a)x+\bigg(\frac{d-1}{2}d!a+(d-1)!b\bigg)=\Delta^{d-1}(Q) \\ &= \sum_{k=0}^{d-1}(-1)^{d-1-k}\binom{d-1}{k}Q(x+k). \label{2}\tag{2} \end{align}

Notice that in the LHS of \eqref{2}, the constant term can be rewritten as $(d!)a \times \rho$ where $\rho=\frac{d-1}{2}+\frac{b}{da}$. Subtracting $\rho$ times \eqref{1} from \eqref{2}, we deduce :

\begin{align} ((d!)a)x= \sum_{k=0}^{d}(-1)^{d-1-k}\bigg(\binom{d-1}{k}+\rho\binom{d}{k}\bigg)Q(x+k) \label{3}\tag{3} \end{align}

(since $\dbinom{d-1}{d}=0$). We now apply this context to $Q=\beta_{d,0}$. Then we have $a=1,b=\frac{d(d-1)}{2}$ and hence $\rho=d-1$, so that \eqref{1} becomes

$$ 1=\frac{(-1)^d}{d!} \sum_{k=0}^{d}(-1)^k \binom{d}{k}\beta_{d,k} \label{1'}\tag{1'} $$

and \eqref{3} becomes

$$ x= \sum_{k=0}^{d}\frac{(-1)^{d-1-k}}{d!}\bigg(\binom{d-1}{k}+(d-1)\binom{d}{k}\bigg)\beta_{d,k} \label{3'}\tag{3'} $$

Note that $\binom{d-1}{k}+(d-1)\binom{d}{k}=\big(d-\frac{k}{d}\big)\binom{d}{k}$, so that \eqref{3'} simplifies to

$$ x=\frac{(-1)^d}{d!}\sum_{k=0}^{d}(-1)^{k+1}\big(d-\frac{k}{d}\big)\binom{d}{k}\beta_{d,k} \label{3''}\tag{3''} $$

Combining \eqref{1'} and \eqref{3''}, we deduce

$$ a_k=\frac{(-1)^d}{d!}(-1)^{k}\binom{d}{k}\bigg(c-\big(\frac{k}{d}-d\big)\bigg) \ (0\leq k\leq d) \label{4}\tag{4} $$ and your claim immediately follows.

  • $\begingroup$ (+1) Your (4) is verified by Maple. $\endgroup$ – River Li Sep 5 '20 at 14:22
  • 1
    $\begingroup$ Thanks for writing this up! I've made some simplifications and corrections. $\endgroup$ – darij grinberg Sep 5 '20 at 23:00

Some thoughts

Clearly, $d\ge 1$. Let $x = -(m-1), -m, -(m+1), \cdots, -(d-1)$ respectively to get \begin{align} P(1-m) &= c + m - 1, \\ P(-m) &= c + m, \\ P(-m - 1) &= c + m+1, \\ &\cdots\cdots\\ P(-d+1) &= c + d - 1. \end{align} Then we have (weighted sum of the equations above) $$\sum_{k=0}^{d-m} P(-m - k + 1)(-1)^k\binom{d+1}{k} = \sum_{k=0}^{d-m} (c + m + k - 1) (-1)^k\binom{d+1}{k}. \tag{1} $$

Claim 1: It holds that $$\sum_{k=0}^{d-m} P(-m - k + 1)(-1)^k\binom{d+1}{k} = 0.$$ (The proof is given at the end.)

By (1) and Claim 1, we have $$\sum_{k=0}^{d-m} (c + m + k - 1) (-1)^k\binom{d+1}{k} = 0$$ which results in $$c = -m + 1 - \frac{\sum_{k=0}^{d-m} k (-1)^k\binom{d+1}{k}}{\sum_{k=0}^{d-m} (-1)^k\binom{d+1}{k}} = -m + 1 - (d+1)\frac{d-m}{d} = \frac{m}{d} - d$$ where we have used the identity (see 26.3.10 in https://dlmf.nist.gov/26.3) $$(-1)^N \binom{M}{N} = \sum_{k=0}^N (-1)^k \binom{M+1}{k}, \quad 0\le N \le M$$ to get $$\sum_{k=0}^{d-m} (-1)^k\binom{d+1}{k} = (-1)^{d-m}\binom{d}{d-m}$$ and $$\sum_{k=0}^{d-m} k (-1)^k\binom{d+1}{k} = (d+1)\frac{d-m}{d}(-1)^{d-m}\binom{d}{d-m}. \tag{2}$$ (The proof of (2) is given at the end.)


Proof of Claim 1: We have \begin{align} &\sum_{k=0}^{d-m} P(-m - k + 1)(-1)^k\binom{d+1}{k}\\ =\ & \sum_{k=0}^{d-m} \sum_{i=0}^d a_i\left(\prod_{j=i}^{d+i-1}(-m - k + 1+j)\right)(-1)^k\binom{d+1}{k}\\ =\ & \sum_{i=0}^d a_i \sum_{k=0}^{d-m} \left(\prod_{j=i}^{d+i-1}(-m - k + 1+j)\right)(-1)^k\binom{d+1}{k}\\ =\ & \sum_{i=0}^d a_i A_i \end{align} where $$A_i = \sum_{k=0}^{d-m} \left(\prod_{j=i}^{d+i-1}(-m - k + 1+j)\right)(-1)^k\binom{d+1}{k}.$$ It suffices to prove that $A_i = 0$ for all $i \ne m$.

We split into three cases:

  1. $m = d$: For $0\le i < m$, we have $$A_i = \prod_{j=i}^{d+i-1}(-d + 1+j) = 0.$$

  2. $m = 0$: For $1\le i\le d$, noting that $\prod_{j=i}^{d+i-1}(-m - k + 1+j) = 0$ for $i + 1 \le k \le d$, we have \begin{align} A_i &= \sum_{k=0}^{d} \left(\prod_{j=i}^{d+i-1}( - k + 1+j)\right)(-1)^k\binom{d+1}{k}\\ &= \sum_{k=0}^i \left(\prod_{j=i}^{d+i-1}( - k + 1+j)\right)(-1)^k\binom{d+1}{k}\\ &= \sum_{k=0}^i \frac{(d+i-k)!}{(i-k)!}(-1)^k\binom{d+1}{k}\\ &= d! \sum_{k=0}^i (-1)^k \binom{d+1}{k} \binom{d+i-k}{i-k}\\ &= 0 \end{align} where we have used the identity (see @arindam mitra's answer:
    Prove combinatorial identity using inclusion/exclusion principle) $$\sum_{k=0}^M (-1)^k \binom{N}{k}\binom{N + r - k}{M - k} = 0, \quad 0 \le r \le M-1$$ to get (let $M = i$, $N = d + 1$, $r = i - 1$) $$\sum_{k=0}^i (-1)^k \binom{d+1}{k} \binom{d+i-k}{i-k} = 0.$$

  3. $1 \le m \le d - 1$: If $0\le i < m$, clearly $\prod_{j=i}^{d+i-1}(-m - k + 1+j) = 0$ and hence $A_i = 0$.

If $m < i \le d$, I $\color{blue}{\textrm{GUESS}}$ $A_i = 0$.

Remark: With the help of Maple, $\color{blue}{\textrm{it appears that}}$ $$\sum_{k=0}^{d-m} \Big(\prod_{j=i}^{d+i-1}(-m - k + 1+j)\Big)(-1)^k\binom{d+1}{k} = (-1)^{d-m}\binom{d}{m} \prod_{0\le k \le d, \, k\ne m} (i-k). \tag{2}$$ How to prove it?


Proof of (2): If $d-m = 0$, it is obvious. If $d-m\ge 1$, we have \begin{align} \sum_{k=0}^{d-m} k (-1)^k\binom{d+1}{k} &= \sum_{k=1}^{d-m} k (-1)^k\binom{d+1}{k}\\ &= (d+1) \sum_{k=1}^{d-m} (-1)^k \binom{d}{k-1}\\ &= -(d+1) \sum_{j=0}^{d-m-1} (-1)^j \binom{d}{j}\\ &= -(d+1)(-1)^{d-m-1}\binom{d-1}{d-m-1}\\ &= (d+1)\frac{d-m}{d}(-1)^{d-m}\binom{d}{d-m}. \end{align} We are done.


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.