Dãy số - Phần 9


Đây là bài cuối cùng trong chuỗi bài về dãy số. Nếu các bạn chưa đọc các bài trước thì đây là bài đầu tiên "Dãy số - Phần 1".

Hôm nay chúng ta sẽ làm thêm một ít bài tập về dãy số. Trong các bài tập này chúng ta sẽ chứng minh một vài hằng đẳng thức thú vị. Chẳng hạn, với dãy số Pell $$P_0=0, ~~P_1 = 1, ~~P_n = 2 P_{n-1} + P_{n-2},$$ và dãy số Pell-đồng hành $$H_0=1, ~~H_1 = 1, ~~H_n = 2 H_{n-1} + H_{n-2},$$ chúng ta có hằng đẳng thức $$H_n^2 - 2 P_n^2 = (-1)^n.$$

Với dãy số Fibonacci quen thuộc $$F_0 = 0, ~~F_1 = 1, ~~F_n = F_{n-1} + F_{n-2},$$ chúng ta sẽ chứng minh rằng $$\frac{F_{2013(n+1)} - F_{2013 (n−1)}}{F_{2013 n}} = \frac{F_{2013(n^{2013}+1)} - F_{2013 (n^{2013}−1)}}{F_{2013 n^{2013}}}.$$


Trong chuổi bài về dãy số, chúng ta đã học cách tìm công thức tổng quát cho dãy số $\{ f_n \}$ thõa mãn phương trình sai phân tuyến tính $$a_k f_n + a_{k−1} f_{n−1} + a_{k−2} f_{n−2}+ \dots + a_0 f_{n−k}=0.$$

Chúng ta thấy rằng khi giải một phương trình sai phân tuyến tính thì phương trình đặc trưng rất quan trọng. Phương trình đặc trưng là phương trình sau đây $$a_k ~x^k + a_{k−1} ~x^{k−1} + \dots + a_1 ~x + a_0=0.$$ Dạng của dãy số sẽ phụ thuộc vào việc phương trình đặc trưng có bao nhiêu nghiệm, nghiệm đơn hay nghiệm kép, nghiệm thực hay nghiệm phức.

Giả sử chúng ta phân loại nghiệm của phương trình đặc trưng ra làm hai loại:
  • Loại nghiệm thực: giả sử phương trình đặc trưng có $t$ nghiệm thực $x_1$, $x_2$, ..., $x_t$, trong đó $x_1$ là nghiệm bội bậc $u_1$; $x_2$ là nghiệm bội bậc $u_2$; v.v...
  • Loại nghiệm phức: giả sử phương trình đặc trưng có $s$ bộ nghiệm phức $z_1$, $\overline{z_1}$, $z_2$, $\overline{z_2}$, ..., $z_s$, $\overline{z_s}$, trong đó $z_1$, $\overline{z_1}$ là bộ nghiệm phức bội bậc $v_1$; $z_2$, $\overline{z_2}$ là bộ nghiệm phức bội bậc $v_2$; v.v... Chúng ta viết các nghiệm phức này về dạng lượng giác như sau $$z_1, \overline{z_1} = r_1 (\cos{\phi_1} \pm i ~ \sin{\phi_1}); ~\dots; ~z_s, \overline{z_s} = r_s (\cos{\phi_s} \pm i ~ \sin{\phi_s}).$$
Vậy thì công thức sau đây là công thức tóm lược tất cả các trường hợp cho dãy số thực $\{ f_n \}$ $$f_n = p_1(n) ~x_1^{n} + \dots +  p_t(n) ~x_t^{n} $$ $$+  (g_1(n) ~\cos{n \phi_1} + h_1(n) ~ \sin{n \phi_1}) ~r_1^n + \dots +  (g_s(n) ~ \cos{n \phi_s} + h_s(n) ~ \sin{n \phi_s}) ~r_s^n.$$ Ở đây
  • $p_1(n)$, ..., $p_t(n)$ là các đa thức có hệ số thực và có bậc lần lượt bé thua $u_1$, ..., $u_t$; còn
  • $g_1(n)$, $h_1(n)$, ..., $g_s(n)$, $h_s(n)$ là các đa thức có hệ số thực và có bậc lần lượt bé thua $v_1$, ..., $v_s$.

