高二竞赛讲义多项式的插值与差分

1、高二数学竞赛班二试讲义第3讲多项式的插值与差分班级 姓名一、知识点金1.拉格朗日插值公式：存在唯一的一个次数不超过n 1的多项式f(x)满足f(Xi)y,i 1,2, ,n ( f(x)的图象经过n个不同点(Xi,y)；并且f(x)可表示为f(x)f (Xi)(x x2)(x x3)(xix2)(xi x3)(x xn)(xi xn)f %)(x )(x x3)(x2 xi)(x2 x3)(x xn)(x2 xn)f (xn、 (x X) (x xn 2)(x xn)1 ) ；0:(xn i xi) (xn i xn 2)(xn i *n)、(x X) (x xn 2)(x xn i)f (x

2、n ) I；1;(xn xi)(xn *口2)函 *n i)2 .对于函数f(x)及固定的h 0, f(x h) f(x)称为f(x)的步长为h的一阶差分，记 作；f(x)。iihf(x h) hf(x) f(x 2h) 2f(x h) f(x),称为 f (x)的步长为 h 的二阶差 分。记作 2 f (x) h f (x h) ；f(x)。h( hif(x)o般地，f(x)的步长为h的n阶差分定义为nf (x)n3 .对于函数 f(x),有 nf(x)(i)nicnf(x ih)i 0nhf(x) ( i)n icnf(x ih), i 0i)niC；f(x ih)nih) (i i代替上

3、式中i的位置)i 0数学归纳法证明：n i时结论显然成立。假设 nn则 nif(x) ( i)niC：f(x h ih) ( i 0i 0n in(i)n i icnif(x ih) ( i)n icnf(x i ii 0n i(i)nii(cni c；)f(x ih)(注意：定义 cni 0, Cnn i 0) i 0 n i(i)niicnif(x ih)i 0 n因此nf (x)( i)nic；f(x ih)对一切正整数n成立。n次多项式;i 0 mm i,. . n4 .设 f(x) amxam ixax a0,当 n m 时，hf (x)是一个 m而对于n m , n f (x)恒为

4、零。证明：由定义可知，hf(x) f(x h) f(x) am(x h)ma0 amxma0m im imhamx低次项，这是一个m i次多项式，首项为mhamx,依此类推，m i f (x) m!hmiamx 常数项，m f (x) m!hmam,从而当 n m 时，n f (x) 0。5 .综合第3、4条，取步长h i ,可得出0, 若 m n, m!am,若 m n,n(i)设f(x)是m次多项式，首项系数为am,则 (i)nicnf(x i) i 0(2)特别地，取f (x) xm,并在上面等式中取 x 0,得欧拉恒等式n(1)icn imi 00,若m n,(1)nn!,若 mn,6

5、.整值多项式:如果当X取整数时，复系数多项式整系数多项式当然都是整值多项式。但组合数Ckf(x)为整数，则称f(x)为整值多项式。x(x 1) (x k 1),-是非整系数的整值k!多项式。7. n次复系数多项式 f(x)为整值多项式的充分必要条件是,nn 1anCxan 1cx-1aQx a0,其中 ai(i 0,1,2,它可表不成,n)均为整数，且an 0证明：充分条件是显然的。现证明必要性。以c：除f(x),商必为常数，设为an ,则f(x) anc： f1(x), f(x)或者为零，或者次数小于n;在用n 1次多项式c： 1除f1(x),如此进行，便得到 f(x) anC； an 1c

6、xn 1aC；a0,这种表示显然是惟一的。、例题分析例1.设n次多项式f(x)满足f (k)(k0,1,n)。求 f (n1)。例1.法一：由多项式插值公式得,f(x)f(k)f(m)k所以f(nf(k)(0n1)1)nk m(m 1)(m n)x i -,对于k in(m1)nk)k!(n k)!0,若n为奇数,1,若n为偶数1)n kf(k)cmcm法二：因为n次多项式“*)的门1阶差分为零,所以1)n1 icn 1f (xi) 0令x 0,并以f(i 0,1, ,n)代人，得f (n1)n(1)n1 icni 01f(i) 0n所以f(n 1)(i 01)n i0,若n为奇数,1,若n为

7、偶数例2.设n次多项式,、1f(x)满足 f(k) (k 1,2, k例1.法一由多项式插值公式得。略法二：因为n次多项式“*)的门1阶差分为零，所以1 令 x 1 ,并以 f (i) 1(ii0,1,n)代人,f (n2)(1) 0n(i 0n1 icn # (x1)n1 iC；1i) 0nf(n 2)( 1)nicni 01)n 11)n10,n为奇数，12,n为偶数n 2法三：对于本题还有更好的做法,有n 1个不同的零点x 1,2,考虑n 1次多项式g(x) xf(x) 1。有已知条件，g(x),n 1,又 g(0)1于是g(x)(x 1)(x 2) (xn 1)f(n1)n(n 1)!

8、0,n为奇数,因此 g(n 2)- (1 ，一,进而Dn例3.设f(x)是一个,n为偶数n 2n次多项式，满足f(k) 2k(k1,2,n D，求 f (n3)的值。例3.因为n次多项式 “*)的门1阶差分为零，所以1)n1iC：1f(x i)f(n 2)n(1)n1iC： 12i1i 00, f (n2)(1)n1iC；012i 12n 2f(n2)n 12( 1)n1 i iQiQn 2Cn 122f (n2)2(2n 1 n 21)20,所以f (n2)再用取2, f (n3) Cn1f(n2)1)n1 iCn12i 2f(n3)C：1f (n2)n 1(1)n1iCn12in 3 n

