作者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/m.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