※完全に記録用です。
漸化式から一般項を求めるいい練習になりましたが。
今回は以下のような数列を考えます。
{an}=1,2,3,5,7,11,15,23,31,47,63,95,127,…
見ての通り、最初のほうは1と15を除き素数が並びます。47くらいまで数列を出して15を「?」にしておけばおそらく半数以上の人が13,17で迷うはずです。
1. 数列の特徴
まずは数列の特徴を軽く押さえておきます。
どう見ても等間隔ではないので等差数列ではありませんし、素数も多数含まれているので等比数列もありえません。そこで各項の差を取ってみます。
an=1,2,3,5,7,11,15,23,31,47,63,95,…より、a2−a1=1a3−a2=1a4−a3=2a5−a4=2a6−a5=4a7−a6=4a8−a7=8a9−a8=8a10−a9=16a11−a10=16a12−a11=32…
このようにすると、数列の特徴がよくわかります。言葉で説明すると、「1から始めて2回繰り返したら倍になるという法則で増える数列」です。
2. 階差数列の一般項を求める(1)
数列の差に関しての法則があれば階差数列を求めることができます。階差数列が求まれば、そこから元の数列の一般項を求められます(下記の補足参照)。
※以下、{an}の階差数列を{bn}とします。
まずは{bn}を書き出して、少し変形しておきます。
{bn}=1,1,2,2,4,4,8,8,16,16,32,32,64,64,…=20,20,21,21,22,22,23,23,24,24,25,25,26,26,27,27,…
指数が1回おきに1増えるので、floor関数(切り捨て)を使えば一般項は下のように書けます。
bn=2⌊2n−1⌋
n=1のときは20=1、n=2のときは⌊21⌋=⌊0.5⌋=0∴2⌊21⌋=1のように代入するとしっかりbnが現れます。
【補足】階差数列から元の数列の一般項を求める方法
階差数列の定義より、bn=an+1−anよって、b1=a2−a1,b2=a3−a2,…より、a1+b1=a2,a2+b2=a3,…,an−1+bn−1=anここで、a2,a3,…,an−1にbnの式を代入すると、an=a1+b1+b2+b3+b4+…+bn−1b1+b2+…+bn−1をまとめると、an=a1+k=1∑n−1bkしたがって、k=1∑n−1bkを求めればanも求まる。
3. 階差数列の一般項を求める(2)
bn=2⌊2n−1⌋ がわかったのは良いですが、最終的にanを求めるためにはbnの部分和を計算する必要があります。しかし、∑の計算においてn乗の公式はありますが「n(小数を切り捨て)乗」という公式はありません(何なら切り捨てのfloor関数は初等関数ですらありません)。これを何とかするべく、式を変形します。
まずは条件分岐の場合分けで考えます。
n−1が偶数、つまりnが奇数の場合は2n−1をそのまま入れればよいですが、n−1が奇数、つまりnが偶数の場合は切り捨てになるので2n−1−0.5=2n−1となります。この考え方を使うと、以下の式が導けます。
bn=⎩⎨⎧22n−1 (nは奇数)22n−1 (nは偶数)
これらを比較すると、nが偶数の場合にのみ21を引けばよいことになります(2n−1−21=2n−2=2n−1)。
ここで、次のような式を考えます。
(1) : 21−(−1)n (2) : 21+(−1)n
(1)の式はnに奇数を代入すると1、偶数を代入すると0を出力します。(2)の式はこの逆で、偶数を代入すると1、奇数を代入すると0と出力します。これは(−1)nがnが奇数なら−1、nが偶数なら1を出力するというように数式で数の偶奇を判別できることを利用しています。
今回はnが偶数の場合のみ21を引きたいので、指数部分は、
2n−1−21⋅21+(−1)n=42n−2−(1+(−1)n)=42n−3−(−1)n
21を引くところに偶奇の判断を入れて掛けておけばどちらか一方のみ演算ができるという考え方です。
したがって、初等関数で表した{bn}の一般項は以下のようになります。
bn=242n−3−(−1)n
4. Σを計算する
bnが分かったので、いよいよanの一般項を求めていきます。まずはk=1∑n−1bkを求めます。
※指数部分が非常に見づらかったので数式部分は拡大で書いています
※mは自然数、Mは2M+1,2M>0を満たす整数とします
bk=242n−3−(−1)nにおいて、k=2m−1のときは242(2m−1)−3−(−1)2m−1=244m−2−3+1=2m−1k=2mのときは242⋅2m−3−(−1)2m=244m−3−1=2m−1
このことから、
k=1∑n−1bkにおいてn−1の偶奇で分けると、n−1=2Mのときk=1∑n−1bk=m=1∑M(b2m−1+b2m)=2m=1∑M2m−1=2(2M−1)=2M+1−2=22n+1−2n−1=2M+1のときk=1∑n−1bk=m=1∑M(b2m−1+b2m)+b2M+1=2m=1∑M2m−1+2M=2M+1−2+2M=2⋅2M+2M−2=3⋅2M−2
これをまとめると、
k=1∑n−1bk=⎩⎨⎧22n+1−1 (nは奇数)3⋅22n−1−1 (nは偶数)
5. 計算結果を1つにまとめる
k=1∑n−1bk={22n+1−1 (nは奇数)3⋅22n−1−1 (nは偶数)が分かったので、次はこれを(−1)nを利用して一つの式にまとめます。今回は偶数、奇数どちらの式も利用します。ここで1つのテクニックとして、−2は共通しているので移項してから計算します(面倒な展開をしなくて済みます)。
2+k=1∑n−1bk=22n+1⋅21−(−1)n+3⋅22n−1⋅21+(−1)n=22n−1−22n−1⋅(−1)n+3⋅22n−2+3⋅22n−2⋅(−1)n=3⋅22n−2+22n−1+(−1)n⋅(3⋅22n−2−22n−1)∴ k=1∑n−1bk=3⋅22n−2+22n−1+(−1)n⋅(3⋅22n−2−22n−1)−2
6. 数列の一般項
k=1∑n−1bkが求まったので、2.の補足のやりかたでanを求めることができます。
※初項は最初に提示した数列からa1=1とわかります
an=a1+k=1∑n−1bk=1+k=1∑n−1bk=3⋅22n−2+22n−1+(−1)n⋅(3⋅22n−2−22n−1)−1
最終的な一般項は下のようになります。
an=3⋅22n−2+22n−1+(−1)n⋅(3⋅22n−2−22n−1)−1
最初の規則的な並びからは想像もできない複雑な式ですが、特殊な方法で漸化式を解くと大体こうなることが多い気がします。(−1)nは「2回に1回(階差数列が)増える」などということをいうときによく使われる条件分岐の項です。
7. テクニック集
(1) -1のn乗を利用した条件分岐
21−(−1)n:nが奇数なら1,偶数なら021+(−1)n:nが奇数なら0,偶数なら1
一般に、A={f(n) (nが奇数)g(n) (nが偶数) のとき、
A=f(n)⋅21−(−1)n+g(n)⋅21+(−1)n
(2) Σの計算の偶奇分け
k=1∑nckにおいて、ck=c2m−1+c2mを利用することで計算できる場合がある。
8. 数列の第50項までの数
参考までに、数列の数を50項まで書いておきます。
1, 2, 3, 5, 7,
11, 15, 23, 31, 47,
63, 95, 127, 191, 255,
383, 511, 767, 1023, 1535,
2047, 3071, 4095, 6143, 8191,
12287, 16383, 24575, 32767, 49151,
65535, 98303, 131071, 196607, 262143,
393215, 524287, 786431, 1048575, 1572863,
2097151, 3145727, 4194303, 6291455, 8388607,
12582911, 16777215, 25165823, 33554431, 50331647
5個ずつ区切っています。
素数が多いのは奇数項は必ず2^m-1の形になるからかな?というのが私の見解です。【一般項を利用して数列の各項を出すpythonプログラム】
def seq(n,list_flag=True):
res = []
for i in range(1,n+1):
a = 3 * (2 ** (i/2 - 2)) + 2 ** ((i-1)/2)
b = 3 * (2 ** (i/2 - 2)) - 2 ** ((i-1)/2)
if list_flag == True:
res.append(int(a + ((-1)**i)*b) - 1)
else:
print(int(a + ((-1)**i)*b) - 1)
if list_flag == True:
return res
# seq(表示個数) で実行、そこまでの数列をリストで返す
# ただし、第二引数はFalseを指定するとリストを返さずにprintで表示
# (第二引数は初期値True,指定しなくても可)