Note linh tinh về dãy Fibonacci

Định nghĩa

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

• \(F_0 = 0, F_1 = 1\)

• \(F_n = F_{n-1}+F_{n-2}, \quad n>1\)

Công thức tổng quát tính \(F_n\) - công thức Binet

$$\boxed{ F_n = \frac 1 {\sqrt 5} \left( \frac {1 + \sqrt 5} 2 \right)^n - \frac 1 {\sqrt 5} \left( \frac {1 - \sqrt 5} 2 \right)^n}$$

Chứng minh:

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

$$\left( \begin{matrix} F_{k+2} \\ F_{k+1} \end{matrix} \right) = \left( \begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix} \right) \left( \begin{matrix} F_{k+1} \\ F_k \end{matrix} \right)$$

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ó \(\overrightarrow F_{k+1} = \mathbf A \overrightarrow F_k\) , suy ra \(\overrightarrow F_{n} = \mathbf A^n \overrightarrow F_0\).

Ma trận \(\mathbf A\) có các giá trị riêng 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 \(\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ó

$$\begin{align*} \overrightarrow F_n &= \frac 1 {\sqrt 5} \mathbf A ^n \mu - \frac 1 {\sqrt 5} \mathbf A ^n \nu \\ &= \frac 1 {\sqrt 5} \varphi^n \mu - \frac 1 {\sqrt 5} \psi^n \nu = \frac 1 {\sqrt 5} \varphi^n \mu - \frac 1 {\sqrt 5} (-\varphi)^{-n} \nu \\ &= \frac 1 {\sqrt 5}\left( \frac {1 + \sqrt 5} 2 \right)^n \left( \begin{matrix} \varphi \\ 1\end{matrix} \right) - \frac 1 {\sqrt 5}\left( \frac {1 - \sqrt 5} 2 \right)^n \left( \begin{matrix} -\varphi^{-1} \\ 1\end{matrix} \right) \\ &= \left( \begin{matrix} F_{n+1} \\ F_n\end{matrix} \right) \end{align*} \\$$

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

$$F_n = \frac 1 {\sqrt 5} \left( \frac {1 + \sqrt 5} 2 \right)^n - \frac 1 {\sqrt 5} \left( \frac {1 - \sqrt 5} 2 \right)^n$$

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: \(F_1^2+F_2^2+\dots+F_k^2 + F_{k+1}^2 = F_{k+1}F_{k+2}\).

Ta có \(F_1^2+F_2^2+\dots+F_k^2 + F_{k+1}^2 = F_kF_{k+1} + F_{k+1}^2 = F_{k+1}(F_k + F_{k+1}) = F_{k+1}F_{k+2} \quad \checkmark\)

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

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

Với \(n=1, F_1 = F_2 = 1\) do đó \(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\)

$$\begin{align*} F_{m-1}F_{k+1} + F_mF_{k+2} &= F_{m-1}(F_{n-1}+F_n) + F_m(F_n + F_{n+1})\\ &= F_{m-1}F_{n-1} + F_{m-1}F_n + F_mF_n+F_mF_{n+1} \\ &=(F_{m-1}F_{n-1}+F_mF_n) + (F_{m-1}F_n + F_mF_{n+1}) \\ &= F_{m+n-1} +F_{m+n} \\ &= F_{m+n+1} & \checkmark \end{align*}$$

Vì công thức không phụ thuộc \(m\) 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)}\).

Định lý 2:

$$\gcd(F_n,F_m) = F_{\gcd(m,n)}$$

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ó:

$$\begin{align*} \gcd(F_m, F_n) &= \gcd(F_m, F_{mk+1}F_r + F_{mk}F_{r-1}) \\ &=\gcd(F_m,F_{mk+1}F_r) \\ &=\gcd(F_m,F_r) \quad (\text {since }\gcd(F_m,F_{mk+1})=1) \end{align*}$$

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ó \(\gcd(F_n,F_m) = \gcd(F_m,F_{mk+r}) = \gcd(F_m,F_r)=\gcd(F_r, F_{rk+q})=\gcd(F_r, F_q)= \dots\) 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.