Công thức ở trên là công thức tổng quát nhất, tuy nhiên, trong toán phổ thông chúng ta thường hay gặp hai trường hợp đơn giản sau đây.
Trường hợp 1: phương trình đặc trưng chỉ có nghiệm đơn $x_1$, $x_2$, ..., $x_k$.
Trường hợp này công thức cho dãy số là $$f_n = \alpha_1 ~x_1^{n} + \alpha_2 ~x_2^{n} + \dots +  \alpha_k ~x_k^{n},$$ trong đó $\alpha_1$, $\alpha_2$, ..., $\alpha_k$ là các hằng số thực.

Trường hợp 2: phương trình đặc trưng có đúng một bộ nghiệm phức $z_1$, $\overline{z_1}$, $$z_1, \overline{z_1} = r (\cos{\phi} \pm i ~ \sin{\phi}).$$
Trường hợp này công thức cho dãy số là $$f_n = (\alpha ~\cos{n \phi} +  \beta ~ \sin{n \phi}) ~r^n,$$ trong đó $\alpha$, $\beta$ là các hằng số thực.


Bài tập về dãy số nhìn chung có hai dạng. Dạng thứ nhất, chúng ta có một công thức truy hồi và chúng ta cần tìm công thức tổng quát cho dãy số. Dạng thứ hai thì ngược lại, chúng ta có công thức tổng quát và chúng ta cần tìm lại công thức truy hồi cho dãy số.

Bây giờ chúng ta giải một vài bài tập.

Bài toán 1: Dãy số Pell là dãy số sau đây $$P_0=0, ~~P_1 = 1, ~~P_n = 2 P_{n-1} + P_{n-2}.$$
Còn dãy số Pell-đồng hành là dãy số sau đây $$H_0=1, ~~H_1 = 1, ~~H_n = 2 H_{n-1} + H_{n-2}.$$
Chứng minh rằng $$H_n^2 - 2 P_n^2 = (-1)^n.$$

Lời giải: Phương trình đặc trưng cho cả hai dãy số $P_n$ và $H_n$ là $$x^2 - 2 x - 1 = 0.$$
Giải phương trình này chúng ta có hai nghiệm $$1 \pm \sqrt{2}.$$
Do đó $$P_n = \alpha ~ (1 + \sqrt{2})^n + \beta ~ (1 - \sqrt{2})^n$$
và $$H_n = \gamma ~ (1 + \sqrt{2})^n + \delta ~ (1 - \sqrt{2})^n.$$
Với $n=0,1$, chúng ta có $$P_0 = \alpha + \beta = 0, ~~P_1 = \alpha ~(1 + \sqrt{2}) + \beta ~(1 - \sqrt{2}) = 1,$$ $$H_0 = \gamma + \delta = 1, ~~H_1 = \gamma ~(1 + \sqrt{2}) + \delta ~(1 - \sqrt{2}) = 1.$$
Giải hệ phương trình này chúng ta có $\alpha = \frac{1}{2 \sqrt{2}}$, $\beta = -\frac{1}{2 \sqrt{2}}$, $\gamma = \frac{1}{2}$, $\delta = \frac{1}{2}$. Vậy $$P_n = \frac{1}{2 \sqrt{2}} [(1 + \sqrt{2})^n - (1 - \sqrt{2})^n],$$ $$H_n = \frac{1}{2} [(1+\sqrt{2})^n + (1 - \sqrt{2})^n].$$
Do đó $$P_n^2 = \frac{1}{8} [(1 + \sqrt{2})^n - (1 - \sqrt{2})^n]^2 = \frac{1}{8} [(1+\sqrt{2})^{2n} + (1 - \sqrt{2})^{2n} - 2 (-1)^n],$$ $$H_n^2 = \frac{1}{4} [(1+\sqrt{2})^n + (1-\sqrt{2})^n]^2 = \frac{1}{4} [(1 + \sqrt{2})^{2n} + (1 - \sqrt{2})^{2n} + 2 (-1)^n].$$
Từ đó chúng ta rút ra được đẳng thức $$H_n^2 - 2 P_n^2 = (-1)^n.$$


