如何計算遞歸函數的顯式形式？

Question

我有這個遞歸函數：

f(n) = 2 * f(n-1) + 3 * f(n-2) + 4 
f(1) = 2 
f(2) = 8 

我從經驗中知道，它的明確的形式是：

f(n) = 3^n - 1 // pow(3, n) - 1 

我想知道是否有任何的方式來證明這一點。我搜索了一下，但沒有發現任何簡單的理解。我已經知道生成函數可能會解決它，它們太複雜了，我寧願不進入它們。我正在尋找更簡單的方法。

P.S. 如果它幫助我記得是這樣解決的：

f(n) = 2 * f(n-1) + 3 * f(n-2) + 4 
// consider f(n) = x^n 
x^n = 2 * x^(n-1) + 3 * x^(n-2) + 4 

然後你不知何故電子計算機X導致的遞推公式的形式明確，但我不太記得

Answer 1

f(n) = 2 * f(n-1) + 3 * f(n-2) + 4 
f(n+1) = 2 * f(n) + 3 * f(n-1) + 4 

f(n+1)-f(n) = 2 * f(n) - 2 * f(n-1) + 3 * f(n-1) - 3 * f(n-2) 
f(n+1) = 3 * f(n) + f(n-1) - 3 * f(n-2) 

現在4不見了。 正如你說，下一步是讓F（N）= X^N

x^(n+1) = 3 * x^n + x^(n-1) - 3 * x^(n-2) 

除以X ^（N-2）

x^3 = 3 * x^2 + x - 3 
x^3 - 3 * x^2 - x + 3 = 0 

factorise找到X

(x-3)(x-1)(x+1) = 0 
x = -1 or 1 or 3 

f(n) = A * (-1)^n + B * 1^n + C * 3^n 
f(n) = A * (-1)^n + B + C * 3^n 

現在使用您所擁有的數值找到A，B和C

f(1) = 2; f(2) = 8; f(3) = 26 

f(1) = 2 = -A + B + 3C 
f(2) = 8 = A + B + 9C 
f(3) = 26 = -A + B + 27C 

求解A，B和C：

f(3)-f(1) = 24 = 24C  => C = 1 
f(2)-f(1) = 6 = 2A + 6 => A = 0 
2 = B + 3     => B = -1 

最後

f(n) = 3^n - 1 

Answer 2

一般來說，沒有將遞歸形式轉換爲迭代形式的算法。這個問題是不可判定的。作爲一個例子，考慮這個遞歸函數定義，它定義了在Collat​​z序列：

f(1) = 0 
f(2n) = 1 + f(n) 
f(2n + 1) = 1 + f(6n + 4) 

它不知道這是否是一個甚至明確定義的功能或沒有。如果存在可以將其轉換爲封閉形式的算法，我們可以決定它是否定義良好。

但是，對於許多常見情況，可以將遞歸定義轉換爲迭代定義。優秀的教科書具體數學花大部分頁面展示如何做到這一點。當你猜測答案是什麼時，使用歸納法的一種常用技術很有效。作爲一個例子，假設你相信你的遞歸定義確實給出了3^n-1。爲了證明這一點，試着證明它對於基本情況是成立的，然後證明這個知識可以讓你向上推廣解決方案。您沒有在您的帖子中放置基本案例，但我假設

f(0) = 0 
f(1) = 2 

鑑於此，我們來看看您的預感是否正確。對於0和1的具體輸入，可以通過檢查來驗證該函數確實計算了3^n-1。對於歸納步​​驟，我們假設對於所有n'< n，f（n）= 3^n-1然後我們有

f(n) = 2f(n - 1) + 3f(n - 2) + 4 
    = 2 * (3^{n-1} - 1) + 3 * (3^{n-2} - 1) + 4 
    = 2 * 3^{n-1} - 2 + 3^{n-1} - 3 + 4 
    = 3 * 3^{n-1} - 5 + 4 
    = 3^n - 1 

所以我們剛剛證明了這個遞歸函數確實產生3^N - 1.

Answer 3

好吧，我知道你不想生成（從現在起GF）功能，所有複雜的東西，但我問題原來是非線性的，簡單的線性方法似乎不起作用。因此，經過一整天的搜索，我找到了答案，希望這些發現對其他人有幫助。

我的問題：a [n + 1] = a [n] /（1 + a [n]）（即不是線性的（也不是多項式的），但也不是完全非線性的 - 它是一個有理差分方程）

1. 如果你的復發是線性的（或多項式），wikihow有一步一步的指示（有和沒有GF）
2. 如果你想閱讀一些關於GF，去this wiki，但我沒有直到我開始做實例（見下一個）
3. GF usage example on斐波那契
4. 如果前面的例子沒有意義，請下載GF book並閱讀最簡單的GF例子（1.1節，即a [n + 1] = 2 a [n] +1，則1.2，a [n + 1] = 2一個[n] +1，然後1.3 - 斐波那契）
5. （雖然我在書的主題）templatetypedef提到具體數學，下載here，但我不太瞭解它，除了它有一個循環，總和，和GF章節（除此之外）和一個簡單的GF表格在第335頁
6. 當我爲非線性材料做更深入的研究時，我看到this page，使用它我在z變換方法失敗並且沒有嘗試線性代數，但是鏈接到合理的區別eqn是最好的（見下一步）
7. 所以根據this page，合理的功能是不錯，因爲你可以將它們轉換成多項式，並使用步驟1和3和4的線性方法，這是我手工寫出來的，可能會犯一些錯誤，因爲（見8）
8. Mathematica（或者甚至是免費的WolframAlpha ）有一個復發求解器，其中RSolve[{a[n + 1] == a[n]/(1 + a[n]), a[1] == A}, a[n], n]讓我簡單的{{a[n] -> A/(1 - A + A n)}}。所以我想我會回去查找手工計算中的錯誤（它們對理解整個轉換過程如何工作很有幫助）。

無論如何，希望這有助於。