漸化式や数列、高速部分積分などまとめ

「漸化式」や「数列」、「積分」のコツをお話ししたいと思います。なお、あまりにも当然のことは省いていますのでご了承ください。

Xn+1=AXn+f(n)

当たり前ですが、A=1でf(n)の次数d=0のとき、ただの等差数列です。また、A=1でd>0のときは、階差数列ですよね。主にここではA≠1のときをみてみますが、基本的に、Xn-f(n)=α(Xn-1-f(n-1))の等比数列に持ち込むことが多いですね。(f(n)はnを含む多項式。)

Xn=Xn-1+Bn-Cのとき、Xn-Xn-1=Bn-Cとなります。同様にして、
Xn-1-Xn-2=B(n-1)-C
Xn-2-Xn-3=B(n-2)-C

X1-X0=B-Cとなるわけです。これを足していくと、きれいに途中の項が消しあってくれます。結果として、Xn-X0=Σ(1→n) Bk-Cが導かれますね。これが階差数列でした。

【重要】d=0のとき

Xn+1=AXn+B

Xn+1-α=A(Xn-α)…(1)という定石パターンに持ち込みます(f(n)=α(=定数))。Yn=Xn-αとすれば、公比aの等比数列になりますからね。(1)を展開すれば、

Xn+1-α=AXn-αA
⇔Xn+1=AXn-αA+α
つまり、-αA+α=B⇔α=Aα+Bを満たすαを求めればオッケーです。

d>0のとき

Xn+1=AXn+Bn-C

Xn+1-α(n+1)-β=A(Xn-αn-β)となるように、適切なα及びβを設定して変形します(f(n)=αn+β)。

【重要】三項間漸化式

Xn+2=AXn+1+BXn

Xn+2-αXn+1=β(Xn+1-αXn)…(2)の定石パターンに持ち込みます。

(2)を整理すると、Xn+2-(α+β)Xn+1+αβXn=0なので、
X2=AX+Bの2解がα、βということになります。2解をx1,x2(x1<x2)として、(α,β)=(x1,x2),(x2,x1)のそれぞれにおいて(2)式をつくります。その2式を引くことによって、Xn+2の項を消去することができますね。

また、一般的に、Xn=Cαn+Dβn(C,Dは定数、α,βは前述の2解)…(3)が成り立つことも重要です。n=0,1のときに(3)が成り立つように、C,Dを設定してあげます。

【重要】2数列の連立漸化式

以下、(4),(5)の連立漸化式を考えます。
Zn=AYn-1+BZn-1+C…(4)

Yn=DYn-1+E…(5)

Zn-αYn-β=γ(Zn-1-αYn-1-β)の形に持ち込めばオッケーですね。f(n)=αYn+βとなるように、αとβを適切に設定してあげるだけです。

階乗や累乗がある場合

Xn+1=AXn+Bn

のときは、両辺をBn+1で割って、Yn=Xn/Bnを作ります。
Yn+1=(A/B)Yn+(1/B)となり、(1)に持ち込めます。n!の場合も、同じように(n+1)!で両辺を割って、、Yn=Xn/n!を作ります。

【重要】漸化式確率

コインを投げて裏が2回連続で出たら終了する試行を考えます。表の確率をq、裏の確率を1-qとします。このとき、n回目でやめる確率Pnを求めます。直前との関係性がつかみにくい場合は、1回目の試行のときに場合分けして考えるのが基本です。

Pn=q*Pn-1+(1-q)q*Pn-2となります。

右辺第1項は、1回目が表の場合です。残りのn-1回で終了する確率はPn-1と同じですよね。右辺第2項は1回目が裏の場合です。しかし、同様にPn-1をかけてはいけません。もしも2回目が裏だった場合終了してしまうからです。だから、2回目が表であるという条件も必要なのです。これは、Pnという確率に1回目が表であるという条件がないからですね。

【重要】等比数列の和の公式

初項a,公比rの等比数列の和Sを求めます。

S=a+ar+ar2…arn-1…(1)
rS=   ar+ar2…arn-1+arn…(2)

(1)-(2)より、S=(a-arn)/(1-r)ですね。n→∞のとき(|r|<1)は、a/(1-r)となります。イメージとして、(初項ー末項*公比)÷(1-公比)と考えましょう。

【重要】等差数列×等比数列の和の公式

Xk=krkなどの場合です。といっても、考え方は先ほどと同じです。

S=r+2r2…nrn…(3)
rS= r2…(n-1)rn+nrn+1…(4)

(3)-(4)より、(1-r)S=r+r2…rn-nrn+1となり、右辺に初項r、公比rの等比数列が現れますね。

Σxprxのような累乗×等比数列のパターンも同様にして導けます。

高速部分積分

∫x2e-xdxを求めてみましょう。

+ x2 -e-x
– 2x e-x
+ 2 -e-x

から、(-x2e-x)-(2xe-x)+(-2e-x)+Cとなります。

1列目は+,-を交互に書いていきます。2列目は部分積分の片方をどんどん微分していきます。3列目はもう片方を積分していきます。ただし、3列目の1行目は既に1回積分してからはじめてください。そして2列目にxがなくなるまでこの作業を続けます。最後に、各行の結果に1行目の正負をかけたものをすべて足すと積分の完成です。このやり方は高速部分積分と呼ばれ、部分積分のプロセスを簡略化したものです。

奇関数、偶関数

正規分布関連の問題などは、奇関数や偶関数の性質を使うことが多いので忘れないようにしておきましょう。

もったいないミスを防ぐ!9つの計算ミス対策とは?

広告

さあ、友人にも教えてあげよう!

カテゴリー別記事一覧
広告
トップへ戻る