9、n 22 Cn 1 2f(n3)Cnn1f(n2)f(n 所以 例4.3)f (n 设例4.由于Cnn1f(n3)x1，x2,n 1ax2)i 0n 14 (i 04( 12)n 12n 32n 3 CnCn12n22n 3,xn2n1是任意nan 在点 x1，x2,记所说的多项式为f(x),1个互不相同的整数。,xn 1处所取得的n由多项式插值公式得,f(x)的首项系数为1,故由上式得出但 x1，x2,(xik if(i)f (i) (i 1,2, ,n)的最大值，则有nn 212则任意 n次多项式1个值中,f(x)1(xi xk),xn 1是任意n 1个互不相同的整数，可设xk)(xi x

10、)(xi x 1)(xi xi 1)(x至少有一个的绝对值n!2n(x xk)k ix1x2xn 1)(x xk) f(i)-(x xk)k ixn1,我们有(i1)(i2) 1 2 (ni) (in!1)!(n 1 i)!尸1Cn于是(x Xk)1n 1 C 1Cni 1 n!Cnn!n!CC? 2例5.设k的性质：(1) f(0)k i3是奇数。证明：存在一个次数为0, f (1) 1;(2)有无穷多个正整数 n,使得对s 2k n f (X1) f(x2)没有整数解X1,x2, ,Xsok的非整系数的整值多项式f(x),具有下面1,方程 f (Xs)例5.先证明一个引理：存在一个首项系数

11、为正的k次整值多项式f(x),系数不全是整数,满足 f(0) 0, f (1) 1 ,以及 f(x)0(mod 2k),若x为偶数,1(mod 2k工若遇奇数。引理证明：满足 f(0)0, f(1) 1的首项系数为正的 k次整值多项式f(x)可以表示为:kk 11，一f (x) akCx ak 1cxa1cx，其中 ak 0 , a1 1因为 cX 2 CX 2C； 1 c；2,所以 XUx x x，/i/k 1f(x 2) f(x) 2akCx 1(2ai -冲；1i 1现在我们去ak, ak 1, , a2满足则易解得(注意a1 1)2(2ak 2k,2aiai 1由此即知，对每一个整数

12、x ,有f (x 2)0,1 i k 1i k ,从而 f (x 2)f(x) 0(mod2k)k k 1f(x) 2 Cx由于 f(0) 0 0(mod 2k),所以 x为偶数时，f(x) 0(mod 2k), 由于 f(1) 1 1(mod2k),所以 x 为奇数时，f (x) 1(mod2k),即有f (x)0(mod 2k),若x为偶数, 1(mod 2k),若x为奇数。k 1 k -k 2 k 1这时多项式f(x) 2 Cx 2 Cx“2 1 k2 k 1 一2Cx Cx , x的系数是在k k!3时为非整数。满足引理中的要求。回到原问题：取正整数 nn f(X1) f (X2)1(

13、mod2k),假设有整数X1,X2, ,Xs,使得f(Xs),则更有 f(x1) f (X2)f(Xs)1(mod2 )但由引理可知，上式左边每一项模 2k是0或1,因此在s 2k 1时，左边模2k决不可能为_ k .21,矛盾！从而本题结论成立。三、同步检测1.求一个次数小于 4 的多项式 f(x),满足 f( 1) 2i 2, f (0) 1, f (1) 0, f(2) 2i 1,1 .利用拉格朗日插值公式得 f(x) ix2 (1 i)x 11 /1 , 25 ° 112 .证明多项式 一 x4 x3 x2 x 1是整值多项式。24122412e,取 x 0,1,2,3,4

14、,可f (x)是整值多项式。、几 141325 21 143c213 .设xxxx1 aCxbCxcCxdCx24122412求得a b 1,c1,d 0,e 1 ,因此所说的多项式是整值多项式。4 .设f(x)是n次多项式，在连续 n 1个整数处取值为整数，则3 .对任意整数a, f(x)是整值多项式，等价于g(x) f(x a)是整值多项式。因此可设连续 n 1 个整数是 0,1,2, ,n。先将 f(x)表示为 f(x) anCxn an 1C11aC； a0,再由f(k)(k 0,1,2, ,n)是整数，可推出诸系数都是整数。5 .设 f(x)是 2n 次多项式，f (0) f (2) f (2n) 0,f (1) f(3) f(2n 1) 2,且 f(2n 1)30 ,求 n 的值。2n 14.因为2n次多项式f(x)的2n 1阶差分为零，所以(1)2nlic2n # (x i)i 0取 x 0,并以 f(i)(i 0,1, ,2n2nf(2n 1)( 1)2nlic2n#(i)i 0所以 30 2(22n 1) 0,解得n2n 11)代人，彳导(1)2n 1 iC2n 1f(i)i