Still working on this. A related question: are there non-polynomial sequences that satisfy condition a) alone?

How about $ q_n=n!$?

Peter wrote: How about $ q_n = n!$? $ 5!-2!$ must be divisible by $ 3$,but it is not true.

Indeed, I'm sorry. Interesting question, I can't find a counterexample either.

$ q_n=P_n(n), P_n(x)=a_0+a_1x+a_2x(x-1)+...+a_nx(x-1)...(x+1-n)$, were $ a_i\in Z$. For any integer sequence $ a_i$ we get sequence $ q_n=P_n(n)$, suth that $ m-n|q_m-q_n$.

Rust's counter example is false, as his sequence is not bounded by any polynomial I did see solution of this problem once, it 's proof used Lagrange interpolation and an easy to show inequality on "Least common multiple"

Obviously, Rust answered all that posts before (except the starting post)

mto wrote: Rust's counter example is false, as his sequence is not bounded by any polynomial Were is false? If $ m - n|q_m - q_n \ \forall m > n$, then exist integer sequence $ a_i$, suth that $ q_n = P_n(n)$. If $ a_i$ integer sequence, then it define $ q_n = P_n(n)$, suth that $ m - n|P_m(m) - P_n(n) = P_m(m) - P_m(n)$. We can define polinom P(x): \[ P(x) = \sum_{k = 0}^{\infty}a_k\binom{x}{k}k!, \] were $ \binom{x}{0}0! = 1,\binom{x}{k}k! = x(x - 1)...(x + 1 - k)$ and $ degP(x) = \infty$ if there are infinetely many $ a_i\not = 0$. Then $ q_n = P(n) = P_n(n)$ give solution.

Nice (and I was thinking along the same lines). It is clear that we can "mod out" by any sequence of the form Rust gives, but I don't see a way to readily turn this into a solution (at least, I cannot pin down the intuitive notion that the growth rate of $ q_k$ mod polynomials of the form Rust gives is either better-than-polynomial or zero). Idea: consider the generating function $ P(x) = \sum_{k = 0}^{\infty} \frac {q_k}{k!} x^k$. If $ q_k$ is a polynomial sequence then $ P(x)$ is given by a product of a polynomial and $ e^x$ (or something along those lines); in particular, $ P(x)$ satisfies a linear homogeneous differential equation. $ q_k$ being bounded by a polynomial implies convergence for all $ x$. The first condition says that the coefficients of $ P(x) - P^{(m - n)}(x)$ have numerators divisible by $ m - n$, or something along those lines.

Rust wrote: mto wrote: Rust's counter example is false, as his sequence is not bounded by any polynomial Were is false? If $ m - n|q_m - q_n \ \forall m > n$, then exist integer sequence $ a_i$, suth that $ q_n = P_n(n)$. If $ a_i$ integer sequence, then it define $ q_n = P_n(n)$, suth that $ m - n|P_m(m) - P_n(n) = P_m(m) - P_m(n)$. We can define polinom P(x): \[ P(x) = \sum_{k = 0}^{\infty}a_k\binom{x}{k}k!, \] were $ \binom{x}{0}0! = 1,\binom{x}{k}k! = x(x - 1)...(x + 1 - k)$ and $ degP(x) = \infty$ if there are infinetely many $ a_i\not = 0$. Then $ q_n = P(n) = P_n(n)$ give solution. But we don't have |qn| <n^10 for all n .... I don't remember solution of my teacher for this one ( it was a long time). But it 's based on Lagrange interpolation and inequality on LCM of consecutive integers

"mto wrote: But we don't have |qn| <n^10 for all n .... I don't remember solution of my teacher for this one ( it was a long time). But it 's based on Lagrange interpolation and inequality on LCM of consecutive integers I give all solutions. If you want $ |q_n|<n^{10}$ you can take $ a_i=0, \ \forall i\not =10, \ a_{10}=1.$