Dưới đây là một vài số hạng đầu tiên của dãy số Pelldãy số Pell-đồng hành $$P_0=0, ~~P_1 = 1, ~~P_2 = 2, ~~P_3 = 5, ~~P_4 = 12, ~~P_5 = 29, \dots $$ $$H_0=1, ~~H_1 = 1, ~~H_2 = 3, ~~H_3 = 7, ~~H_4 = 17, ~~H_5 = 41, \dots$$
Chúng ta có hằng đẳng thức
  • $H_2^2 - 2 P_2^2 = 3^2 - 2 \times 2^2 = 9 - 8 = 1,$
  • $H_3^2 - 2 P_3^2 = 7^2 - 2 \times 5^2 = 49 - 50 = -1,$
  • $H_4^2 - 2 P_4^2 = 17^2 - 2 \times 12^2 = 289 - 288 = 1,$
  • $H_5^2 - 2 P_5^2 = 41^2 - 2 \times 29^2 = 1681 - 1682 = -1,$ ...
Các bạn thử tìm cách mở rộng bài toán trên nhé.



Bài toán 2:  Cho dãy số $$f_0=2, ~f_1 = 2013, ~f_n = 2013 f_{n-1} + f_{n-2}.$$ Tìm tất cả các số $n$ sao cho $$f_n f_{n+2} + 2013^2 + 4$$ là số chính phương.

Lời giải: Từ phương trình sai phân $$f_n - 2013 f_{n-1} - f_{n-2} = 0$$ chúng ta có phương trình đặc trưng $$x^2 - 2013 x - 1 = 0.$$
Phương trình này có hai nghiệm $x_1, x_2$ thoã mãn công thức Vieta $$x_1 + x_2 = 2013,$$ $$x_1 x_2 = -1.$$
Chúng ta có $$f_n = \alpha ~ x_1^n + \beta ~ x_2^n.$$
Với $n=0,1$, chúng ta có $$f_0 = \alpha + \beta = 2,$$ $$f_1 = \alpha ~x_1 + \beta ~x_2 = 2013.$$
Giải hệ phương trình này chúng ta rút ra được $\alpha = \beta = 1$, vậy $$f_n = x_1^n + x_2^n.$$
Từ đó chúng ta có  $$f_n f_{n+2} = (x_1^n + x_2^n)(x_1^{n+2} + x_2^{n+2}) = x_1^{2n+2} + x_2^{2n+2} + x_1^n x_2^n (x_1^2 + x_2^2)$$ $$= (x_1^{n+1} + x_2^{n+1})^2 - 2 x_1^{n+1} x_2^{n+1} + x_1^n x_2^n [(x_1 + x_2)^2 - 2 x_1 x_2]$$ $$= f_{n+1}^2 - 2 (-1)^{n+1} + (-1)^n (2013^2 + 2) = f_{n+1}^2 + (-1)^n (2013^2 + 4).$$
Chúng ta có hằng đẳng thức $$f_n f_{n+2} = f_{n+1}^2 + (-1)^n (2013^2 + 4).$$

Có hai trường hợp.

