Công thức truy hồi

Dãy số là một ánh xạ từ \(\mathbb{N}\) tới \(\mathbb{R}\)

\[u : \mathbb{N} \to \mathbb{R}, \quad n \mapsto u(n).\]

Khi đó các giá trị \(u(1)\), \(u(2)\), ... được gọi là số hạng của dãy số. Chúng ta cũng có thể viết \(u_1\), \(u_2\), ... thay vì \(u(1)\), \(u(2)\), ..., hoặc thậm chí là \(\{ u_ n \}\).

Cấp số cộng và công thức truy hồi bậc nhất

Cho dãy số \(\{ u_n \}\) với phần tử đầu \(u_0\) và công sai \(d\). Khi đó các phần tử sau đó được tính với công thức

\[u_{n} = u_{n-1} + d\]

với mọi \(n \geqslant 1\) thì \(\{ u_n \}\) được gọi là cấp số cộng.

Như vậy cấp số cộng là một dãy số có dạng

\[u_n = \varphi(n, u_{n-1}).\]

Dãy số có dạng như trên gọi là truy hồi bậc nhất (hay first order).

Ví dụ 18

Dãy số \(\{ u_n \}\) xác định bởi

\[u_n = a u_{n-1} + b n + c\]

với \(u_0\) là số hạng đầu; \(a\), \(b\) và \(c\) là các số thực.

Ví dụ 19

Dãy số \(\{ u_ n \}\) xác định bởi

\[u_n = a u_{n-1}^2 + b u_{n-1} + c\]

với \(u_0\) là số hạng đầu; \(a\), \(b\) và \(c\) là các số thực.

Ta cần chú ý rằng việc nói truy hồi bậc nhất mang nghĩa là số hạng thứ \(n\) chỉ phụ thuộc vào số hạng thứ \(n - 1\), chứ không phải các số hạng trước đó như số hạng thứ \(n - 2\), \(n - 3\), vân vân và mây mây.

Ở ví dụ thứ hai thì số hạng thứ \(n\) là hàm bậc hai theo số hạng thứ \(n - 1\) nhưng đây là công thức truy hồi bậc nhất.

Dãy số Fibonacci và công thức truy hồi bậc hai

Đây có lẽ là dãy số nổi tiếng nhất trong toán học. Công thức của dãy số là với hai phần tử ban đầu \(u_0 = 0\) và \(u_1 = 1\), các phần tử sau sẽ được tính với công thức

\[u_n = u_{n-1} + u_{n-2}\]

với mọi \(n \geqslant 2\).

Ở đây, số hạng thứ \(n\) được tính bởi hai số hạng trước nó nên đây là ví dụ của truy hồi bậc hai. Dãy số truy hồi bậc hai là dãy số có dạng

\[u_n = \varphi(n, u_{n-1}, u_{n-2}).\]

Ví dụ 20

Dãy số \(\{ u_n \}\) được xác định bởi

\[u_n = a u_{n-1} + b u_{n-2} + c\]

với \(u_0\) và \(u_1\) là số hạng đầu; \(a\), \(b\) và \(c\) là các số thực.

Công thức truy hồi bậc cao

Tổng quát, nếu số hạng thứ \(n\) của dãy số \(\{ u_n \}\) được tính bởi \(k\) số hạng trước nó, nghĩa là

\[u_n = \varphi(n, u_{n-1}, u_{n-2}, \ldots, u_{n-k})\]

thì ta gọi là công thức truy hồi bậc \(k\).

Các dãy truy hồi có ứng dụng rộng rãi trong toán học và các ngành khoa học khác, tiêu biểu nhất là dãy Fibonacci ở trên. Trong khoa học máy tính, công thức truy hồi có một ứng dụng để sinh một dãy số cho nhiều mục đích khác nhau như sinh số giả ngẫu nhiên (pseudo-random), sinh khóa cho thuật toán mã hóa dòng (stream cipher). Các ứng dụng này thường sử dụng dãy truy hồi tuyến tính, tức là bậc của các hạng tử \(u_{n-1}\), \(u_{n-2}\), ..., \(u_{n-k}\) không quá \(1\). Nói cách khác thì

\[u_n = a_{n-1} u_{n-1} + a_{n-2} u_{n-2} + \cdots + a_{n-k} u_{n-k} + \phi(n),\]

