漸化式をできるだけたくさん紹介する記事

本気を出す数学B

漸化式を解くのはとても楽しいです。なので解きましょう。簡単な数列から、有名な数列まで。漸化式の難易度を$(Lv.x)$で表します。

等差数列の一般項$(Lv.1)$

$n$番目の項を$a_n\ (n\in\mathbb{Z^+})$と表すことにします。

定義の右辺を順番に展開していくと導けます。一応、$n,k$ともに整数として見ることができます。

等比数列の一般項$(Lv.1)$

これも帰納的に導けます。

特性方程式を解くやつ$(Lv.1)$

よく、$a_{n+1}=pa_n+q\ \cdots (A)$ とされてるやつの一般項です。特性方程式の立て方から一般項まで。今回は初項$a_1$の場合のみ紹介します。

$Mustn't$暗記。こんな公式覚えるくらいなら$(B)$と$(C)$の形を覚えたほうが身のためやで。
以下出てくる漸化式はすべて一般的な解はそう簡単に存在しません。注意してね。

階差数列を持つタイプ$(Lv.2 )$

ある項と直後の項の差をとったものを階差数列と呼びましたね。形としては、
$a_{n+1}=a_n+f(n)$です。$f(n)$が$a_n$の階差数列となってます。

ほとんどの場合$n≧1$でまとまっちゃう。基本こういうのはシグマ公式で処理します。形だけ似た別物がいるので紹介。

階差数列っぽい違うやつ$(Lv.3)$

このパートで説明する漸化式の形は、
$a_{n+1}=pa_n+f(n)$です。$p\neq 1$となっているので解き方は上とは異なります。
解き方は、もちろん特性方程式みたいに変形できる前提として、
$$a_{n+1}+g(n+1)+α=β(a_n+g(n)+α)$$
にできれば解決。$a_n+g(n)+α$をカタマリとして見るので、左辺では$g(n)$が$g(n+1)$になるように、ずれている必要があります。
今回はたくさん紹介したいので、演習問題は他の方々のサイトに委ねます。

指数が入ったやーつ$(Lv.3)$

$a_{n+1}=pa_n+qr^n$のような形です。数字をずらすための工夫がいるので、大体こういうのは$p^{n+1}$で割って$b_{n}=\frac{a_n}{p^n}$として階差数列を作るタイプにするか、$r^{n+1}$で割って$b_n=\frac{a_n}{r^n}$として特性方程式を作れる形にします。大体誘導付きだそうです。

逆数にする形$(Lv.2 )$

$$a_{n+1}=\frac{pa_n}{qa_n+r}$$
基本誘導つき。両辺逆数をとりましょう。ここで、必ず$a_1$と漸化式の形から$a_n\neq 0$であることを断ってください。じゃないと、ね。分かるね。
$\displaystyle \frac{1}{a_{n+1}}=\frac{q}{p}+\frac{r}{p}\cdot\frac{1}{a_n}$となるので、$\displaystyle b_n=\frac{1}{a_n}$とおけば特性方程式が作れる形になります。

階...比...数列?を含む形$(Lv.4)$

例のサイトでの呼称です。お借りします。
$a_{n+1}=f(n)a_n$
大学の総乗記号を使うと、一般項が総乗でつくれます。

総乗記号を詳しく知りたい方は、...調べましょう。簡潔に言えば、$\Sigma$の掛け算verです。
高校生の解き方としては、帰納的に解くか、数字が合うようにうまく調整するか。つまり$g(n+1)a_{n+1}=g(n)a_n$にすれば勝ちです。

次数ずれ$(Lv.3)$

$a_{n+1}=pa_n^q$の形。次数が違う。そうです。
両辺底が$p$とか$\sqrt{p}$とか$a_1$の対数をとりましょう。もちろん真数条件も確認しましょう。誘導? ついてるっしょ。さすがに。

隣接三項間$(Lv.5)$

いよいよ来ました。正直数学好き向けです。解き方にはセオリーがいろいろあるんですが、覚える容量を減らしたいならば、未定係数法。特性方程式やそれっぽい形にします。
$a_{n+2}+f(n+1)a_{n+1}+g(n+1)=β(a_{n+1}+f(n)a_n+g(n))$という形に変えられれば勝利。($f(n)$や$g(n)$が定数であればもっと簡単。)二つ新たな漸化式が出てくるのでそれらをそれぞれ解いて連立させて$a_n$が求まります。ちなみに隣接$n$項間漸化式では初項が$n-1$個定まっています。じゃないと解けない。

和を含むタイプ$(Lv.2 )$

$a_1+a_2+\cdots +a_n=S_n$とすれば、$S_{n}+a_{n+1}=S_{n+1}$。以上。これを使って攻略してね。基本初項がないタイプです。あと$S_1=a_1$(初項)。

その他の形

誘導付きじゃなきゃ出ないってくらい難しいものもあります。一応形だけ紹介。
1.一次分数型漸化式$(Lv.6)$
$$a_{n+1}=\frac{pa_n-q}{ra_n-s}$$
これにも特性方程式があるのですが、参考文献のほうに掲載いたしますので。そこから「一次分数型」を探してください。