Trường hợp $n$ là số chẵn, thì $$f_n f_{n+2} = f_{n+1}^2 + (2013^2 + 4).$$
Do đó $$f_n f_{n+2} + 2013^2 + 4 = f_{n+1}^2 + 2(2013^2 + 4).$$
Chúng ta sẽ chứng minh rằng trường hợp này, số $f_n f_{n+2} + 2013^2 + 4$ không thể là số chính phương.
Thực vậy, nếu $$f_n f_{n+2} + 2013^2 + 4 = f_{n+1}^2 + 2(2013^2 + 4) = N^2,$$ thì $$N^2 - f_{n+1}^2 = 2(2013^2 + 4).$$
Như vậy $N^2 - f_{n+1}^2$ là một số chẵn nhưng không chia hết cho 4. Điều này là vô lý vì (chẳng hạn bằng cách sử dụng modulo) các bạn có thể dễ dàng chứng minh được rằng nếu $a^2 - b^2$ là số chẵn thì nó phải chia hết cho 4.

Trường hợp $n$ là số lẻ, thì $$f_n f_{n+2} = f_{n+1}^2 - (2013^2 + 4).$$
Do đó $f_n f_{n+2} + 2013^2 + 4 = f_{n+1}^2$ là số chính phương.

Tóm lại, để $f_n f_{n+2} + 2013^2 + 4$ là số chính phương thì $n$ phải là số lẻ.


Xin các bạn lưu ý rằng ở bài toán 2, $$x_1, x_2 = \frac{1}{2}(2013 \pm \sqrt{2013^2 + 4}),$$ nhưng chúng ta không viết nó ra cụ thể vì rườm rà, thay vào đó chúng ta sử dụng công thức Vieta $$x_1 + x_2 = 2013,$$ $$x_1 x_2 = -1.$$



Bài toán 3: Chứng minh rằng với mọi giá trị của $f_0$ và $f_1$, dãy số sau đây luôn luôn tuần hoàn $$f_n = 2 \cos{\frac{\pi}{2013}} f_{n-1} - f_{n-2}.$$
(Dãy số tuần hoàn là dãy số mà tồn tại một chu kỳ $K \neq 0$ sao cho $f_{n+K} = f_n$ với mọi $n$.)

Lời giải: Từ phương trình sai phân $$f_n - 2 \cos{\frac{\pi}{2013}} f_{n-1} + f_{n-2} = 0$$ chúng ta có phương trình đặc trưng $$x^2 - 2 \cos{\frac{\pi}{2013}} x + 1 = 0.$$ $$\Delta' = (\cos{\frac{\pi}{2013}})^2 - 1 = - (\sin{\frac{\pi}{2013}})^2.$$
Phương trình này có hai nghiệm phức $$x_1, x_2 = \cos{\frac{\pi}{2013}} \pm i~ \sin{\frac{\pi}{2013}}.$$
Do đó $$f_n = \alpha ~\cos{\frac{n \pi}{2013}} +  \beta ~ \sin{\frac{n \pi}{2013}}.$$
Từ đó suy ra $$f_{n + 4026} = \alpha ~\cos{\frac{(n+4026) \pi}{2013}} +  \beta ~ \sin{\frac{(n+4026) \pi}{2013}}$$ $$= \alpha ~\cos{(\frac{n \pi}{2013} + 2 \pi)} +  \beta ~ \sin{(\frac{n \pi}{2013} + 2 \pi)}$$ $$= \alpha ~\cos{\frac{n \pi}{2013}} +  \beta ~ \sin{\frac{n \pi}{2013}}= f_n,$$ tức là $\{f_n\}$ là một dãy số tuần hoàn.



Bài toán 4: Cho dãy số $$f_0 = 1, ~~f_1 = 2 \cos{\frac{\pi}{2013}}, ~~ f_n = 4 \cos{\frac{\pi}{2013}} f_{n-1} - 4 f_{n-2}$$
Chứng minh rằng $f_{2013}$ là một số nguyên.

