フィボナッチ数列の一般項を差分を使って導く
はじめに
フィボナッチ数列の一般項については、数学ⅡBの知識でとけますが、今回は「差分」という考え方から導いてみます。
差分とは
差分は、「離散的な微分」と言えます。
微分:
$f^{\prime}(x)=\lim_{h \to 0}\frac{f(x+h)-f(x)}{h}$
差分:
$\Delta f(x)=\frac{f(x+1)-f(x)}{1}={f(x+1)-f(x)}$
微分における微小量を$1$に固定したものとも言えます。ここで$x\in\mathbb{Z}$とします。
例
ここで、差分における$e^{x}$、つまり差分しても変わらない関数を探してみます。
$\Delta f(x)=f(x),f(0)=1$の時、$f(x)=2^{x}$
$\Delta f(x)=f(x)$
$f(x+1)-f(x)=f(x)$
$f(x+1)=2f(x)$
$f(0)=1$のとき、これは初項$1$、公比$2$の等比数列なので、
$f(x)=2^x$
ここで重要な性質を紹介します。
$\Delta f(x)=Af(x),f(0)=1$の時、$f(x)=(A+1)^{x}$
$\Delta f(x)=Af(x)$
$f(x+1)-f(x)=Af(x)$
$f(x+1)=(A+1)f(x)$
$f(0)=1$のとき、これは初項$1$、公比$A+1$の等比数列なので、
$f(x)=(A+1)^x$
つまり、累関数を差分しても「あまり性質は変わらない」ということです。後で使います。
$n$階差分
次に、関数を$n$階差分してみます。以下、$n$階差分された関数を$\Delta^{n}f(x)$と表します。
$\Delta^{n}f(x)=\sum_{i=0}^{n}(-1)^i{}_n \mathrm{ C }_if(x+n-i)$
$n=1$の時、
$\Delta^{1}f(x)=f(x+1)-f(x)$
より成り立つ。
$n=k$の時成り立つと仮定すると、$n=k+1$の時、
$\Delta^{n+1}f(x)=\Delta\Delta^{n}f(x)$
$=\Delta[\sum_{i=0}^{n}(-1)^i{}_n \mathrm{ C }_if(x+n-i)]$
$=\Delta[ {}_n \mathrm{ C }_0f(x+n)-{}_n \mathrm{ C }_1f(x+n-1)+{}_n \mathrm{ C }_2f(x+n-2)-...+(-1)^{n-1}{}_n \mathrm{ C }_{n-1}f(x+1)+(-1)^{n}{}_n \mathrm{ C }_nf(x)]$
$={}_n \mathrm{ C }_0f(x+n+1)-{}_n \mathrm{ C }_0f(x+n)-{}_n \mathrm{ C }_1f(x+n)+{}_n \mathrm{ C }_1f(x+n-1)+{}_n \mathrm{ C }_2f(x+n-1)-{}_n \mathrm{ C }_2f(x+n-2)-...+(-1)^{n-1}{}_n \mathrm{ C }_{n-1}f(x+2)-(-1)^{n-1}{}_n \mathrm{ C }_{n-1}f(x+1)+(-1)^{n}{}_n \mathrm{ C }_nf(x+1)-(-1)^{n}{}_n \mathrm{ C }_nf(x)$
ここで、$l\in\mathbb{Z}$とすると、
${}_n \mathrm{ C }_l+{}_n \mathrm{ C }_{l+1}$
$=\frac{n(n-1)(n-2)...(n-l+1)}{l!}+\frac{n(n-1)(n-2)...(n-l)}{(l+1)!}$
$=\frac{(l+1)n(n-1)(n-2)...(n-l+1)+(n+1)n(n-1)...(n-l)}{(l+1)!}$
$=\frac{[n(n-1)(n-2)...(n-l+1)](l+1+n-l)}{(l+1)!}$
$=\frac{(n+1)n(n-1)(n-2)...(n-l+1)}{(l+1)!}$
$={}_{n+1} \mathrm{ C }_{l+1}$
だから、
$\Delta^{n+1}f(x)={}_n \mathrm{ C }_0f(x+n+1)-{}_{n+1} \mathrm{ C }_1f(x+n)+{}_{n+1} \mathrm{ C }_2f(x+n-1)+...+(-1)^n{}_{n+1} \mathrm{ C }_nf(x+1)-(-1)^n{}_{n} \mathrm{ C }_nf(x)$
$={}_{n+1} \mathrm{ C }_0f(x+n+1)-{}_{n+1} \mathrm{ C }_1f(x+n)+{}_{n+1} \mathrm{ C }_2f(x+n-1)+...+(-1)^n{}_{n+1} \mathrm{ C }_nf(x+1)+(-1)^{n+1}{}_{n+1} \mathrm{ C }_{n+1}f(x)$
$=\sum_{i=0}^{n+1}(-1)^i{}_{n+1} \mathrm{ C }_if(x+(n+1)-i)$
成り立つ
この公式は、二項定理と非常によく似ていて、同じ構造を持っているとも言えます。
$\Delta^{2}f(x)=f(x+2)-2f(x+1)+f(x)$
$\Delta^{3}f(x)=f(x+3)-3f(x+2)+3f(x+1)-f(x)$
$\Delta^{4}f(x)=f(x+4)-4f(x+3)+6f(x+2)-4f(x+1)+f(x)$
といった具合です。$(x-1)^n$の展開した形とほぼ同じですね。
差分方程式
先ほどの式を使って差分方程式について考えます。漸化式のことを差分方程式と呼ぶ方が一般的なようですが、ここでは、下のような差分した関数の和であらわされた方程式のことを「差分方程式」と呼び、「漸化式」とは区別します。
$\Delta^{3}f(x)+\Delta f(x)+f(x)=0$
を展開すると、
$f(x+3)-3f(x+2)+f(x+1)-f(x)=0$
という漸化式になります。
逆に漸化式から差分方程式に直してみます。
$f(x+2)-3f(x+1)-f(x)=0$
という例で考えます。「足して余分なものを引く」精神で行きます。
$f(x+2)-3f(x+1)-f(x)=0$
$\Longleftrightarrow [f(x+2)-2f(x+1)+f(x)]-[f(x+1)-f(x)]-3f(x)=0$
$\Longleftrightarrow \Delta^{2}f(x)+\Delta f(x)-3f(x)=0$
この直した形を応用していきます。
漸化式をとく
これらの技術を応用して漸化式を解いていきます。フィボナッチ数列を例にしましょう。
$f(x+2)-f(x+1)-f(x)=0$
これを差分方程式に直すと、
$[f(x+2)-2f(x+1)+f(x)]+[f(x+1)-f(x)]-f(x)=0$
$\Longleftrightarrow\Delta ^{2}f(x)+\Delta f(x)-f(x)=0$
この時の$f(x)$を求めましょう。
この方程式は、「$f(x)$を2階差分したものと、１階差分したものの和から$f(x)$を引いたもの」といえます。つまり、$f(x)$は差分しても性質があまり変わらないものだと考えられます。実際、これとよく似た常微分方程式の解は$Ae^{ax}$の形の式の和になるそうです。（エアプ）これは微分してもあまり性質が変わりませんね。
ここで、差分しても性質が変わらないものとして冪関数が考えられます。
$f(x)=a^x$について、
$\Delta f(x)=a^{x+1}-a^{x}=(a-1)a^x$
$\Delta^{2} f(x)=(a-1)(a^{x+1}-a^x)=(a-1)^2a^x$
帰納的に
$\Delta ^n f(x)=(a-1)^na^x$
と分かります。
差分しても性質があまり変わっていませんね。これを代入してみましょう。
$\Delta^{2}f(x)+\Delta f(x)-f(x)=0$
$\Longleftrightarrow (a-1)^2a^x+(a-1)a^x-a^x=0$
$\Longleftrightarrow (a^2-a-1)a^x=0$
$a^x\neq0$より、$a^2-a-1=0$のときこの方程式は成り立つので、$a=\frac{1\pm\sqrt{5}}{2}$、つまり、
$f(x)=(\frac{1\pm\sqrt{5}}{2})^x$
実際に代入すると、成り立っていることが分かります。しかし、これでは不十分です。いま求めたいのは、フィボナッチ数列の一般項ですから、$f(0)=0,f(1)=1$という２つの初期値を考慮しなければなりません。パラメータを追加しましょう。$f(x)=Aa^{x}$という形でも１つしか代入できないので、$f(x)=Aa^x+Bb^x (a\neq b)$で考えてみます。
$a>b$とすると、
$f(x)=A(\frac{1+\sqrt{5}}{2})^x+B(\frac{1-\sqrt{5}}{2})^x$となります。これに$f(0)=0,f(1)=1$を代入すると、$A=\frac{1}{\sqrt{5}},B=-\frac{1}{\sqrt{5}}$とわかります。よって、
$f(x)=\frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^x-(\frac{1-\sqrt{5}}{2})^x]$
実際に代入すると、成り立っていることが分かります。
一般化について（放棄）
ここで$a,b$について考えてみましょう。$a$と$b$
は、$x^2-x-1=0$を満たしました。これは、求める漸化式である$f(x+2)-f(x+1)-f(x)=0$に似ています。これには理由があります。
$\Delta ^{n}f(x)$の展開は$(x-1)^n$の展開と同じ構造ということを言いました。そして$\Delta^{n}f(x)$の係数は$(a-1)^n$です。つまり、二項定理と同じ構造のものでまとめて、それを二項定理で展開しているので、同じになるわけです。
先の例を一般化して多項間漸化式の一般項を求めることもできますが、力尽きたので止めます。解の一意性？知らんな
↓一応紹介
$$ a_{n+k}=p_{k-1}a_{n+k-1}+p_{k-2}a_{n+k-2}+...+p_{1}a_{n+1}+p_{0}a_{n} $$
という漸化式について、$k$次方程式
$ \phi(\lambda)=\lambda^{k}-p_{k-1}\lambda^{k-1}-p_{k-2}\lambda^{k-2}-..-+p_{1}\lambda+p_{0}=0 $
を特性方程式という。特性方程式の解$\lambda_{1},...\lambda_{k}$がすべて異なるとき、数列$a_{n}$の一般項は
$a_{n}=C_{1}\lambda_{1}^{n}+C_{2}\lambda_{2}^{n}+...+C_{k}\lambda_{k}^{n}$
と表せる（$C_{1},...C_{k}$は初期条件によって決まる定数）。
こんな証明方法 があります。
おわりに
はじめてmathlogやってみたけどなれなくてクソ時間かかりました。
差分学という分野はすでに確立されていますが、この記事の中の差分理論は我流なので、表記法はオリジナルなものになってます。ごめんなさい。適当に書いて推敲もろくにしてないので間違ってたら教えてほしいです。多分めっちゃ間違えてます。
学校の数学の先生に見せたら面白がってくれたのでうれしかったです。