漸化式はいいぞ。(数列:漸化式)

どうも、クマと申します。
なれんじ氏が積分してるので私は数列を。
例題を解きながら漸化式を布教したいと思います。

基礎編

2項の単純な漸化式

例題1 次の漸化式で表される数列\(\{a_n\}\)の一般項\(a_n\)を\(n\)を用いて表せ。\((n \geqq 0,p\not=1)\)
\(a_0 = 0 , a_{n+1} = p a_n + q\)

超基礎ですね。
一応数項分書き出してみると下記のようになります。

\(a_1 = q\)
\(a_2 = pq + q\)
\(a_3 = p^2q + pq + q\)

どうでしょう?\(a_n\)は下のようになりそうですね。

\(a_n = q(p^{n-1}+p^{n-2}+…+p+1)\)

ただこう回答しては品がありません。(品性を疑う)
\(p\not=1\)な訳ですし、もう少しキレイに回答できますね。下の通りです。

[解] \(a_n = \frac{q(p^n-1)}{p-1}\)

こうすると\(n=0\)においても明らかに成り立ちますし、なによりキレイですね。

3項の単純な漸化式

例題2 次の漸化式で表される数列\(\{F_n\}\)の一般項\(F_n\)を\(n\)を用いて表せ。\((n \geqq 0)\)
\(F_0 = 0 , F_1 = 1, F_{n+2} = F_{n+1} + F_n\)

かの有名なフィボナッチ数列ですね。
3項になると解法を知らないと解けません。(たぶん)

回答 \(\alpha^2=\alpha+1\)を解くと\(\alpha=\frac{1\pm\sqrt{5}}{2}\)であるから、\( s=\frac{1+\sqrt{5}}{2} , t=\frac{1-\sqrt{5}}{2} \)とおくと\(F_{n+2} = F_{n+1} + F_n\)は下の2通りに変形できる。

\(F_{n+2} – tF_{n+1} = s(F_{n+1} – tF_n)\)
\(F_{n+2} – sF_{n+1} = t(F_{n+1} – sF_n)\)

\(S_n = F_{n+1} – tF_n , T_n = F_{n+1} – sF_n\)とおくと、\(\{S_n\}\)は初項\(S_0 = F_1 – tF_0 = 1\)、公比\(s\)の等比数列、\(\{T_n\}\)は初項\(T_0 = F_1 – sF_0 = 1\)、公比\(t\)の等比数列である。よって、\(S_n = s^n , T_n = t^n\)である。
ここで、\(S_n = F_{n+1} – tF_n , T_n = F_{n+1} – sF_n\)であるから、\(F_n=\frac{S_n-T_n}{s-t}\)。よって、\(F_n\)は下のように表される。

[解] \(F_n=\frac{1}{\sqrt{5}}\left\{\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right\}\)

無理やり等比数列に持っていくのがコツですね。一般に\(a_{n+2} + pa_{n+1} + qa_n = 0\)の形の漸化式は\(\alpha^2 + p\alpha + q = 0\)を解いて、その後上のように等比数列に持っていくことで解くことができます。

簡単な分数の形の2項の漸化式

例題3 次の漸化式で表される数列\(\{b_n\}\)の一般項\(b_n\)を\(n\)を用いて表せ。\((n \geqq 1)\)
\(b_1 = 1, b_{n+1} = \frac{b_n}{4b_n + 3}\)

分母が\(4b_n+3\)なのに対して、分子が\(b_n\)だけです。分子分母をひっくり返したくなりますよね?

回答 両辺の逆数を取ると、\(\frac{1}{b_{n+1}} = \frac{4b_n+3}{b_n} = 4 + \frac{3}{b_n}\)となる。
ここで\(B_n = \frac{1}{b_n}\)とおくと、\(B_{n+1} = 3B_n + 4\)であるから、\(B_n = 3^n – 2\)である。従って、\(b_n\)は下のようになる。

[解] \(b_n = \frac{1}{3^n – 2}\)

逆数を取り、\(b_n\)自体の逆数について考えると簡単に解けます。