Lời giải: Từ phương trình sai phân $$f_n - 4 \cos{\frac{\pi}{2013}} f_{n-1} + 4 f_{n-2} = 0$$ chúng ta có phương trình đặc trưng $$x^2 - 4 \cos{\frac{\pi}{2013}} x + 4 = 0.$$ $$\Delta' = (2 \cos{\frac{\pi}{2013}})^2 - 4 = - 4 (\sin{\frac{\pi}{2013}})^2.$$
Phương trình này có hai nghiệm phức $$x_1, x_2 = 2 (\cos{\frac{\pi}{2013}} \pm i~ \sin{\frac{\pi}{2013}}).$$
Do đó $$f_n = 2^n ~( \alpha ~\cos{\frac{n \pi}{2013}} +  \beta ~ \sin{\frac{n \pi}{2013}} ).$$
Với $n=0,1$, chúng ta có $$f_0 = \alpha = 1,$$ $$f_1 = 2 ( \alpha~\cos{\frac{\pi}{2013}} +  \beta ~ \sin{\frac{\pi}{2013}} ) = 2 \cos{\frac{\pi}{2013}}.$$
Giải hệ phương trình này chúng ta rút ra được $\alpha = 1$ và $\beta = 0$. Vậy $$f_n = 2^n  ~\cos{\frac{n \pi}{2013}}.$$
Từ đó suy ra $f_{2013} = -2^{2013}$ là một số nguyên.




Bài toán 5: Tìm công thức truy hồi cho dãy số $f_n=n 2^n$.

Lời giải: Chúng ta tìm phương trình đặc trưng có một nghiệm kép $x=2$ bậc 2. Đó là phương trình $$(x−2)^2=x^2− 4 x+ 4=0.$$
Từ đó suy ra phương trình sai phân là $$f_n− 4f_{n−1} + 4f_{n−2}=0.$$
Kết hợp với điều kiện ban đầu chúng ta có công thức truy hồi $$f_0=0, ~~f_1=2, ~~f_n = 4f_{n−1} - 4f_{n−2}.$$



Bài toán 6: Tìm công thức truy hồi cho dãy số $f_n=2n^3−n^2+3n−1$.

Lời giải: Bởi vì $$f_n = (2n^3 - n^2 + 3n-1) 1^n$$ chúng ta tìm phương trình đặc trưng có một nghiệm kép $x=1$ bậc 4. Đó là phương trình $$(x−1)^4=x^4 - 4 x^3 + 6 x^2 - 4 x + 1=0.$$
Từ đó suy ra phương trình sai phân là $$f_n− 4f_{n−1} + 6f_{n−2} - 4 f_{n-3} + f_{n-4}=0.$$
Kết hợp với điều kiện ban đầu chúng ta có công thức truy hồi $$f_0=-1, ~~f_1=3, ~~f_2 = 17, ~~f_3 = 53, ~~f_n = 4f_{n−1} - 6f_{n−2} + 4f_{n-3} - f_{n-4}.$$



Bài toán 7: Cho đa thức $P(x)$ bậc $k$, chứng minh rằng $$P(n) - {{k+1} \choose 1} P(n-1) + {{k+1} \choose 2} P(n-2) - {{k+1} \choose 3} P(n-3)$$ $$ + \dots + (-1)^k {{k+1} \choose k} P(n-k) + (-1)^{k+1} P(n-k-1) = 0.$$

Lời giải: Xây dựng dãy số $$f_n = P(n).$$
Bởi vì $$f_n = P(n) ~ 1^n$$ và đa thức $P(x)$ có bậc là $k$ nên phương trình đặc trưng cho dãy số $f_n$ có một nghiệm kép $x=1$ bậc $k+1$.
Phương trình đặc trưng là $$(x-1)^{k+1} = x^{k+1} - {{k+1} \choose 1} x^k + {{k+1} \choose 2} x^{k-1} - \dots + (-1)^k {{k+1} \choose k} x + (-1)^{k+1} = 0.$$
Từ đó suy ra phương trình sai phân là $$f_n - {{k+1} \choose 1} f_{n-1} + {{k+1} \choose 2} f_{n-2} - \dots + (-1)^k {{k+1} \choose k} f_{n-k} + (-1)^{k+1} f_{n-k-1} = 0.$$
Tức là $$P(n) - {{k+1} \choose 1} P(n-1) + {{k+1} \choose 2} P(n-2) - \dots + (-1)^k {{k+1} \choose k} P(n-k) + (-1)^{k+1} P(n-k-1) = 0.$$



