Jacobsthal數遞回公式-有解無憂

我有一個非常簡單（而且愚蠢:) 的問題：

我如何從這個運算式中得到：

Jacobsthal數遞回公式

到這個遞回公式？

Jacobsthal數遞回公式

我不想要任何完整的解決方案，但也許您可以通過一些提示幫助我理解它。

謝謝，美好的一天:)

uj5u.com熱心網友回復：

這與[維基百科]：斐波那契數非常相似，是一個典型的[維基百科]：數學歸納示例。

從公式對（給定的）n成立的假設開始（我們稱之為P(n)）：

J_n = 2 * J_{n - 1} (-1)^{n - 1}

然后，使用上述等式和函式定義，您必須證明P(n 1) - 該公式對于（連續的）n 1也成立。這是你問題中的一個：

J_{n 1} = 2 * J_n (-1)ⁿ

由于這是一個編程站點（而且我懶得手動計算前幾個值），這里有一些Python代碼可以為我們執行此操作：

>>> def j(n):
...     if n <= 0:
...         return 0
...     elif n == 1:
...         return 1
...     else:
...         return j(n - 1)   2 * j(n - 2)
... 
>>>
>>> for i in range(15):
...     print("{:2d} - {:4d}".format(i, j(i)))
...
 0 -    0
 1 -    1
 2 -    1
 3 -    3
 4 -    5
 5 -   11
 6 -   21
 7 -   43
 8 -   85
 9 -  171
10 -  341
11 -  683
12 - 1365
13 - 2731
14 - 5461

從上面可以看出，這個公式是正確的，肉眼可見。
現在應該應用歸納機制：從P(n) 開始并使用函式定義（^第三個分支）到達P(n 1)。考慮到存在 2 級依賴關系（大多數術語最終會相互減少，但我沒有嘗試查看它的“可見性”），這可能不是微不足道的。
您可以查看[SO]: Recursive summation of a sequence of return wrong result (@CristiFati's answer)，了解有關更簡單問題的更多詳細資訊。

注意：

鑒于當前的系數，我必須提到遞回的特征方程（檢查 [ \Wikipedia]: Constant-recursive sequence），它將給出一個非回圈公式：J_n

J_n = J_{n - 1} 2 * J_{n - 2}轉換為：-> （以 -1 和 2 作為根），從這里（使用Binet（或Moivre）公式）：x² = x¹ 2 * x⁰x² - x - 2 = 0

J_n = (2ⁿ - (-1)ⁿ) / 3（分母值為：2 - -1）

讓計算機從我們這里做一些計算（檢查之前的實作結果是否與這個匹配）：

>>> def j_simpl(n):
...     return (2 ** n - (-1) ** n) / 3
...
>>>
>>> print(all(j(i) == j_simpl(i) for i in range(20)))
True

轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/364976.html

標籤：递归数学

上一篇：對這個python程式有一些疑問（PRIMEorNOT）

下一篇：以二進制計算二項式系數