作者yueayase (scrya)
看板Math
标题Re: [中学] 余式定理和递回
时间Sat Jul 11 01:20:48 2020
※ 引述《Beiloin (哈士奇)》之铭言：
: 准备考APX了
: 解了一下类题
: 如图
: http://i.imgur.com/8mapn1H.jpg
: http://i.imgur.com/sGwWPAq.jpg
: 不知道这两题有没有神人能帮忙解答@@
: -----
: Sent from JPTT on my Realme RMX1851.
http://i.imgur.com/sGwWPAq.jpg
用长除法or综合除法观察:
11 10 9 8 7 6
a + b + 0 + ...................................... + 1 | 1
+ a | 1
0 + a | a
----------------------------------------------------------|
a |(a+b) +a (a+b) | a+b
1 (a+b) |
-----------------------------------------------------------|
(2a+b)|(a+b) | 2a+b
2 (2a+b) (2a+b) |
-----------------------------------------------------------|
(3a+2b) (2a+b) | 3a+2b
3 (3a+2b) (3a+2b) |
------------------------------------------------------------
(5a+3b) (3a+2b)
可观察出做第k层综合除法後会有 F(k)a+F(k-1)b F(k-1)a+F(k-2)b
F(k)为费氏数列 F(0) = F(1) = 1
=> 当消到剩x^2项时
F(9)a+F(8)b F(8)a+F(7)b + 1 | F(9)a+F(8)
F(9)a+F(8)b + F(9)a+F(8)b|
--------------------------------------------------------------------
F(10)a+F(9)b + F(9)a+F(8)b+1
因为x^2-x-1为因式
所以 F(10)a+F(9)b = 0
F(9)a+F(8)b +1 = 0
k | 0 1 2 3 4 5 6 7 8 9 10
----------------------------------
F(k)| 1 1 2 3 5 8 13 21 34 55 89
=> 89a+55b = 0 ---(1)
55a+34b = -1 ---(2)
(1)*55-(2)*89 => (3025-3026)b = 89
所以 b = -89
Remark:
https://en.wikipedia.org/wiki/Fibonacci_sequence
Cassini's identity: F(n)^2-F(n+1)F(n-1) = (-1)^n
知道这公式，在刚刚加减消去法时: F(9)^2-F(10)F(8) = (-1)^9 = -1
就不用硬乘了
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 218.166.138.78 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1594401651.A.1BD.html
1F：推 Beiloin : 谢谢！看懂了 还以为有什麽神奇的余式定理代值 07/11 01:31
http://i.imgur.com/8mapn1H.jpg
a(n+1) = (a(n)-1+1)^2 (a(n)-1)^2+2(a(n)-1)+1 a(n)-1 1
------------ = ---------------------- = ------- + 1 + ---------
2(a(n)-1) 2(a(n)-1) 2 2(a(n)-1)
=> (a(n+1)-1) = (a(n)-1) 1
-------- + ---------
2 2(a(n)-1)
令b(n) = a(n)-1 => b(n+1) = b(n)/2 + 1/2b(n), b(1) = A-1
由算几不等式，
b(n+1) = [b(n) +1/b(n)]/2 >= √[b(n)*1/b(n)] = 1 => b(n+1) > =1 for all n in N
算几等号成立时 b(n) = 1/b(n) => b(n)^2 = 1 => b(n) = ±1 => a(n) = 0 or 2
因为a(1)=A>2 所以显然等号不可能成立 i.e b(n+1) = a(n+1)-1 > 1 for all n in N
故 a(n+1) > 2 for all n in N 及 a(1) = A > 2
所以 a(n) > 2 for all n in N => 选(B)
-----------------------------------------------------------------------------
再来，观察 b(n+1)/b(n) = [1+1/b(n)^2]/2
因为 b(n) = a(n)-1, a(n) > 2 for all n in N，所以 b(n) > 1 for all n in N
则 1/b(n)^2 < 1 => b(n+1)/b(n) < (1+1)/2 = 1 => b(n+1) < b(n) for all n in N
故 a(n) = b(n)+1, n>=1 为单调递减序列 => 选(E)
----------------------------------------------------------------------------
至於(D)，举反例 A=3 => b(1)=2 => b(2) = (2+1/2)/2 = 5/4
=> a(2) = b(2)+1 = 9/4 = 2 + 1/4 < 2+ 1/2^(2-1)= 2 + 1/2
※ 编辑: yueayase (218.166.138.78 台湾), 07/11/2020 02:01:51
※ 编辑: yueayase (218.166.138.78 台湾), 07/11/2020 04:05:01
2F：推 Beiloin : 再次感谢y大写的这麽清楚易懂，以为这题有什麽一般 07/11 09:21
3F：→ Beiloin : 项可以证，原来要一个个选项去match 07/11 09:21