Hàm sinh

Một hệ thức truy hồi tuyến tính với hệ số hằng luôn trở thành một phương trình đại số (thực chất là phương trình hữu tỉ) đơn giản một khi ta nhân với $x$$^n$ rồi lấy tổng theo mọi $n$ — hệ thức truy hồi trở thành phép nhân với một đa thức theo $x$.

Nhân hệ thức truy hồi $F_n=F_{n-1}+F_{n-2}$ (đúng với $n\ge2$) với $x^n$ rồi lấy tổng theo $n\ge2$: $\sum_{n\ge2}F_nx^n=\sum_{n\ge2}F_{n-1}x^n+\sum_{n\ge2}F_{n-2}x^n$.

Vế trái bằng $F(x)-F_0-F_1x=F(x)-x$. Tổng đầu tiên ở vế phải là $x\sum_{n\ge2}F_{n-1}x^{n-1}=x\sum_{m\ge1}F_mx^m=x(F(x)-F_0)=xF(x)$. Tổng thứ hai là $x^2\sum_{n\ge2}F_{n-2}x^{n-2}=x^2\sum_{k\ge0}F_kx^k=x^2F(x)$.

Vậy $F(x)-x=xF(x)+x^2F(x)$, tức là $(1-x-x^2)F(x)=x$.

Giải phương trình theo $F(x)$ ta được $F(x)(1-x-x^2)=x$, suy ra $F(x)=\frac{x}{1-x-x^2}$, một hàm hữu tỉ duy nhất gói trọn toàn bộ dãy Fibonacci vô hạn.

Mọi hàm sinh hữu tỉ có mẫu số là tích các nhân tử tuyến tính khác nhau đều tách được thành tổng các chuỗi cấp số nhân đơn giản, và mỗi chuỗi cấp số nhân cho ngay một công thức tường minh cho hệ số.

Phân tích mẫu số: vì các nghiệm của $1-x-x^2=0$ là $x=1/\varphi$ và $x=1/\psi$, ta có $1-x-x^2=(1-\varphi x)(1-\psi x)$.

Viết $\frac{x}{1-x-x^2}=\frac{A}{1-\varphi x}+\frac{B}{1-\psi x}$ với hằng số $A,B$. Quy đồng mẫu số và so khớp số hạng tự do cùng hệ số của $x$ ta được một hệ phương trình tuyến tính có nghiệm $A=\frac{1}{\sqrt5}$, $B=-\frac{1}{\sqrt5}$, do đó $\frac{x}{1-x-x^2}=\frac{1}{\sqrt{5}}\left(\frac{1}{1-\varphi x}-\frac{1}{1-\psi x}\right)$.

Khai triển mỗi số hạng thành chuỗi cấp số nhân: $\frac{1}{1-\varphi x}=\sum_{n\ge0}\varphi^nx^n$ và $\frac{1}{1-\psi x}=\sum_{n\ge0}\psi^nx^n$.

Lấy hệ số của $x^n$ ở hai vế ta được $F_n=\frac{1}{\sqrt{5}}\left(\varphi^n-\psi^n\right)$, gọi là công thức Binet.