※ 引述《cuttlefish (无聊ing ><^> .o O)》之铭言： : 已知a_0, a_1, a_2, ... 为整数数列, 满足 : (1) m-n | a_m - a_n for all m>n>=0 : (2) 存在多项式P使得 |a_n| < P(n) for all n>=0 : 证明存在多项式Q使得 a_n = Q(n) for all n>=0 (6/13) 补完了 好长 超长...qw q (6/14) 订正错误的部分 并改写前半部证明 Let Q(n) be the unique polynomial satisfies degQ <= d = degP, Q(i) = a_i for 0 <= i <= d There exists some c_1, c_2 > 0, P' = c_1 P + c_2 such that P'(n) >= |Q(n)| for all n>=0 clearly P' also satisties (2), thus we can replace P by P' We recall some property of finite difference here. Given any polynomial T(n), we define Δ^0 T(n) = T(n) Δ^i T(n) = Δ^(i-1) T(n+1) - Δ^(i-1) T(n) Note that (1) Δ is associative, i.e. Δ^(m+n) T = Δ^m(Δ^n T) (2) degT = t, then deg(Δ^k T) = t-k for k < t Δ^t T is nonzero constant Δ^u T is zero function if u > t k (3) Δ^k T(n) = sum (-1)^(k-i) binom(k, i) T(n+i) (*) i=0 k (4) T(n+k) = sum binom(k, i) Δ^i T(n) (**) i=0 (Prop 1) if ΔT(n) is an integer for all n>=0, T(0) is an integer then T(n) is an integer for all n>=0. (pf) By induction. ■ (Coro 1) Q(n) is an integer for all n>=0 (pf) By (*) we have Δ^i Q(0) is an integer for each 0<=i<=d especially Δ^d Q(0) is an integer, then Δ^d Q is integer constant. Using Prop 1 d times gets the desired result. ■ (Prop 2) Let T(n) be integer for all n>=0 if m |ΔT(n) for all n>=0, m |T(0) then m |T(n) for all n>=0 (pf) By induction ■ (Prop 3) Let T(n) be integer for all n>=0, p prime then p |T(n+p)-T(n) <==> p |Δ^p T(n) (pf) by (**) and the fact that p |binom(p, i) for each 0<i<p ■ (Coro 2) m-n |Q(m)-Q(n) for all m > n>=0 (pf) (s1) p |Q(n+p)-Q(n) for all n>=0, p prime case p >d follows by Prop 3 and Δ^p T = 0 case p<=d, by Prop 3, p |Δ^p T(i) for 0<=i<=d- then p |Δ^t T(0) for each p<=t<=d especially p |Δ^d T(0), then p |Δ^d T(n) for all n>=0 (constant) by Prop 2 (d-p) times, p |Δ^p T(n) for all n>=0 Thus p |Q(n+p)-Q(n) for all n>=0 by Prop 3. (s2) q |Q(n+q)-Q(n) for all n>=0, q = p^b prime power we prove by induction on b. assume p^t |Q(n+p^t)-Q(n) for all n>=0, 0 <t <b q-1 by (**) Q(n+q) = Q(n) + sum binom(q, i) Δ^i Q(n) + Δ^q Q(n) i=1 note that if 0 <i <q, gcd(q, i)=p^c, 0 <c <b then gcd(q, binom(q, i))=p^(b-c) but then p^c |Q(n+p^c)-Q(n) for all n>=0 <==> p^c |Δ^(p^c) Q(n) for all n>=0 => p^c |Δ^i Q(n) for all n>=0 (since i >= p^c) thus p^b = p^(b-c) p^c | binom(q, i) Δ^i Q(n) for each i hence q |Q(n+q)-Q(q) <==> q |Δ^q Q(n) This is a result anologue to Prop 3. Now replace p by q in (s1), completing the proof. (s3) p |Q(n+p)-Q(n) for all n>=0 q |Q(n+q)-Q(n) for all n>=0, (p, q)=1 then pq |Q(n+pq)-Q(n) for all n>=0 (trivial) Therefore, Coro 2 can be proved by decomposing m-n into factors of prime powers ■ Let r_n = Q(n) - a_n. Then r_i = 0 for 0<=i<=d (Lemma 1) If r_n = 0, then m-n | r_m for all m>=0, m!=n (pf) This follows by (1) and Coro 2. ■ Let L(n, d) = lcm(n, n-1, n-2, ..., n-d) if n > d. (Prop 4) L(n, d) >= M(n, d) for some polynomial M with degM = d+1. k (pf) since gcd(lcm(a_1, ... a_k), b) <= prod gcd(a_i, b) i=1 we have L(n, d) = lcm(L(n, d-1), n-d) = L(n, d-1) (n-d) / gcd(L(n, d-1), n-d) d-1 >= L(n, d-1) (n-d) / prod gcd(n-k, n-d) k=0 1 >= --- (n-d) L(n, d-1) d! d 1 d >= (prod ---) prod (n-i) = M(n, d) ■ k=1 k! i=0 Now degM > degP, thus exists N, M(n) > 2|P(n)| for all n > N (Prop 5) r_n = 0 for all n >= 0 (step 1) given n > d, by Lemma 1, n-i | r_n for 0<=i<=d Thus L(n, d) | r_n, but n > N gives |r_n| = |Q(n) - a_n| <= 2P(n) < M(n) <= L(n, d) thus r_n = 0 for all n > N (step 2) given m <= N, by Lemma 1, n-m | r_m for all n > N n can be arbitrary large, thus r_m = 0 ■ Therefore Q_n = a_n for all n>=0, we are done. -- 嗯嗯ow o --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.112.25.105 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1497368489.A.4F4.html ※ 编辑: Desperato (140.112.25.105), 06/14/2017 01:29:23 ※ 编辑: Desperato (140.112.25.105), 06/14/2017 22:31:19