Bài toán 8: Cho dãy số Fibonacci $$F_0 = 0, ~~F_1 = 1, ~~F_n = F_{n-1} + F_{n-2}.$$ Chứng minh rằng $$\frac{F_{2013(n+1)} - F_{2013 (n−1)}}{F_{2013 n}} = \frac{F_{2013(n^{2013}+1)} - F_{2013 (n^{2013}−1)}}{F_{2013 n^{2013}}}.$$

Lời giải: Từ phương trình sai phân $$F_n - F_{n-1} - F_{n-2} = 0$$ chúng ta có phương trình đặc trưng $$x^2 - x - 1 = 0.$$
Phương trình này có hai nghiệm $x_1, x_2$ thoã mãn công thức Vieta $$x_1 + x_2 = 1,$$ $$x_1 x_2 = -1.$$
Chúng ta có $$F_n = \alpha ~ x_1^n + \beta ~ x_2^n.$$

Xây dựng dãy số $$f_n = F_{2013 n}.$$
Chúng ta có $$f_n = \alpha ~ x_1^{2013 n} + \beta ~ x_2^{2013 n} = \alpha ~ (x_1^{2013})^n + \beta ~ (x_2^{2013})^n.$$
Phương trình đặc trưng cho dãy số $f_n$ có hai nghiệm là $x_1^{2013}$ và $x_2^{2013}$.

Chúng ta có $$x_1^{2013} x_2^{2013} = -1.$$
Đặt $$T = x_1^{2013} + x_2^{2013}.$$
Theo công thức Vieta, $x_1^{2013}$ và $x_2^{2013}$ là hai nghiệm của phương trình $$x^2 - T ~x - 1=0.$$
Từ đó suy ra phương trình sai phân cho dãy số $f_n$ là $$f_n− T ~f_{n−1} - f_{n−2}=0.$$

Chúng ta có $$f_{n+1}− T~ f_{n} - f_{n−1}=0.$$
Tức là $$F_{2013(n+1)}− T ~F_{2013 n} - F_{2013 (n−1)}=0.$$

Từ đó suy ra $$\frac{F_{2013(n+1)} - F_{2013 (n−1)}}{F_{2013 n}} = T$$
là một hằng số. Vì vậy cho nên
$$\frac{F_{2013(n+1)} - F_{2013 (n−1)}}{F_{2013 n}} = \frac{F_{2013(n^{2013}+1)} - F_{2013 (n^{2013}−1)}}{F_{2013 n^{2013}}}.$$



Đến đây chúng ta tạm dừng chuổi bài về dãy số. Trong suốt chuổi bài này, chúng ta đã học về cách giải phương trình
$$a_k f_n + a_{k−1} f_{n−1} + a_{k−2} f_{n−2}+ \dots + a_0 f_{n−k}=0,$$ phương trình này được gọi là phương trình sai phân tuyến tính thuần nhất.

Trong tương lai, chúng ta sẽ học tiếp về một loại phương trình khác có tên là phương trình sai phân tuyến tính không thuần nhất, đó là
$$a_k f_n + a_{k−1} f_{n−1} + a_{k−2} f_{n−2}+ \dots + a_0 f_{n−k}=g_n,$$ trong đó $g_n \neq 0$, ví dụ như $$f_n = 5 f_{n-1} - 6 f_{n-2} + 5^n.$$
Dãy số có nhiều ứng dụng rất đẹp, nếu có dịp, chúng ta sẽ học cách dùng dãy số để tính tổng chuỗi số, ví dụ như
$$\sum_{n=1}^{N}{2013^n ~n^2}, ~~~~\sum_{n=1}^{N}{2013^n ~n^2 ~\cos{\frac{n \pi}{2013}}}, ~~~~\sum_{n=1}^{N}{2013^n  ~\sin{\frac{n \pi}{2013}}}.$$

Xin hẹn gặp lại các bạn ở các kỳ sau.