目次
単純な漸化式
次のように定義される数式{a_n}の一般項を求めます。
$a_1=1, a_{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)1 1 1
2 5 5
3 9 9
4 13 13
5 17 17簡単な漸化式は、再帰関数で計算することができます。
少し複雑な漸化式
次のように定義される数式{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)1 3 3
2 14 14
3 49 49
4 156 156
5 479 479少し複雑なものでも簡単に計算できます。
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))1 1 1
2 2 2
3 19 19
4 68 68
5 421 4213項間漸化式でも計算できてしまいました。
