フィボナッチ数列の一般項

フィボナッチ数列とは
0,1,1,2,3,5,8,13,21\cdots
という数列。
この数列の一般項を求めたい。それには以下の母関数を用いる。
F(x)=0x^{0}+1x^{1}+1x^{2}+2x^{3}+3x^{4}+5x^{5}+8x^{6}+13x^{7}+21x^{8}+\cdots
ところで
xF(x)=0x^{1}+1x^{2}+1x^{3}+2x^{4}+3x^{5}+\cdots
であり、
x^{2}F(x)=0x^{2}+1x^{3}+1x^{4}+2x^{5}+3x^{6}+\cdots
である。こいつらを用いて、F(x)の項を消してやる。
F(x)-(xF(x)+x^{2}F(x))=0x^{0}+1x^{1}-0x^{1}
すなわち
(1-x-x^{2})F(x)=x
よって
F(x)=\frac{x}{1-x-x^{2}}

こいつが以下のようになってくれると仮定し、A,a,B,bを求める。
F(x)=\frac{x}{1-x-x^{2}}=\frac{A}{1-ax}+\frac{B}{1-bx}
A=\frac{1}{a-b}
B=-\frac{1}{a-b}
これを用いてF(x)を書くと、
F(x)=\frac{a-b}{a-b}x+\frac{a^{2}-b^{2}}{a-b}x^{2}+\frac{a^{3}-b^{3}}{a-b}x^{3}+\cdots
よって、一般項は
\frac{a^{n}-b^{n}}{a-b}
となる。
a,b=\frac{1\pm\sqrt{5}}{2}
より、一般項は
\frac{1}{\sqrt{5}}\{\bigl(\frac{1+\sqrt{5}}{2}\bigr)^{n}-\bigl(\frac{1-\sqrt{5}}{2}\bigr)^{n}\}
と書ける。
尚、これが一般項であることを証明するには数学的帰納法を使えばいい。