Pythonで漸化式を解く

Pythonは漸化式の計算に非常に便利な言語です。以下に、いくつかの基本的な漸化式の例を示します。

単純な漸化式

次のように定義される数列{a_n}の一般項を求めます。

$$a_1=1,\u3000\u3000\u3000\u3000a_{n+1}=a_n+4$$

漸化式を解くと一般項は次の通りです。

$$a_n=4n-3$$

これをPythonの再帰関数と一般項の式を使って、n=1から5まで計算し比較します。

def recurrence(n):
    if n ==1:
        return 1
    else:
        return recurrence(n-1)+4

for i in range(1,6):
    print(i,recurrence(i),4*i-3)

少し複雑な漸化式

次のように定義される数列{a_n}の一般項を求めます。

$$a_1=3,\hspace{5pt}a_{n+1}=3a_n+2n+3$$

$$a_n=2\cdot3^n-n-2$$

def recurrence(n):
    if n ==1:
        return 3
    else:
        return 3*recurrence(n-1)+2*(n-1)+3

for i in range(1,6):
    print(i,recurrence(i),2*3**(i)-i-2)

3項間漸化式

次のように定義される数列{a_n}の一般項を求めます。

$$a_1=1,a_2=2\hspace{5pt}a_{n+2}=2a_{n+1}+15a_n$$

$$a_n=\displaystyle \frac{5^n-(-3)^n}{8}$$

from fractions import Fraction

def recurrence(n):
    if n ==1:
        return 1
    if n==2:
        return 2
    else:
        return 2*recurrence(n-1)+15*recurrence(n-2)

for i in range(1,6):
    print(i,recurrence(i),Fraction(5**i-(-3)**i,8))

これらの例からわかるように、Pythonは漸化式の計算に非常に便利な言語です。再帰関数を使うことで、様々な漸化式を簡単に計算することができます。.