trong đó \(\phi(n)\) là một hàm số nào đó không phụ thuộc các hạng tử \(u_{n-1}\), ..., \(u_{n-k}\). Các hệ số \(a_{n-1}\), ..., \(a_{n-k}\) nằm trong trường số nào đó tùy thuộc bài toán. Ví dụ với các dãy LFSR (Linear Feedback Shift Register) để sinh dãy trong tin học ở trên thì các phép tính được thực trên trên trường \(\mathbb{F}_2\). Hiện tại chúng ta sẽ khảo sát dãy số với hệ số thực.

Chúng ta quan tâm đến công thức tổng quát của dãy số truy hồi. Dễ thấy rằng, để tính số hạng thứ \(n\) theo truy hồi thì ta phải biết đủ \(k\) số hạng trước đó. Nhưng với mỗi số hạng trong \(k\) số hạng đó ta lại cần đi ngược về trước đó nữa cho đến khi tới các số hạng ban đầu \(u_0\), \(u_1\), ..., \(u_{k-1}\). Tuy nhiên đôi khi chúng ta quan tâm một số tính chất đại số mà cần công thức tổng quát cho \(\{ u_n \}\) và chỉ phụ thuộc \(n\), nghĩa là \(u_n = f(n)\). Khi đó chúng ta sẽ sử dụng phương pháp hàm sinh (hay generating function method, hay метод проводящих функций).

Phương pháp hàm sinh

Phương pháp hàm sinh thực hiện theo các bước sau:

1. Xác định các số hạng ban đầu \(u_0\), \(u_1\), ..., \(u_{k-1}\).

2. Gọi \(G(x)\) là đa thức với hệ số là các số hạng của dãy số, tức là

\[G(x) = u_0 + u_1 x + u_2 x^2 + \cdots + u_n x^n + \cdots\]

3. Phân tích \(G(x)\) thành tổng các phân thức dạng \(\dfrac{1}{H(x)}\). Sau đó ta gom các số hạng có cùng lũy thừa của \(x\) lại để được công thức tổng quát của \(\{ u_n \}\). Các hàm \(H(x)\) sẽ được trình bày ở phần cuối với các ví dụ, và ta gọi chúng là hàm sinh.

Một ví dụ hay dùng của hàm sinh là khai triển sau.

(7)\[\dfrac{1}{1 - mx} = 1 + mx + m^2 x^2 + \cdots + m^n x^n + \cdots\]

Công thức trên có thể thu được từ khai triển Taylor-Maclaurin hoặc bằng quy nạp.

Ví dụ I

Xét dãy số \(\{ u_n \}\) với \(u_0 = 0\), \(u_1 = 1\), và

\[u_n = 5 u_{n-1} - 6 u_{n-2} \ \text{với mọi} \ n \geqslant 2.\]

Đặt

(8)\[G(x) = u_0 + u_1 x + u_2 x^2 + \cdots + u_n x^n + \cdots\]

Khi đó, ta nhân \(G(x)\) với \(x\), \(x^2\) và nhân thêm số hạng để khử các hạng tử theo công thức truy hồi

\[u_n - 5 u_{n-1} + 6 u_{n-2} = 0.\]

Cụ thể, ta tính

\[x \cdot G(x) = u_0 x + u_1 x^2 + u_2 x^3 + \cdots + u_{n-1} x^n + \cdots,\]

và

\[x^2 \cdot G(x) = u_0 x^2 + u_1 x^3 + u_2 x^4 + \cdots + u_{n-2} x^n + \cdots\]

Khi đó

\[\begin{split}G(x) - 5 x \cdot G(x) + 6 x^2 \cdot G(x) & = u_0 + u_1 x + {\color{blue} u_2 x^2} + {\color{green} u_3 x^3} + \cdots {\color{red} + u_n x^n} + \cdots \\ & - 5 u_0 x {\color{blue} - 5 u_1 x^2} {\color{green} - 5 u_2 x^3} - \cdots {\color{red} - 5 u_{n-1} x^n} + \cdots \\ & {\color{blue} + 6 u_0 x^2} {\color{green} + 6 u_1 x^3} + \cdots {\color{red} + 6 u_{n-2} x^n} + \cdots\end{split}\]

Các bạn có thấy điều gì không? Các số hạng trước \(x^2\), \(x^3\), ... đều bằng \(0\) theo công thức truy hồi. Như vậy thu gọn vế trái và thay \(u_0\), \(u_1\) vào vế phải ta có

\[(1 - 5x + 6x^2) \cdot G(x) = u_0 + u_1 x - 5 u_0 x = x,\]

tương đương với

