Computer Transformation(2) - カメヲラボ

前回調べたn=1〜15の解を、数列aとしてみる。ちょっと数が多い気もするので、最初の10項程度書き並べると、

0, 1, 1, 3, 5, 11, 21, 43, 85, 171...

この数列の隣接2項を初項から順に足してみると、

 0 +   1 =   1
 1 +   1 =   2
 1 +   3 =   4
 3 +   5 =   8
 5 +  11 =  16
11 +  21 =  32
21 +  43 =  64
43 +  85 = 128
85 + 171 = 256

このように2^kになっていることがわかる。すなわち、この数列は

$a_{k+2} + a_{k+1} = 2( a_{k+1} + a_k )$

という漸化式で表すことができる。これは等比数列を表すから、
$a_{k+1} + a_k=2^{k-1}$ となり、さらに変形すると

$a_{k+1}=2^{k-1}-a_k (a_1=0)$

のように、隣接2項の漸化式で表すことができた。次は、ここから一般項を導いてみる。