A sequence of real numbers $a_0, a_1, \dots$ satisfies the condition\[\sum\limits_{n=0}^{m}a_n\cdot(-1)^n\cdot\dbinom{m}{n}=0\]for all large enough positive integers $m$. Prove that there exists a polynomial $P$ such that $a_n=P(n)$ for all $n\ge0$.
Problem
Source: Turkey TST 2016 P4
Tags: algebra, polynomial
mberke
10.04.2016 19:58
This question was a lemma on shortlist IMO 2007 on page 23, A7 https://www.imo-official.org/problems/IMO2007SL.pdf
Stefan4024
12.04.2016 01:12
Obviously the following identity is true $\binom{i}{n}\binom{m}{i} = \binom{m}{n}\binom{m-n}{i-n}$. Now using this we have:
$$\sum_{i=n}^{k} \binom{i}{n}\binom{k+1}{i}(-1)^{n+i} = (-1)^{k+n}\binom{k+1}{n} \iff \sum_{i=n}^{k} \binom{k+1}{n}\binom{k+1-n}{i-n}(-1)^{n+i} = (-1)^{k+n}\binom{k+1}{n}$$$$ \iff \sum_{i=n}^{k} \binom{k+1-n}{i-n}(-1)^{n+i} = (-1)^{k+n} \iff \sum_{i=0}^{k-n}\binom{k+1-n}{i}(-1)^i + (-1)^{k+1}\binom{k+1-n}{k+1-n} = 0 $$$$\iff \sum_{i=0}^{k-n+1}\binom{k+1-n}{i}(-1)^i = 0 \iff (1-1)^{k+n-1} = 0$$
Let's consider the polynomials $F_{k+1}(x) = F_{k} + \left(a_{k+1} - F_k(k+1)\right)\binom{x}{k+1}$ and $F_0 = a_0$. This is a Lagrange polynomial interpolation, such that the graph of $F_{k+1}$ contains points $(i,a_i); \forall k+1\ge i \ge 0$. We claim that: $$F_k(x) = \sum_{n=0}^k \sum_{i=n}^k a_n\binom{i}{n}\binom{x}{i}(-1)^{n+i}$$
Obviously this is true for $k=0$. Now let’s assume that $F_k$ is of this form. Now using induction we have:
$$F_{k+1}(x) = \sum_{n=0}^n \sum_{i=n}^k a_k\binom{i}{n}\binom{x}{i}(-1)^{n+i} + (a_{k+1} - \sum_{n=0}^k \sum_{i=n}^k a_n\binom{i}{n}\binom{k+1}{i}(-1)^{n+i})\binom{x}{k+1} = $$$$ =\sum_{n=0}^k \sum_{i=n}^k a_n\binom{i}{n}\binom{x}{i}(-1)^{n+i} + \sum_{n=0}^k a_{n}(-1)^{n+k+1}\binom{k+1}{n}\binom{x}{k+1} + a_{k+1}\binom{k+1}{k+1}\binom{x}{k+1}(-1)^{k+1 + k +1} = \sum_{n=0}^{k+1} \sum_{i=n}^{k+1} a_n\binom{i}{n}\binom{x}{i}(-1)^{n+i}$$
If the equation holds for $m\ge m_0$, then we’ll prove that $F_{m-1}(m) = a_{m}$. This is true as: $$F_{m-1}(m) = \sum_{n=0}^{m-1} \sum_{i=n}^{m-1} a_n\binom{i}{n}\binom{m}{i}(-1)^{n+i} = \sum_{n=0}^{m-1} (-1)^{m+n-1}a_n\binom{m}{n} = a_m$$ But now using the equation for construction of $F_k$ we can conclude that $F_m = F_{m_0-1} \forall m\ge m_0$. Hence: $F_{m_0-1}(n) = a_n; \forall n\ge 0$. Q.E.D.
dgrozev
02.09.2018 19:50
Finite difference. That's the key word. Let $f(x)$ be a function with $f(n)=a_n\,,\, n=0,1,2,\dots$. Denote its $k$-th finite difference with step $h$ at point $x$ as: $$ \Delta_h^k f(x) := \sum_{i=0}^k (-1)^{k-i}\binom{k}{i}f(x+ih)$$The only property we need is that for any polynomial $P$ of degree $n$, $\Delta_h^m P(x)\equiv 0$ for all $m\geq n$. Further, in our case we have $\Delta_1^k f(0)=0 $ for all $k\geq m$, $m$ is some natural number. Consider the polynomial $P(x)$ of degree $m-1$ for which $P(i)=f(i)\,,\,i=0,1,\dots,m-1$. It's unique, for example could be constructed with the Lagrange interpolation. Thus, we have $\Delta_1^m P(0)=0$, because $P$ is a polynomial of degree $m-1$. On the other hand $\Delta_1^m f(0)=0$, because of the given condition. Hence: $$\Delta_1^m P(0)=\Delta_1^m f(0)$$View it as equation with respect to $f(m)$, consider all other $P(i)=f(i)\,,\, i= 0,1,\dots,m-1$ as fixed. It is a linear equation and since putting $P(m)$ instead of $f(m)$ makes it hold, it's the only root, thus $f(m)=P(m)$. In the same way from: $$\Delta_1^{m+1} P(0)=\Delta_1^{m+1} f(0)$$we get $f(m+1)=P(m+1)$ and so on. Thus $f(n)=P(n)\,,\,n\in \mathbb{N}$.