\[G(x) = \dfrac{x}{1 - 5x + 6x^2}.\]

Vì \(1 - 5x + 6x^2\) phân tích thành nhân tử là \((1 - 2x)(1 - 3x)\) nên ta muốn phân tích \(G(x)\) thành tổng

\[G(x) = \dfrac{\alpha}{1 - 2x} + \dfrac{\beta}{1 - 3x} = \dfrac{(\alpha + \beta) + (-3\alpha -2\beta) x}{(1 - 2x)(1 - 3x)},\]

với \(\alpha\) và \(\beta\) là hệ số cần tìm để

\[(\alpha + \beta) + (-3\alpha - 2\beta)x \equiv x.\]

Như vậy, đồng nhất hệ số ta có

\[\alpha + \beta = 0, \quad -3\alpha - 2\beta = 1,\]

giải hệ ta có \(\alpha = -1\) và \(\beta = 1\). Ta thu được

\[G(x) = \dfrac{-1}{1 - 2x} + \dfrac{1}{1 - 3x}.\]

Theo công thức (7), ta có

\[\dfrac{1}{1 - 2x} = 1 + 2x + 2^2 x^2 + \cdots + 2^n x^n + \cdots,\]

và

\[\dfrac{1}{1 - 3x} = 1 + 3x + 3^2 x^2 + \cdots + 3^n x^n + \cdots.\]

Thay hai khai triển trên vào \(G(x)\) ta có

\[\begin{split}G(x) = & - (1 + 2x + 2^2 x^2 + \cdots + 2^n x^n + \cdots) \\ & + (1 + 3x + 3^2 x^2 + \cdots + 3^n x^n + \cdots) \\ = & 0 + (3 - 2) x + (3^2 - 2^2) x^2 + \cdots + (3^n - 2^n) x^n + \cdots\end{split}\]

Đồng nhất hệ số với (8) ta có

\[u_n = 3^n - 2^n.\]

Đây chính là công thức tổng quát của dãy \(\{ u_n \}\).

Tất nhiên là ví dụ trên có thể được giải bằng cách khác là đa thức đặc trưng và đây là phương pháp phổ biến ở phổ thông. Tuy nhiên một số bài toán khác không thể sử dụng đa thức đặc trưng. Trước khi đến với các bài toán như vậy thì mình sẽ liệt kê một số hàm sinh thông dụng để giải quyết các bài toán đó.

Một số hàm sinh thông dụng

\[\boxed{\dfrac{1}{1 - mx} = 1 + mx + m^2 x^2 + \cdots + m^n x^n + \cdots}\]

\[\boxed{\dfrac{1}{(1-x)^t} = \sum_{i=0}^{\infty} C^i_{t+i-1} x^i.}\]

Khi \(t = 2\) thì \(C^i_{i+1} = \dfrac{(i+1)!}{i! \cdot 1!} = i + 1\) nên ta có kết quả

\[\boxed{\dfrac{1}{(1-x)^2} = \sum_{i=0}^\infty (i+1) x^i.}\]

Kết hợp hai công thức trên

\[\boxed{\dfrac{1}{(1 - mx)^t} = \sum_{i=0}^\infty C^i_{t+i-1} m^i x^i.}\]

Ví dụ II

Cho dãy số \(\{ u_n \}\) xác định bởi \(u_0 = 1\), \(u_1 = 2\) và

\[u_n = 6 u_{n-1} - 8 u_{n-2} + n, \ \text{với mọi} \ n \geqslant 2.\]

Tương tự, đầu tiên ta đặt \(G(x)\) là đa thức có hệ số là dãy \(\{ u_n \}\), nghĩa là

\[G(x) = u_0 + u_1 x + u_2 x^2 + \cdots + u_n x^n + \cdots\]

Ta cũng nhân \(x\) và \(x^2\) cho \(G(x)\) và thu được

\[x \cdot G(x) = u_0 x + u_1 x^2 + u_2 x^3 + \cdots + u_{n-1} x^n + \cdots,\]

và

\[x^2 \cdot G(x) = u_0 x^2 + u_1 x^3 + u_2 x^4 + \cdots + u_{n-2} x^n + \cdots\]

Như vậy, hoàn toàn tương tự ví dụ I, mình tính được

\[\begin{split}G(x) - 6x \cdot G(x) + 8x^2 \cdot G(x) & = u_0 \\ & + (u_1 - 6 u_0) x \\ & + (u_2 - 6 u_1 + 8 u_0) x^2 \\ & + (u_3 - 6 u_2 + 8 u_1) x^3 \\ & + \cdots \\ & + (u_n - 6 u_{n-1} + 8 u_{n-2}) x^n \\ & + \cdots\end{split}\]