応用編

\(n\)が出てくる漸化式

むずかしい(遺言)
未だにどう解けばいいのかよくわかってません。(:thinking_face:)

例題4 次の漸化式で表される数列\(\{c_n\}\)の一般項\(c_n\)を\(n\)を用いて表せ。\((n \geqq 1)\)
\(c_1 = 1 , c_{n+1} = 3c_n + 2n – 1\)

方針 3でくくれそうなので置換してくくる

回答 \(C_n = c_n + n\)とおくと、\(C_1 = 2 , C_{n+1} = 3C_n\)であるから、\(C_n = 2\cdot3^{n-1}\)より、\(c_n\)は以下のようになる。

[解] \(c_n = 2\cdot3^{n-1} – n\)

例題5 次の漸化式で表される数列\(\{d_n\}\)の一般項\(d_n\)を\(n\)を用いて表せ。\((n \geqq 1)\)
\(d_1 = -1, d_{n+1} = d_1 + 2d_2 + … + nd_n\)

方針 式変形で漸化式を簡単にする

回答 \(d_n = \sum_{i=1}^{n-1}id_i\)であるから、\(n \geqq 2\)において、次のように式変形できる。

\begin{eqnarray} d_{n+1} &=& \sum_{i=1}^{n}id_i \\
&=& \sum_{i=1}^{n-1}id_i + nd_n
&=& \sum_{i=1}^{n-1}id_i + n\sum_{i=1}^{n-1}id_i \\
&=& (n+1)\sum_{i=1}^{n-1}id_i \\
&=& (n+1)d_n \end{eqnarray}

ここで、\(d_2 = d_1 = -1 = -\frac{2!}{2}\)である。
よって、\(d_n\)は下のようになる。

[解] \(d_1 = -1, d_n = -\frac{n!}{2} (n \geqq 2)\)

(\(n\)が入ってる時って勘で解くしかなくないですか?おしえてえろいひと)

簡単な冪乗が出てくる漸化式

例題6 次の漸化式で表される数列\(\{p_n\}\)の一般項\(p_n\)を\(n\)を用いて表せ。\((n \geqq 1)\)
\(p_1 = 4, p_{n+1}^3 = \frac{p_n^2}{2}\)

方針 対数を取り指数を消す

回答 以下、対数の底は\(2\)とする。
\(P_n = \log p_n\)とする。このとき、漸化式の対数を取ると\(P_1=2 , 3P_{n+1} = 2P_n – 1\)である。
よって、自明に\(P_n = 3\cdot(\frac{2}{3})^{n-1} – 1\)となる。
以上より、\(p_n\)は下のようになる。

[解] \(p_n = 2^{3\cdot\left(\frac{2}{3}\right)^{n-1} – 1}\)

(対数取ったあと等比数列だと指数に指数乗るから気持ち悪さあるよね…ない?)


変則編

なんかよくわかんなかったり見た目がおもしろそうだったりする問題を乗せるコーナー

例題7 次の漸化式で表される数列\(\{q_n\}\)の一般項\(q_n\)を\(n\)を用いて表せ。\((n \geqq 1)\)
\(q_1 = 4, q_{n+1} = q_n^2 – 2\)

方針 \((c+\frac{1}{c})^2=c^2+2+\frac{1}{c^2}\)を使う

回答 \(c\)を実数とし、\(q_1 = c + \frac{1}{c}\)と置く。
このとき、\(q_n = c^{2^n} + \frac{1}{c^{2^n}}\)であることを数学的帰納法で示す。
まず、\(n=1\)の時は明らかに成り立つ。
次に、\(n=k\)で成り立つ、つまり\(q_k = c^{2^k} + \frac{1}{c^{2^k}}\)と仮定する。
このとき、\begin{eqnarray} q_{k+1} &=& q_k^2 – 2 \\
&=& (c^{2^k} + \frac{1}{c^{2^k}})^2 – 2 \\
&=& c^{2^{k+1}} + 2 + \frac{1}{c^{2^{k+1}}} – 2 \\
&=& c^{2^{k+1}} + \frac{1}{c^{2^{k+1}}} \end{eqnarray}であるから、\(n=k\)で成り立つ時、\(n=k+1\)でも成り立つ。
よって数学的帰納法より、\(n \geqq 1\)なる全ての\(n\)について\(q_n = c^{2^n} + \frac{1}{c^{2^n}}\)である。
あとは\(c\)を求めればよい。
\(q_1 = c + \frac{1}{c} = 4\)より\(c^2 – 4c + 1 = 0\)、これを解いて\(c=2\pm\sqrt{3}\)を得る。\(\frac{1}{2-\sqrt{3}}=2+\sqrt{3}\)であるから、\(q_n\)は下のようになる。

