Vài note linh tinh về dãy Fibonacci

Định nghĩa

Dãy Fibonacci được định nghĩa như sau:

Công thức tổng quát tính $F_n$ - Công thức Binet

Chứng minh:

Dựa vào định nghĩa, ta có thể đưa về dạng ma trận như sau:

Gọi ma trận $\mathbf A = \left( \begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix} \right)$, vector $\overrightarrow F_{k+1} = \left( \begin{matrix} F_{k+2} \\ F_{k+1} \end{matrix} \right), \overrightarrow F_{k} = \left( \begin{matrix} F_{k+1} \\ F_{k} \end{matrix} \right)$ ta có:

Suy ra:

Ma trận $\mathbf A$ có các trị riêng (eigen value) là: $\displaystyle \varphi = \frac 1 2 (1 + \sqrt 5)$ và $\displaystyle \psi=-\varphi^{-1} = \frac 1 2 (1 - \sqrt 5)$ tương ứng với các vector riêng (eigen vector): $\mu = \left( \begin{matrix} \varphi \\ 1 \end{matrix} \right)$ và $\nu = \left( \begin{matrix} \psi \\ 1 \end{matrix} \right)$.

Với giá trị khởi đầu là $\displaystyle \overrightarrow F_0 = \left( \begin{matrix} 1 \\ 0 \end{matrix} \right) = \frac 1 {\sqrt 5} \mu - \frac 1 {\sqrt 5}\nu$. Từ đó ta có:

Nếu rút trích công thức ra ta sẽ có:

Công thức 1: $F_1^2+F_2^2+\dots+F_n^2 = F_nF_{n+1}$

Chứng minh: Dùng pp quy nạp.

Đầu tiên, công thức đúng với $n = 1: F_1 ^2 = 1^2 = F_1F_2 = 1. 1$

Giả sử công thức đúng tới $k$, nghĩa là: $F_1^2+F_2^2+\dots+F_k^2 = F_kF_{k+1}$, ta chứng minh công thức đúng tới $k+1$. Nghĩa là cần chứng minh:

Ta có:

Công thức 2: $F_{m-1}F_n + F_mF_{n+1} = F_{m+n}$

Chứng minh: Giữ cố định, ta chứng minh công thức đúng với mọi bằng phương pháp quy nạp.

Với $n=1, F_1 = F_2 = 1$ ta có $F_{m-1}F_n + F_mF_{n+1} = F_{m-1} + F_m = F_{m+1} \quad \checkmark$

Giả sử công thức đúng với $k$, ta chứng minh công thức đúng với $k+1$

Vì công thức không phụ thuộc nên công thức đúng với mọi $m$ và $n$

Định lý 1:

Nếu $n$ chia hết cho $m$ thì $F_n$ cũng chia hết cho $F_m$.

Chứng minh: Vì $n$ chia hết cho $m$ nên $n=mk$. Ta chứng minh quy nạp theo $k$ và áp dụng Công Thức 2 ở trên:

• $k=1$ đúng

• Giả sử đúng tới $k$ ta có $F_{mk}$ chia hết cho $F_m$

• Kiểm tra trường hợp $F_{m(k+1)}$, ta có: $F_{m(k+1)} = F_{mk+m} = F_{mk}F_{m-1} + F_{mk+1}F_m$

Rõ ràng $F_{mk}F_{m-1}$ chia hết cho $F_m$ và $F_{mk+1}F_m$ cũng chia hết cho $F_m$ nên ta có $F_{m(k+1)}$ cũng chia hết cho $F_m$.

Định lý 2:

Chứng minh:

Nhắc lại định lý: Nếu $\gcd(m,n)=1$ thì $\gcd(m,nk) =\gcd(m,k)$(bạn có thể tự chứng minh định lý này)

Vì $m,n$ là độc lập tương đương nên ta giả sử $n=m+r, 0 \le r \lt m$, ta có:

Nếu ta liên tục lặp đi lặp lại công thức trên nhiều lần như thuật toán Euclide tìm ước số chung lớn nhất của hai số sẽ có:

Dãy này liên tục giảm tương ứng cho đến giá trị $\gcd(m,n)$ suy ra điều phải chứng minh.