MathLabs
Định lýĐã chứng minh

Công thức đóng cho hàm sinh của dãy Fibonacci

Phát biểu

Cho F0=0, F1=1F_0=0,\ F_1=1 và Fn=Fn−1+Fn−2F_n=F_{n-1}+F_{n-2} với n≥2n\ge2. Khi đó hàm sinh thường F(x)=∑n=0∞FnxnF(x)=\sum_{n=0}^{\infty}F_nx^n bằng F(x)=x1−x−x2F(x)=\frac{x}{1-x-x^2}.

Vì sao đúng?

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 xxn^n rồi lấy tổng theo mọi nn — hệ thức truy hồi trở thành phép nhân với một đa thức theo xx.

Phác thảo chứng minh

Nhân hệ thức truy hồi Fn=Fn−1+Fn−2F_n=F_{n-1}+F_{n-2} (đúng với n≥2n\ge2) với xnx^n rồi lấy tổng theo n≥2n\ge2: ∑n≥2Fnxn=∑n≥2Fn−1xn+∑n≥2Fn−2xn\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)−F0−F1x=F(x)−xF(x)-F_0-F_1x=F(x)-x. Tổng đầu tiên ở vế phải là x∑n≥2Fn−1xn−1=x∑m≥1Fmxm=x(F(x)−F0)=xF(x)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à x2∑n≥2Fn−2xn−2=x2∑k≥0Fkxk=x2F(x)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)+x2F(x)F(x)-x=xF(x)+x^2F(x), tức là (1−x−x2)F(x)=x(1-x-x^2)F(x)=x.

Giải phương trình theo F(x)F(x) ta được F(x)(1−x−x2)=xF(x)(1-x-x^2)=x, suy ra F(x)=x1−x−x2F(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.

Chủ đề chứa định lý này

Hàm sinh

Chứng minh từng bước

Chưa có chứng minh từng bước cho định lý này.

Tài liệu tham khảo

  1. Herbert S. Wilf (1994). generatingfunctionology
  2. Philippe Flajolet, Robert Sedgewick (2009). Analytic Combinatorics