Re: [分析] 遞迴關係式的分析方法

看板Math作者xxxx9659 (嘎嘎嘎嘎嘎)時間5年前 (2019/03/26 16:44)推噓3(3推 0噓 8→)

留言11則, 4人參與討論串3/4 (看更多)

※ 引述《Desperato (肥鵝)》之銘言： : ※ 引述《xxxx9659 (嘎嘎嘎嘎嘎)》之銘言： : : 最近算了一個遞迴關係式寫成這樣 : : A(1) = 1 : : n-1 : : A(n) = 1 + 1/n * Σ A(i) : : i=1 : : 我想要簡化這個算式 : : 反覆看了半天才發現原來它是調和級數 : : 那就可以把上面這個公式推導成這個簡單版本 : : A(1) = 1 : : A(n) = A(n-1) + 1/n : : 我算是僥倖猜到它是調和級數才有簡化的目標 : : 那如果一開始算式比較複雜的話 : : 我看再久也想不到簡化的方法 : : 請問各位大大有沒有什麼SOP的分析步驟 : : 可以把遞迴關係式變的簡單？ : : 感謝～ : 代回去就好了 : n-2 : A(n-1) = 1 + 1/(n-1) * sum A(i) : i=1 : n-2 : sum A(i) = (n-1) (A(n-1) - 1) : i=1 : n-1 : sum A(i) = n A(n-1) - (n-1) : i=1 : n-1 : A(n) = 1 + 1/n * sum A(i) = A(n-1) + 1/n : i=1 感謝回答～我的問題是這樣的如果看到一個遞迴關係式長得像這樣 A(1) = 2 A(2) = 4 A(n) = A(n-1) + 2 A(n-2) 把數列一一列出來 2, 4, 8, 16, 32, 64, ... 一眼就了解 A(n) = 2^n 那稍為把題目改一下 A(1) = 1 A(2) = 1 A(n) = A(n-1) + 2 A(n-2) 把數列一一列出來 1, 1, 3, 5, 11, 21, ... 我眼睛要看到脫窗才知道 A(n) = ( 2^n - (-1)^n ) / 3 原本的那題遞迴關係式是把他列出來後發現是調合級數我去才動手把算式簡化要簡化的遞迴方法我就只有嘗試代參數猜答案那如果題目難一點看不出來我就沒招了不知道沒有什麼通用方法或步驟可以分析這種問題？還是有網站或書在教這類的分析的？ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.116.73.83 ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1553589846.A.AAF.html

推

oblivion87

03/26 17:27, 5年前 , 1^F

03/26 17:27, 1^F

→

oblivion87

03/26 17:29, 5年前 , 2^F

03/26 17:29, 2^F

→

oblivion87

03/26 17:29, 5年前 , 3^F

03/26 17:29, 3^F