Cơ mà ở đây \(u_n - 6 u_{n-1} + 8 u_{n-2}\) không đủ để triệt tiêu thành \(0\) mà cần thêm \(n\) nữa. Vậy phải làm sao?

Chúng ta sẽ cần một hàm \(F(x)\) sao cho

\[\begin{split}G(x) - 6x \cdot G(x) + 8x^2 \cdot G(x) + F(x) & = u_0 \\ & + (u_1 - 6 u_0) x \\ & + (u_2 - 6 u_1 + 8 u_0 {\color{red} - 2}) x^2 \\ & + (u_3 - 6 u_2 + 8 u_1 {\color{red} - 3}) x^3 \\ & + \cdots \\ & + (u_n - 6 u_{n-1} + 8 u_{n-2} {\color{red} - n}) x^n \\ & + \cdots\end{split}\]

Như vậy mình gom các hệ số màu đỏ lại sẽ được

\[F(x) = -2x^2 - 3x^3 + \cdots - nx^n + \cdots\]

Khi đó

\[G(x) - 6x \cdot G(x) + 8x^2 \cdot G(x) + F(x) = u_0 + (u_1 - 6 u_0) x,\]

và việc của chúng ta là tìm một hàm sinh biểu thị cho \(F(x)\) nữa để có thể biểu diễn \(G(x)\) như ở ví dụ I.

Ta có

\[\begin{split}F(x) & = -2x^2 - 3x^3 - \cdots - nx^n + \cdots \\ & = 1 x - x (1 + 2x + 3x^2 + \cdots + nx^{n-1} + \cdots) \\ & = x - x (1 + x + x^2 + x^3 + \cdots + x^n + \cdots)' \\ & = x - x \cdot \left(\dfrac{1}{1-x}\right)' \\ & = x - x \cdot \dfrac{1}{(1-x)^2} \\ & = \dfrac{x(1 - 2x + x^2) + x}{(1-x)^2} = -\dfrac{x^2(2 - x)}{(1-x)^2}.\end{split}\]

Thay \(u_0\), \(u_1\) và \(F(x)\) vào ta tính được \(G(x)\) là hàm

\[(1 - 6x + 8x^2) \cdot G(x) - \dfrac{x^2 (2 - x)}{(1-x)^2} = 1 - 4x,\]

tương đương với

\[\begin{split}G(x) & = \dfrac{1}{1 - 6x + 8x^2} \left[ 1 - 4x + \dfrac{x^2(2-x)}{(1-x)^2} \right] \\ & = \dfrac{(1 - 4x)(1 - 2x + x^2) - 2x^2 + x^3}{(1 - 6x + 8x^2)(1-x)^2} \\ & = \dfrac{1 - 2x + x^2 - 4x + 8x^2 - 4x^3 + 2x^2 - x^3}{(1 - 6x + 8x^2)(1-x)^2} \\ & = \dfrac{1 - 6x + 11x^2 - 5x^3}{(1 - 6x + 8x^2)(1 - x)^2}.\end{split}\]

Bây giờ, \(1 - 6x + 8x^2\) phân tích thành nhân tử \((1 - 2x)(1 - 4x)\). Vậy mình sẽ cần tách \(G(x)\) thành

\[G(x) = \dfrac{A}{1 - 2x} + \dfrac{B}{1 - 4x} + \dfrac{C}{1 - x} + \dfrac{D}{(1-x)^2}\]

với \(A\), \(B\), \(C\) và \(D\) là các hệ số cần tìm. Quy đồng mẫu số mình có

\[G(x) = \dfrac{A(1-4x)(1-x)^2 + B(1-2x)(1-x)^2 + C(1-2x)(1-4x)(1-x) + D(1-2x)(1-4x)}{(1 - 6x + 8x^2)(1-x)^2}.\]

Thu gọn tử số lại mình được

\[(A + B + C + D) + (-6A - 4B - 7C - 6D) x + (9A + 5B + 14C + 8D) x^2 + (-4A - 2B - 8C) x^3,\]

và đồng nhất hệ số thì mình cần giải hệ phương trình

