← 定理辞典📖 定理辞典

数列・Σ・漸化式・帰納法

漸化式と一般項

「前の項から次の項を作る規則」が漸化式。an+1=pan+qa_{n+1}=pa_n+q 型は特性方程式 α=pα+q\alpha=p\alpha+q の解 α\alpha を引くと等比数列に化け、一般項 an=(a1−α)p n−1+αa_n=(a_1-\alpha)p^{\,n-1}+\alpha が出る。

主張

漸化式は「初項」と「前の項から次の項を作る規則」で数列を定める式だよ。規則さえあれば a1,a2,a3,…a_1,a_2,a_3,\dots と順にいくらでも作れる。基本は 33 型。差が一定の an+1=an+da_{n+1}=a_n+d(等差)、比が一定の an+1=rana_{n+1}=ra_n(等比)、そして一番よく出る an+1=pan+qa_{n+1}=pa_n+q(p≠1p\ne1)。この最後の型は、特性方程式 α=pα+q\alpha=p\alpha+q を解いて得た定数 α\alpha(変わらない値=不動点)を両辺から引くと、an+1−α=p(an−α)a_{n+1}-\alpha=p(a_n-\alpha) となって、{an−α}\{a_n-\alpha\} が公比 pp の等比数列に化ける。あとは等比数列の一般項を使えば、nn 番目をいきなり求める式(一般項)an=(a1−α)p n−1+αa_n=(a_1-\alpha)p^{\,n-1}+\alpha が手に入るんだ。

an+1=pan+q (p≠1) → α=pα+q  an+1−α=p(an−α)⟹ an=(a1−α) p n−1+α\begin{gathered}a_{n+1}=pa_n+q\ (p\ne1)\ \xrightarrow{\ \alpha=p\alpha+q\ }\ a_{n+1}-\alpha=p(a_n-\alpha)\\[4pt]\Longrightarrow\ a_n=(a_1-\alpha)\,p^{\,n-1}+\alpha\end{gathered}
a₁a₂a₃a₄
初項から規則(漸化式)を 11 回ずつ使うと、a1→a2→a3→a4a_1\to a_2\to a_3\to a_4 と次々に項が決まっていくよ。

成り立つ条件

特性方程式 α=pα+q\alpha=p\alpha+q が解 α=q1−p\alpha=\dfrac{q}{1-p} を持つには p≠1p\ne1 が必要(これが an+1=pan+qa_{n+1}=pa_n+q 型を等比に直せる条件)。p=1p=1 のときは an+1=an+qa_{n+1}=a_n+q で、これはただの等差数列(公差 qq)として別に扱う。初項 a1a_1 が与えられていることも前提だよ。

証明(なぜ成り立つ?)

an+1=pan+qa_{n+1}=pa_n+q から、動かない値 α\alpha(特性方程式の解)を両辺から引く。ずれ an−αa_n-\alpha がちょうど公比 pp の等比数列になることを示し、等比の一般項に当てはめる。

  1. 1

    「次の項=前の項」になって動かなくなる値(不動点)を α\alpha とすると、特性方程式が立つ。p≠1p\ne1 なら α\alpha はただ 11 つに決まる。これが基準にする値だよ。

    α=pα+q ⇒ α=q1−p\alpha=p\alpha+q\ \Rightarrow\ \alpha=\dfrac{q}{1-p}
  2. 2

    もとの漸化式から特性方程式を辺ごとに引くと、定数 qq が消えてしまう。残るのは「α\alpha を基準にずらして測った量」が、毎回ちょうど pp 倍になるという関係だよ。

    an+1−α=p(an−α)a_{n+1}-\alpha=p(a_n-\alpha)
  3. 3

    そこで α\alpha からのずれを bnb_n とおくと、bnb_n は公比 pp の等比数列。初項は a1−αa_1-\alpha だから、等比数列の一般項がそのまま当てはまるね。

    bn=an−α=(a1−α) p n−1b_n=a_n-\alpha=(a_1-\alpha)\,p^{\,n-1}
  4. 4

    最後に α\alpha を足してもとに戻せば、一般項が手に入る。前の項からしか分からなかった数列が、nn を入れるだけで一発で求まる式になった、というわけだね。

    an=(a1−α) p n−1+αa_n=(a_1-\alpha)\,p^{\,n-1}+\alpha

逆

差をとる bn=an+1−anb_n=a_{n+1}-a_n が一定なら等差、比 an+1an\dfrac{a_{n+1}}{a_n} が一定なら等比、というように、数列の側から「どの型の漸化式に従うか」を読み取れる。階差 bn=an+1−anb_n=a_{n+1}-a_n が nn の式になっている数列(階差数列)は、an=a1+∑k=1n−1bka_n=a_1+\sum_{k=1}^{n-1}b_k(n≥2n\ge2)で一般項に戻せるよ。

補足・つまずきポイント

つまずきの定番は特性方程式の意味。α=pα+q\alpha=p\alpha+q は「次の項=前の項=α\alpha になって動かなくなる値(不動点)」を求めているんだ。その α\alpha を基準にずらして測れば、ずれ an−αa_n-\alpha がきれいに pp 倍ずつになる。だから等比に化ける。α\alpha を引き忘れて ana_n のまま等比扱いするのが最大のミス。最後に n=1n=1 を一般項に入れて a1a_1 に戻るか必ず検算しよう。なお an+1=pan+(nの式)a_{n+1}=pa_n+(n\text{の式}) など、もっと複雑な型は数列を置きかえる別の工夫がいる(本項は基本の 33 型)。

関連する定理

見て確かめる

言葉で読んだら、動くアニメと自分の手で確かめてみよう。

使いどころ

この定理が、実際の問題でどう効くのかを見てみよう。