Fibonacci 数列の母関数 - Red cat の数学よもやま話

あまりに結果が綺麗だったので、「数学ガール」から引用します。

Fibonacci 数列は、次の漸化式で定義されます。
$a_0=0,a_1=1,a_n=a_{n-1}+a_{n-2}(n\geq 2)$

一般に、数列 $\{a_0,a_1,a_2,\dots\}$ に対して、べき級数
$a_0+a_1 x+a_2 x^2+\dots=\sum_{n=0}^\infty a_n x^n$
を、数列 $\{a_0,a_1,a_2,\dots\}$ の母関数と言います。今、Fibonacci 数列の母関数を
$F(x)=\sum_{n=0}^\infty a_n x^n$
とおきましょう。すると
$xF(x)=\sum_{n=0}^\infty a_n x^{n+1}=\sum_{n=1}^\infty a_{n-1} x^n$
$x^2 F(x)=\sum_{n=0}^\infty a_n x^{n+2}=\sum_{n=2}^\infty a_{n-2} x^n$
から
$F(x)-xF(x)-x^2 F(x)=a_0+(a_1-a_0)x+\sum_{n=2}^\infty(a_n-a_{n-1}-a_{n-2})x^n$
となり、 $x^2$ 以降の項は漸化式から分かるように係数が 0 になります。したがって
$(1-x-x^2)F(x)=x$
となり
$F(x)=\frac{x}{1-x-x^2}$
と求まってしまいました !