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

[xxxx9659 (嘎嘎嘎嘎嘎)]

※ 引述《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  : 你給的遞迴都線性的可以直接未定係數法解
→ oblivion87  : 可以google差分方程或直接買離散數學相關的書，都
→ oblivion87  : 有教解法。
推 Desperato   : 遞迴本來就不一定有好看的一般解
→ Desperato   : 解的出來的都是特殊情況
→ Desperato   : 學起來就好了
推 oblivion87  : 線性的話就令A(n)=r^n去解（未定係數法）
→ oblivion87  : 非線性的話基本就像D大說的，很多都解不出來或要用
→ oblivion87  : 特殊方法
→ xxxx9659    : 懂了! 遞迴好像真的沒有萬用解 謝謝你們的教學~
→ doom8199    : 也可以套 Z transform 後整理討論區間在 inverse Z