作者doom8199 (～口卡口卡 修～)
看板Math
標題Re: [中學] 遞迴關係式
時間Tue Jul 26 17:18:23 2016
※ 引述《petwing (主流想法不一定是好的)》之銘言：
: a_1 = 6
: 1
: a_(n+1) = --------
: a_n + 1
: 求 a_n 的一般項
: 謝謝
---
若原po不斷的帶入遞迴式, 會發現它其實就是連分數的型態
可使用輾轉相除法概念去算
例如考慮兩 整數 seq. {p[n]} & {q[n]}
使得 a[n] = p[n]/q[n] 且 gcd{p[n], q[n]} = 1 for all n in N
p[n] 1 q[n-1]
則 ─── = ───────── = ────────
q[n] 1 + p[n-1]/q[n-1] q[n-1] + p[n-1]
不仿假設 p[n] = q[n-1]
則 q[n] = q[n-1] + p[n-1]
= q[n-1] + q[n-2] with (q[0], q[1]) = (6, 1)
且 a[n] - a[n-1]
q[n-1] q[n-2]
= ──── - ────
q[n] q[n-1]
q[n-1]^2 - q[n-2]*q[n]
= ───────────
q[n]*q[n-1]
(q[1]^2 - q[0]*q[2]) * (-1)^n
= ──────────────
q[n]*q[n-1]
41*(-1)^(n+1)
= ─────────
q[n]*q[n-1]
至於 q[n] 就是單純解 二階常係數遞迴 (跟解 fibonacci seq. 一樣)
剩下的 dirty work 就留給原po
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 113.196.153.35
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1469524707.A.0EA.html
→ Desperato : 你偷用連分數公式啊XD 07/26 17:58
推 Desperato : 不過給推 很厲害 07/26 18:01
→ petwing : 越來越懷疑....我看到的是高中題目嗎？.... 07/26 23:49
推 LPH66 : 分子永遠是 ±41 其實很好證 07/27 07:04
→ LPH66 : 問題在分母, q 數列跟費氏數列的遞迴式一樣 07/27 07:05
→ LPH66 : 所以 q 數列也是幾何成長, q[2010] 約為 2.4*10^420 07/27 07:05
→ LPH66 : 所以不太像是求確切值；而若問化簡後的分母 07/27 07:06
→ LPH66 : 子 07/27 07:06
→ LPH66 : (我是說那個 41) 則還要證明 q[2010]*q[2011] 非 07/27 07:06
→ LPH66 : 41 的倍數 (雖然有個強一點的結果是 q 所有項都不是 07/27 07:07
→ LPH66 : 41 的倍數, 但這一件事也不容易證) 07/27 07:07
→ petwing : 謝謝L大解答，我相信是題目出錯了，因為這只是高中 07/30 08:18
→ petwing : 數學題(而且是在非資優班的作業裡看到) 07/30 08:18