[解] \(q_n = (2+\sqrt{3})^{2^n} + (2-\sqrt{3})^{2^n}\)

(こんな解法思いつかんて)

例題8 次の漸化式で表される数列\(\{x_n\}\),\(\{y_n\}\),\(\{z_n\}\)の一般項\(x_n,y_n,z_n\)を\(n\)を用いて表せ。\((n \geqq 1)\)\(x_1 = \frac{1}{6} , y_1 = \frac{1}{3} , z_1 = \frac{1}{2}\)
\(x_{n+1} = \frac{y_n+z_n}{2} , y_{n+1} = \frac{z_n+x_n}{2} , z_{n+1} = \frac{x_n+y_n}{2}\)

方針 とりあえず全部足してみる

回答 \(x_{n+1} + y_{n+1} + z_{n+1} = x_n + y_n + z_n\)であるから、全ての\(n\)に対して\(x_n + y_n + z_n = x_1 + y_1 + z_1 = 1\)である。
ここで\(2x_{n+1} = y_n + z_n\)であるから、\(x_n + y_n + z_n = x_n + 2x_{n+1} = 1\)となる。これを解き、\(x_n = \frac{1}{3}(1 + \frac{1}{(-2)^n})\)を得る。同様に\(2y_{n+1} + y_n = 1\)より\(y_n=\frac{1}{3}\)であるから、\(z_n = 1 – x_n – y_n = \frac{1}{3}(1 – \frac{1}{(-2)^n})\)である。よって、解は以下のようになる。

[解] \begin{eqnarray} \left\{ \begin{array}{l} x_n = \frac{1}{3}(1 + \frac{1}{(-2)^n})\\
y_n=\frac{1}{3}\\
z_n = \frac{1}{3}(1 – \frac{1}{(-2)^n})\\ \end{array} \right. \end{eqnarray}

(解いててちょっと面白さ(?)あった)


途中から着地点見失ってますがなんかよくわかんない感じで終わります。
きっと布教できたことでしょう(なげやり)
みんなも赤チャート買おう!

コメント

  1. Bill より:

    I absolutely love your blog.. Pleasant colors &
    theme. Did you develop this site yourself? Please reply back as I’m hoping to create my
    very own blog and would like to find out where you got this from or exactly what the theme is
    called. Many thanks! Greetings from Ohio! I’m bored at work so I decided to browse your website on my iphone during lunch break.

    I love the information you present here and can’t wait to take a look when I
    get home. I’m shocked at how quick your blog loaded on my
    cell phone .. I’m not even using WIFI, just 3G ..
    Anyways, fantastic blog! Amazing! This blog looks exactly like my old one!

    It’s on a entirely different topic but it has pretty much the same page layout and design. Excellent choice of colors!
    http://goodreads.com/

  2. Thanks for sharing your thoughts about 数学.
    Regards http://www.fukuda-hp.net/category_1/item_1.html

  3. Woah! I’m really enjoying the template/theme of this site.
    It’s simple, yet effective. A lot of times it’s challenging to get
    that “perfect balance” between superb usability and visual appearance.
    I must say that you’ve done a amazing job with this. Additionally, the blog loads very quick for me on Safari.

    Outstanding Blog! http://summerlow.us/__media__/js/netsoltrademark.php?d=Oldehickorytaproom.com

タイトルとURLをコピーしました