\[\begin{split}\begin{cases} A + B + C + D & = 1 \\ -6A - 4B - 7C - 6D & = -6 \\ 9A + 5B + 14C + 8D & = 11 \\ -4A - 2B - 8C & = -5 \end{cases} \Longleftrightarrow \begin{cases} A = -1/2 \\ B = 7/18 \\ C = 7/9 \\ D = 1/3 \end{cases}\end{split}\]

Bây giờ thay các hàm sinh vào \(G(x)\) (chưa cần thay \(A\), \(B\), \(C\) và \(D\) vội) thì mình có

\[\begin{split}G(x) & = A \cdot \left( 1 + 2x + 2^2 x^2 + \cdots + 2^n x^n + \cdots \right) \\ & + B \cdot \left( 1 + 4x + 4^2 x^2 + \cdots + 4^n x^n + \cdots \right) \\ & + C \cdot \left( 1 + x + x^2 + \cdots + x^n + \cdots \right) \\ & + D \cdot \left( 1 + 2x + 3x + \cdots + (n+1) x^n + \cdots \right).\end{split}\]

Nhìn vào hệ số của \(x^n\) mình có công thức tổng quát

\[u_n = A \cdot 2^n + B \cdot 4^n + C + D \cdot (n + 1) = -2^{n-1} + \dfrac{7 \cdot 4^n}{18} + \dfrac{7}{9} + \dfrac{n+1}{3}.\]

Ví dụ III

Trong một số trường hợp "hơi lú", ví dụ như

\[u_n = 4u_{n-1} - 4u_{n-2}\]

thì nếu sử dụng đa thức đặc trưng ta có một phương trình bậc hai với nghiệm kép. Khi đó công thức tổng quát không còn ở dạng

\[u_n = \alpha \cdot z_1^n + \beta \cdot z_2^n\]

với \(z_1\) và \(z_2\) là hai nghiệm phân biệt của phương trình đặc trưng, mà ở một dạng khác. Phương pháp hàm sinh sẽ giúp chúng ta tìm công thức tổng quát ở trường hợp này.

Xét đa thức \(G(x)\) với hệ số là các số hạng của dãy \(\{ u_n \}\) cho bởi công thức truy hồi ở trên:

\[G(x) = u_0 + u_1 x + u_2 x^2 + \cdots + u_n x^n + \cdots\]

Thực hiện tương tự bên trên, mình tính

\[x \cdot G(x) = u_0 x + u_1 x^2 + u_2 x^3 + \cdots + u_{n-1} x^n + \cdots\]

và

\[x^2 \cdot G(x) = u_0 x^2 + u_1 x^3 + u_2 x^4 + \cdots + u_{n-2} x^n + \cdots\]

Như vậy

\[\begin{split}G(x) - 4x \cdot G(x) + 4x^2 \cdot G(x) & = u_0 \\ & + (u_1 - 4u_0) x \\ & + \cancelto{0}{(u_2 - 4u_1 + 4u_0)} x^2 \\ & + \cdots \\ & + \cancelto{0}{(u_n - 4u_{n-1} + 4u_{n-2})} x^n \\ & + \cdots \\ & = u_0 + (u_1 - 4u_0) x.\end{split}\]

Đặt \(G(x)\) làm nhân tử chung và chuyển vế mình có

\[G(x) = \dfrac{u_0 + (u_1 - 4u_0) x}{(1 - 2x)^2}.\]

Mình cần tách \(G(x)\) thành tổng

\[G(x) = \dfrac{A}{1 - 2x} + \dfrac{B}{(1-2x)^2}.\]

Quy đồng mẫu số và đồng nhất hệ số mình cần tìm \(A\) và \(B\) thỏa mãn hệ phương trình

\[\begin{split}\begin{cases} A + B = u_0 \\ -2A = (u_1 - 4u_0) \end{cases} \Longleftrightarrow \begin{cases} A = (-u_1 + 4u_0) / 2 \\ B = (u_1 - 2u_0) / 2 \end{cases}\end{split}\]

Thay hàm sinh vào \(G(x)\) mình được

\[\begin{split}G(x) & = A \cdot (1 + 2x + 2^2 x^2 + \cdots + 2^n x^n + \cdots) \\ & + B \cdot \left[1 + 2 \cdot 2x + 3 \cdot 2^2 x^2 + \cdots + (n+1) \cdot 2^n x^n \right].\end{split}\]

Hệ số trước \(x^n\) cho ta công thức tổng quát của dãy số

\[u_n = A \cdot 2^n + B \cdot (n+1) \cdot 2^n = 2^{n-1} \cdot \left[ 2u_0 + (u_1 - 2u_0) \cdot n \right].\]