2.連立漸化式$(Lv.4)$
$$a_{n+1}=αa_n+βb_n+γ\ ,\ b_{n+1}=δa_n+εb_n+ζ$$
定数がない場合が多いかも。解き方は参考文献から。場合によっては三元連立版$(Lv.7)$もあります。

3.変数変換型漸化式$(Lv.10)$
$$\mathrm{e.g.}\ \ a_{n+1}=2a_n^2-1$$
漸化式ガチャ超級を解いてる方なら一発でお見通しでしょうが、まあ難しい。初見じゃわからない人が多いです。私が作る立場なら誘導付きで作ります。確実に!!

4.ガウス記号を含む漸化式$(Lv.13)$
漸化式ガチャ超級を引いてください。そうしたら恐ろしさが分かります。多分誘導あっても出ないでしょう。出るな!!

5.隣接"四"項間漸化式$(Lv.8)$
$$\mathrm{e.g.}\ \ a_{n+3}+αa_{n+2}+βa_{n+1}+γa_n=δ$$
方針は比較的読みやすいです。数字がずれるように変形してから階差数列の一般項をつくって...長い。

6.一般項が求められない漸化式$(Lv.99999999...)$
$$\mathrm{e.g.}\ \ a_{n+1}=\lfloor\ \frac{n!}{a_{n}^{\sqrt{a_n}^{(n^{n})!}}}\sum_{k=1}^{n}k^ka_k^{(n^{k^{3}})!}\ \rfloor$$
解けないなら解けないで終わりです。この例が解けたら教えてください。深夜テンションで作った漸化式なので。

演習問題

ここまで解法を紹介してきましたが、一般項を推測→数学的帰納法で証明、もありなので。
$(1)$ $\displaystyle a_1=2\ ,\ a_{n+1}=3a_n-1$
$(Lv.2)$ヒント: $a_n-α$の形を作って等比数列の形に持ち込む

$(2)$ $\displaystyle a_1=1\ ,\ a_{n+1}=2a_{n}-n$
$(Lv.3)$ヒント: 両辺それぞれ$n+1,n$の式を作る

$(3)$ $\displaystyle a_1=1\ ,\ a_{n+1}=(n+1)^2a_n$
$(Lv.4)$ヒント: 対数をとってしまうと$(n+1)^2$が対数の中身になってしまうので別の処理を考える

$(4)$ $\displaystyle F_1=1\ ,\ F_2=1\ ,\ F_{n+2}=F_{n+1}+F_n$
$(Lv.5)$ヒント: フィボナッチ数列。ちゃんと両辺$n+2,n+1\ ,\ n+1,n$の形を作って階差数列を出す

$(5)$ $\displaystyle a_1=\frac{4}{9}\ ,\ a_{n+1}=a_n^2$
$(Lv.3)$ヒント: 次数のずれは基本的に対数で解消せよ

$(6)$ $\displaystyle S_n=2(a_n+n)-3\ \ \left(S_n=\sum_{k=1}^{n}a_k\right)$
$(Lv.2)$ヒント: $S_{n+1}$を作って初項や普通の漸化式を生み出す

$(7)$ $\displaystyle a_1=\sqrt{3}\ ,\ a_{n+1}=a_n(a_n^2-3)$
$(Lv.10)$ヒント: いかに形に気付けるか。気づいたら$a_n=f(b_n)$のような形として変数変換を行う。

$(8)$ $\displaystyle a_1=1\ ,\ a_k=0\ (k≧2,k\in\mathbb{N})$ を一つの閉形式の一般項$a_n$で表せ。
$(Lv.??)$ヒント: 気づけたら天才。別解もおそらく存在する。

演習解答

(1)
$\displaystyle a_{n+1}=3a_n-1\Longleftrightarrow a_{n+1}-\frac{1}{2}=3\left(a_n-\frac{1}{2}\right)$と変形できるので、
$a_n-\frac{1}{2}=b_n$とすると$b_1=\frac{3}{2}$より、
$\displaystyle b_n=b_13^{n-1}=\frac{1}{2}\cdot 3^n$
したがって、$\displaystyle a_n=\frac{1}{2}\left(3^n+1\right)$

(2)
$\displaystyle a_{n+1}=2a_n-n$
$a_{n+1}+α(n+1)+β=γ(a_n+αn+β)$として展開し整理すると、
$a_{n+1}=γa_n-(α-αγ)n+(βγ-α-β)$
係数比較して$γ=2\ ,\ α=-1\ ,\ β=-1$
よって漸化式を変形すると、$a_{n+1}-(n+1)-1=2(a_n-n-1)$
$a_n-n-1=b_n$とおくと$b_1=-1\ ,\ b_{n+1}=2b_n$
すなわち$b_n(=a_n-n-1)=-2^{n-1}$であるから、
$a_n=n-2^{n-1}+1$

