数论多项式恒取整值必有组合解释

hujunhua

f(n)是一个有理系数多项式，若f(n)在自然集上恒为整数，那么f(n)必可表成若干组合数的整式。

例1：$f(n)=1/2n^2+1/2n=C(n+1,2)$
例2：$f(n)=n(n+1)(2n+1)/6=C(n+2,3)+C(n+1,3)$
例3：$f(n)=1/8n^4+1/12n^3-1/8n^2-1/12n=2C(n+2,4)+C(n+1,4)$

mathe

这个猜想是成立的，也是已知的，而且好像不需要约定f是有理数多项式，只要是实系数即可（不知道复系数是不是也是成立的）

mathe

发现很简单，用差分直接可以秒：
首先我们总可以将一个多项式写成$f(x)=a_0+\sum_{k=1}^na_k {x(x-1)...(x-k+1)}/{k!}$
我们计算f(x)的差分$\Delta f(x)=f(x+1)-f(x)=a_1+\sum_{k=2}^n a_k {x(x-1)...(x-k+2)}/{(k-1)!}$
于是我们可以用数学归纳法证明$a_1,...,a_n$都是整数，再根据$a_0=f(0)$得出$a_0$也是整数

mathe

于是我们还可以推广，如果n次多项式f(x)使得f(t),f(t+1),...,f(t+n)都是整数，其中t是一个任意的整数，那么这个多项式必然是可以写成楼上形式

hujunhua

Mathe在3#的陈述已经十分简明了，搜了一下发现了由3#那种差分法导致的公式：

牛顿级数公式：$f(x + a) = \sum_{k = 0}^n \frac{\Delta ^kf(a)}{k!}x_{(k)}= \sum_{k = 0}^n ((x),(k))\Delta ^kf(a)$

取a=0即是$f(x) = \sum_{k = 0}^n ((x),(k))\Delta ^kf(0)$, 既然f(n)恒取整数值，那么从f(0)起步的各阶前向差分$\Delta ^kf(0)$都是整数。

其中$x_{(k)}=x(x-1)(x-2).....(x-k+1)$称为x的k阶下降幂。$((x),(k))=x_{(k)}/{k!}$为（广义）二项式系数。

我感觉这个“猜想”在我们的能力范围内，但没想到会这么简单。主要是对差分法不熟。估计精通数值方法的人大多会向Mathe一样秒杀之。

hujunhua

这个所谓“猜想”在我由来已久，中学时常碰到求证f(n)恒为整数的题，做多了就产生了这种想法。但没想过要去证明它，中学以后把这想法就丢到脑后了。昨天看到那个组合求和的帖子，勾起沉淀，贴将上来，原以为会有一番探讨的，没想被秒杀了。

mathe也忒快了，我还打算在第2帖续两个例子的呢。
$f(n)={n^5-n}/30$和$f(n)={n^7-n}/42$，这一般是在学初等数论时同余理论来证明的，按此“猜想”应可有代数证法。
$f(n)={n^5-n}/30={n(n-1)(n+1)(n^2+1)}/30={n(n-1)(n+1)(n^2-4+5)}/30=4((n+2),(5))+((n+1),(3))$
$f(n)={n^7-n}/42={n(n-1)(n+1)(n^2+n+1)(n^2-n+1)}/42={n(n-1)(n+1)((n-2)(n+3)+7)((n+2)(n-3)+7)}/42$
$=5!((n+3),(7))+(2n^2-5)((n+1),(3))$

zgg___

呵呵，学习了，赞上面的2位~~~
看来要证明n次多项式f(x)在整数域上恒为整数只需要依次将0-n代入f就可以了。
于是之后的某一天……
老师出题：证明当n取整数时(n^5-n)/30恒为整数。
同学回答：当n为0-5时，(n^5-n)/30分别为0,0,1,8,34,104，都是整数，故命题得证。
老师判分：0分。
呵呵。

wayne

一个是from down to up
一个是from up to down
一个是from now to future
赞楼上的三位~~