mto wrote: But we don't have |qn| <n^10 for all n .... Rust was addressing my question, not the original one. mto wrote: I don't remember solution of my teacher for this one ( it was a long time). But it 's based on Lagrange interpolation and inequality on LCM of consecutive integers Here's what I've got along those lines: Write a sum of Newton polynomials $ Q(x)$ of degree $ 10$ such that $ q_k = Q(k), k = 0, 1, ... 10$. Then $ p_k = 10! (q_k - Q(k))$ satisfies condition a) (because $ 10! Q(k)$ is an integer polynomial). Moreover, $ p_k = 0, k = 0, 1, ... 10$. It follows that $ m - k | p_m, k = 0, 1, ... 10 \implies$ $ \text{lcm}(m, m-1, ... m-10) | p_m$. What I'm having trouble with is the inequality that would show that $ \text{lcm}(m, m-1, ... m-10)$ grows faster than $ m^{10}$.

t0rajir0u wrote: mto wrote: But we don't have |qn| <n^10 for all n .... Rust was addressing my question, not the original one. mto wrote: I don't remember solution of my teacher for this one ( it was a long time). But it 's based on Lagrange interpolation and inequality on LCM of consecutive integers Here's what I've got along those lines: Write a sum of Newton polynomials $ Q(x)$ of degree $ 10$ such that $ q_k = Q(k), k = 0, 1, ... 10$. Then $ p_k = 10! (q_k - Q(k))$ satisfies condition a) (because $ 10! Q(k)$ is an integer polynomial). Moreover, $ p_k = 0, k = 0, 1, ... 10$. It follows that $ m - k | p_m, k = 0, 1, ... 10 \implies$ $ \text{lcm}(m, m - 1, ... m - 10) | p_m$. What I'm having trouble with is the inequality that would show that $ \text{lcm}(m, m - 1, ... m - 10)$ grows faster than $ m^{10}$. U could replace 10 by any integer K here, then what u have to show is the lcm(m,m-1,..,m-K) grows faster than m^10 Remark that the common divisor of any two numbers in m,m-1,...,m-K does not exceed K. From this, we could show that LCM(m,m-1,..,m-K) > m.(m-1)...(m-K) / [ K^M] for certain constant M

I came to the same conclusion. Edit: The set of sequences satisfying condition a) is a $ \mathbb{Z}$-module $ \mathcal{A}$, a submodule of which is the set of sequences Rust gives $ \mathcal{P}$ (a submodule of which in turn is the set of integer polynomials). The quotient $ \mathcal{A} / \mathcal{P}$ consists of (equivalence classes of) sequences $ \{ q_k \}$ such that $ q_k$ is defined $ \bmod k!$. Hence we can pick a representative such that $ 0 \le q_k < k!$. It follows that $ q_0 = q_1 = q_2 = q_3 = 0$. (Edit 2: ) We then have $ q_4 = 0, 12$ and $ q_5 = 0, 60$. For Rust's claim to be true (that $ \mathcal{A} = \mathcal{P}$ so the quotient is trivial) we need to show that $ q_4, q_5 \neq 0$ gives a contradiction. But in fact I think it's possible that it doesn't.

One more observation. If $ q_m$ satisfies condition a), then so does the forward difference $ \Delta q_m = q_{m+1} - q_m$. The connection to Newton polynomials is clear. In particular, following Rust's lead we can write any integer sequence $ \{ q_k \}$ in the form $ q_n = \sum_{i=0} a_i {n \choose i}$ where $ a_0 = q_0, a_1 = q_1 - q_0$, and in general $ a_n = (\Delta^n q)_0$. We then have $ \Delta^k q_n = \sum_{i=0} a_{i+k} {n \choose i}$. The finite differences eventually becoming the zero sequence corresponds to $ a_n$ eventually becoming zero and $ q_n$ becoming a polynomial. So perhaps we should consider $ \Delta^{11} q_n$. (Unfortunately, the current bounded condition on $ q_n$ does not easily translate into bounds on $ \Delta q_n$ because of the possibility that $ q_n$ alternates between positive and negative values, so the bounds must be taken together with the divisibility condition.) When $ a_n$ is eventually zero, it seems not too hard to prove that the divisibility condition is satisfied if and only if $ k! | a_k$. Otherwise, I'm not so sure.

In fact,Taiwan 1996 is a special case of USA MO 1995.http://www.artofproblemsolving.com/Forum/viewtopic.php?p=353086&sid=985c19f15cb1fc80ca3958605bdec44e#p353086