(3)
$\displaystyle a_{n+1}=(n+1)^2a_n$
【解法1】
$a_{n+1}=(n+1)^2a_n$より$a_n=n^2a_{n-1}$
よって$a_{n+1}=(n+1)^2n^2a_{n-1}=(n+1)^2n^2(n-1)^2a_{n-2}$
$=\cdots=(n+1)^2n^2(n-1)^2\cdots 2^2\cdot a_1=(n+1)!^2$
よって、$a_n=(n!)^2$
【解法2】
漸化式の両辺を$(n+1)!^2$で割ると、
$$\frac{a_{n+1}}{(n+1)!^2}=\frac{(n+1)^2a_n}{(n+1)^2\cdot (n!)^2}$$
$\displaystyle \frac{a_{n}}{(n!)^2}=b_n$とおくと、$b_{n+1}=b_n=b_{n-1}=\cdots=b_1=1$
したがって$\displaystyle \frac{a_{n}}{(n!)^2}=1$より、$a_n=(n!)^2$

(4)
$F_{n+2}-αF_{n+1}=β(F_{n+1}-αF_n)$を展開して整理すると、
$F_{n+2}-(α+β)F_{n+1}+αβF_n=0$
これは解と係数の関係と一致するため、$x^2-x-1=0$の二つの解が$x=α,β$となる。つまり$α$と$β$の位置の交換が可能なので、
$$ \begin{eqnarray} \left\{ \begin{array}{l} F_{n+2}-αF_{n+1}=β(F_{n+1}-αF_n) \\ F_{n+2}-βF_{n+1}=α(F_{n+1}-βF_n) \end{array} \right. \end{eqnarray} $$
それぞれについて漸化式を解くと、
$$ \begin{eqnarray} \left\{ \begin{array}{l} F_{n+1}-αF_n=(1-α)β^{n-1} \\ F_{n+1}-βF_n=(1-β)α^{n-1} \end{array} \right. \end{eqnarray} $$
辺々引くと、$\displaystyle (β-α)F_n=(1-α)β^{n-1}-(1-β)α^{n-1}$
ここで、$x^2-x-1=0$について$\displaystyle α=\frac{1-\sqrt{5}}{2}\ ,\ β=\frac{1+\sqrt{5}}{2}$とすると、
$$\sqrt{5}F_n=\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n$$
よって、$\displaystyle F_n=\frac{1}{\sqrt{5}}\left\{\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right\}$

(5)
$a_{n+1}=a_n^2$に関して両辺底$2$の対数をとると、
$\log_2{a_{n+1}}=2\log_2{a_n}$となるので、$\log_2{a_n}=b_n$とおく。
$b_{n+1}=2b_n$より、$\displaystyle b_n=b_1\cdot 2^{n-1}=2^{n-1}(2\log_2\frac{2}{3})=2^n(\log_2\frac{2}{3})$
よって、$\displaystyle a_n=2^{2^n(\log_2\frac{2}{3})}=\left(\frac{2}{3}\right)^{2^n}$

(6)
$S_n=2a_n+2n-3$より、$S_{n+1}=2a_{n+1}+2n-1$
辺々引くと、$a_{n+1}=2a_{n+1}-2a_n+2\Longleftrightarrow a_{n+1}=2a_n-2\Longleftrightarrow a_{n+1}-2=2(a_n-2)$
ここで、初項は$S_1=a_1$から$a_1=2a_1-1\Longleftrightarrow a_1=1$
よって、$a_n-2=-2^{n-1}$から、$a_n=2(1-2^{n-2})$

(7)
$a_{n+1}=a_n^3-3a_n$に関して、$a_n=2\cos{θ_n}$とおくと、$θ_1=\frac{π}{6}$より、
$2\cos{θ_{n+1}}=8\cos^3{θ_n}-6\cos{θ_n}\Longleftrightarrow \cos{θ_{n+1}}=4\cos^3{θ_n}-3\cos{θ_n}$
ここで、$\cos{3θ}=\cos{θ}\cos{2θ}-\sin{θ}\sin{2θ}=\cos{θ}(2\cos^2{θ}-1)-2\sin^2{θ}\cosθ=2\cos^3{θ}-\cos{θ}-2(1-\cos^2{θ})\cos{θ}$
$=4\cos^3{θ}-3\cos{θ}$より、$\cos{θ_{n+1}}=\cos{3θ_n}$
角度の部分が等比数列なので、$θ_{n}=\frac{π}{6}\cdot 3^{n-1}=\frac{3^{n-2}}{2}π$
したがって、
$$\displaystyle a_n=2\cos{\frac{3^{n-2}}{2}π}$$

(8)(解説略)
$a_n=\tan(4^{n-2}π)$

演習小話

(1)は基本的な問題です。(2)はナンバリングがずらせるかがポイント。(3)は帰納的に解くことをお勧めします。早々階乗で割るなんてアイデア出ない。(4)はかの有名なフィボナッチ数列の一般項を求める問題。$α,β$ともに黄金数と直接的な関わりを持ちます。(5)は対数の性質がわかっていればよいです。(6)は和の性質がわかればよいです。(7),(8)は何となくわかればいい...?

漸化式は解きまくれ!

数をこなしてこそ漸化式や積分に強くなれます。漸化式,積分,因数分解,極限ガチャで強くなりましょう!!