**Các cách tính số fibonacci và ứng dụng của nó**

1. Sử dụng công thức đệ quy: f(n) = f(n-1) + f(n-2) với f(0) = 0, f(1) = 1.
Độ phức tạp: O($2^n$) nếu dùng đệ quy trực tiếp, O(n) nếu triển khai quy hoạch động.
Mức độ ứng dụng rất phổ biến, sử dụng cho nhập môn lập trình phần vòng lặp, đệ quy, giới thiệu về quy hoạch động

2. Sử dụng công thức Binet:
$$f(n) = \frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^n-\frac{1}{\sqrt{5}}(\frac{1-\sqrt{5}}{2})^n$$
Độ phức tạp: C*O(1)
Rất hiếm khi sử dụng vì có sai số do dấu chấm động và khó nhớ. Hơn nữa về mặt tính toán hằng số C có thể rất lớn do các phép tính căn thức yêu cầu rất nhiều phép toán bit nên chưa chắc đã nhanh hơn công thức (1) với n rất lớn. Do đó công thức Binet trên thực tế chỉ được dùng khi cài đặt chung với một thư viện xử lý dấu chấm động để tìm những số Fibonacci với n rất lớn.
3. Sử dụng công thức Vorobev:
$$
f(n+k)=f(n-1) \times f(k) + f(n) \times f(k+1)
$$
Các hẹ quả:
$f(2n+1)=(f(n+1))^2 + (f(n))^2$
$f(2n+2)=2 \times f(n) \times f(n+1) + (f(n+1))^2$
$f(2n) = 2 \times f(n+1) \times f(n) - (f(n))^2$
Độ phức tạp: $O(\log{n})$
Các hệ quả của công thức Vorobev được ứng dụng nhiều hơn, nhằm cài đặt thuật toán có độ phức tạp được giảm thiểu.

4.Sử dụng công thức lũy thừa ma trận: Cho A với
$$
A=\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}
$$
thì
$$
A^n=\begin{pmatrix} f(n+1) & f(n) \\ f(n) & f(n+1) \end{pmatrix}
$$
Độ phức tạp O(n)
Vì những em học sinh không chuyên không được học về ma trận, nên công thức này chỉ để giới thiệu với các em về phép nhân ma trận, và thường thì cũng yêu cầu giảm thiểu độ phức tạp của thuật toán xuống mức$O(\log{n})$ như một bài tập nâng cao.
Đồng thời, công thức nhân ma trận này cũng là một cách để suy ra các hệ quả của công thức Vorobev

Các bài tập nâng cao về số Fibonacci:
i. Đưa ra thuật toán có độ phức tạo O(1) để tìm chữ số tận cùng của số Fibonacci thứ n.
ii. Tìm ước thật sự lớn nhất là số fibonacci của số fibonacci thứ n.