推 LimSinE : Q:有理係數，設kQ整係數。考慮rn=k(Q(n)-an)即可？ 06/15 01:43
→ Desperato : 啊 你是對的 kQ的話 coro2一行就證完了qw q 06/15 02:06
→ Desperato : 蠢蠢的... 06/15 02:07
→ Desperato : 反正我有想到後半部了(欸 06/15 02:07
※ 引述《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://www.ptt.cc/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