Giả sử bạn đang ở một bữa tiệc với chín người khác và mọi người đều bắt tay nhau đúng một lần. Có bao nhiêu cái bắt tay diễn ra?

Đây là “vấn đề bắt tay” và là một trong những vấn đề tôi yêu thích nhất. Là một giáo viên dạy toán, tôi thích nó vì có rất nhiều cách khác nhau để bạn có thể tìm ra lời giải, và sự đa dạng cũng như mối liên kết giữa các chiến lược đó minh họa rất hay cho sức mạnh của tư duy sáng tạo trong toán học.

Một giải pháp như sau: Bắt đầu bằng việc mỗi người bắt tay nhau. Mười người, mỗi người có chín cái bắt tay, sẽ có tổng cộng 9 × 10 = 90 cái bắt tay. Nhưng điều này tính mỗi cái bắt tay hai lần — một lần từ góc nhìn của mỗi người lắc — vì vậy số lần bắt tay thực tế là $latex frac{90}{2} = 45$. Một đối số đếm đơn giản và đáng yêu để giành chiến thắng!

Ngoài ra còn có một cách hoàn toàn khác để giải quyết vấn đề. Hãy tưởng tượng rằng từng vị khách đến một lúc và khi đến nơi, họ bắt tay tất cả những người có mặt. Người đầu tiên không có tay để bắt tay, vì vậy trong bữa tiệc chỉ có một người thì không có tổng số lần bắt tay. Bây giờ người thứ hai đến và bắt tay người thứ nhất. Điều này sẽ thêm một cái bắt tay vào tổng số, vì vậy trong một nhóm hai người, có tổng số 0 + 1 = 1 cái bắt tay. Khi người thứ ba đến và bắt tay hai vị khách đầu tiên, tổng cộng sẽ có hai cái bắt tay. Sự xuất hiện của người thứ tư sẽ cộng thêm ba cái bắt tay vào tổng số, v.v.

Chiến lược này mô hình hóa trình tự bắt tay theo cách đệ quy, nghĩa là mỗi thuật ngữ trong trình tự được xác định tương ứng với các thuật ngữ đứng trước nó. Có thể bạn đã quen thuộc với dãy Fibonacci, dãy đệ quy nổi tiếng nhất. Nó bắt đầu từ 1, 1, 2, 3, 5, 8, 13, 21 và tiếp tục với mỗi số hạng tiếp theo bằng tổng của hai số trước.

Như chúng ta sẽ thấy bên dưới, đệ quy là một khuôn khổ linh hoạt và mạnh mẽ để suy nghĩ về nhiều ý tưởng toán học. Và mặc dù các học giả Ấn Độ cổ đại như Hemachandra được cho là đã biết về những loại trình tự này từ tận năm 1150, nhưng chúng vẫn đưa ra những thách thức hấp dẫn cho các nhà toán học ngày nay.

Hãy xem cách suy nghĩ đệ quy giúp giải quyết vấn đề bắt tay như thế nào. Nếu chúng ta để $latex a_n$ bằng số lần bắt tay tại một n-người, chúng ta có thể biểu diễn mối quan hệ đệ quy này bằng công thức sau:

$latex a_n = a_{n-1} + n–1$

Điều này cho chúng ta biết rằng số lần bắt tay tại một n-người trong nhóm ($latex a_n$) bằng số lần bắt tay tại một (n − 1) nhóm người ($latex a_{n-1}$) cộng n − Thêm 1 cái bắt tay nữa, thể hiện ý tưởng rằng khi một người mới đến, họ sẽ thêm một số cái bắt tay mới nhất định vào số những cái bắt tay đã diễn ra.

Trong phiên bản cụ thể của bài toán bắt tay, chúng ta muốn biết $latex a_{10}$, số lần bắt tay trong một bữa tiệc 10 người, do đó, để thấy rằng chúng ta sử dụng mối quan hệ đệ quy

$latex a_{10} = a_9 + 9$

Để tìm giá trị của $latex a_{10}$, chúng ta chỉ cần biết giá trị của $latex a_9$ và thêm 9 vào đó. Làm cách nào để tìm giá trị của $latex a_9$? Tất nhiên là bằng cách sử dụng đệ quy!

$latex a_9 = a_8 + 8$

Bây giờ, để tìm giá trị của $latex a_8$, chúng ta cần tìm giá trị của $latex a_7$, giá trị này đòi hỏi phải biết $latex a_6$, v.v. Tại thời điểm này, bạn có thể lo lắng rằng điều này sẽ tiếp diễn mãi mãi theo kiểu giảm dần vô hạn, nhưng khi chúng ta đạt đến $latex a_1$ thì chúng ta đã hoàn tất, vì chúng ta biết rằng tổng số lần bắt tay là bằng không trong bữa tiệc một người.

$latex a_1 = 0$

Giá trị ban đầu hay giá trị “hạt giống” này là đặc điểm chính của chuỗi đệ quy. Nó đảm bảo rằng quá trình quay lui xuyên suốt chuỗi sử dụng mối quan hệ đệ quy này sẽ kết thúc. Khi bạn đạt đến giá trị ban đầu, quá trình quay lại sẽ dừng lại và sau đó bạn có thể tiến hành theo cách của mình trong danh sách để nhận được giá trị bạn muốn.

$latex a_1 = 0$

$latex a_2 = a_1 + 1 = 0 + 1 = 1$

$latex a_3 = a_2 + 2 = 1 + 2 = 3$

$latex a_4 = a_3 + 3 = 3 + 3 = 6$

$cdots$

$latex a_{10} = a_9 + 9 = 36 + 9 = 45$

Bằng cách xem xét danh sách, chúng ta thấy rằng có tổng cộng 45 cái bắt tay trong một bữa tiệc gồm 10 người, phù hợp với tính toán ban đầu của chúng ta. Nếu bạn giống học sinh của tôi, bạn có thể hỏi tại sao chúng ta cần một cách khác để giải quyết vấn đề này khi chúng ta đã biết câu trả lời, đặc biệt vì cách tiếp cận thứ hai này dường như mất nhiều thời gian hơn.

Đó là một câu hỏi hay. Một câu trả lời là cách tiếp cận đệ quy cho chúng ta một cái nhìn hoàn toàn khác về những gì đang diễn ra trong bài toán này, và những quan điểm khác nhau rất hữu ích trong toán học, cũng như trong mọi thứ. Chúng mang đến cho chúng ta những cơ hội khác nhau để hiểu các khái niệm và cho phép chúng ta sử dụng các công cụ khác nhau, điều này có thể giúp ích khi chúng ta gặp khó khăn.

Đặc biệt, đệ quy rất hữu ích vì nó có mặt ở mọi nơi trong toán học. Ví dụ, nó phát sinh trong các mối quan hệ tuyến tính mà mọi người học trong lớp toán - những mối quan hệ được đặc trưng bởi tốc độ thay đổi không đổi và được biểu thị bằng các đường thẳng trong mặt phẳng. Một hàm tuyến tính như $latex f(x) = 3x + 5$ có thể được coi là một công thức đệ quy:

$latex a_0 = 5$

$latex a_n = a_{n-1} + 3$

Mặc dù cách rõ ràng hơn để nghĩ về $latex f(2)$ có thể là $latex f(2) = 3 nhân 2 + 5 = 11$, một cách khác là $latex a_2 = a_1 + 3 = a_0 + 3 + 3 = 11$. Mô hình đệ quy đặc tính cơ bản của hàm tuyến tính - tốc độ thay đổi không đổi - cho chúng ta một cách khác để suy nghĩ về mối quan hệ này. Điều tương tự có thể được thực hiện với các hàm số mũ được đặc trưng bởi sự thay đổi cấp số nhân không đổi.

Tư duy đệ quy cũng hoạt động vượt ra ngoài chuỗi số. Nếu bạn đã từng giải một hệ phương trình, chắc chắn bạn đã áp dụng phương pháp đệ quy. Để giải quyết hệ thống

$latex 2x + y = 10$

$latex 3x – y = 5$

trước tiên bạn có thể cộng hai phương trình lại với nhau để loại bỏ y biến, dẫn đến phương trình $latex 5x = 15$. Giải câu này để được $latex x =$ 3, thay thế để tìm $latex y = 4$, thế là xong. Cách tiếp cận này sử dụng thuật toán đệ quy, trong đó giải pháp cho hệ thống được xây dựng từ giải pháp cho các hệ thống nhỏ hơn, có liên quan. Ví dụ, để giải hệ 3 × 3, bạn loại bỏ một biến để biến nó thành hệ 2 × 2, và sau đó lại biến nó thành hệ 1 × 1. Phương trình đơn giản dễ giải này giống như giá trị ban đầu của quá trình đệ quy này. Nó báo hiệu sự kết thúc của quá trình quay lui và từ đó bạn tìm cách quay lại chuỗi phương trình, giống như trong một chuỗi đệ quy.

Thậm chí còn có các kỹ thuật chứng minh đệ quy. Ví dụ, một công thức nổi tiếng trong hình học là công thức tổng các góc của đa giác, trong đó nói rằng tổng số đo các góc trong của một nđa giác có cạnh là $latex (n-2) nhân 180^{circ}$. Một cách để chứng minh kết quả này là bắt đầu bằng một n-gon và tưởng tượng điều gì sẽ xảy ra nếu bạn loại bỏ một hình tam giác.

Loại bỏ một hình tam giác sẽ biến n-gon vào một (n − 1)-gon, và nó cũng loại bỏ số đo góc trong 180 độ. Đây là một mối quan hệ đệ quy: Tổng các góc trong của một n-giác lớn hơn 180 độ so với tổng góc trong của một (n − 1)-gon. Để thiết lập kết quả chung, hãy tiếp tục xóa các hình tam giác cho đến khi bạn đạt đến giá trị gốc, trong trường hợp này xảy ra khi bạn đã xóa tất cả trừ ba n-các đỉnh của -gon. Tại thời điểm này, đa giác ban đầu đã được thu gọn thành một hình tam giác có tổng các góc trong bằng 180 độ. Bây giờ hãy thực hiện ngược lại, cộng 180 độ ở mỗi bước và bạn sẽ có được công thức.

Quay trở lại với bữa tiệc của chúng ta, bản thân vấn đề bắt tay đã cho chúng ta thấy điều gì có thể xảy ra khi chúng ta suy nghĩ sáng tạo và sau đó kết nối nhiều quan điểm khác nhau của một vấn đề lại với nhau. Nếu chúng ta thử sử dụng mô hình đệ quy cho chuỗi bắt tay của mình:

$latex a_1 = 0$

$latex a_n = a_{n-1} + n – 1$

một mô hình đẹp xuất hiện:

$latex a_2 = a_1 + 1 = 0 + 1$

$latex a_3 = a_2 + 2 = 0 + 1 + 2$

$latex a_4 = a_3 + 3 = 0 + 1 + 2 + 3$

$cdots$

$latex a_n = a_{n-1} + (n-1) = 0 + 1 + 2 + 3 + cdots + (n-1)$

Bây giờ chúng ta có một cách nhìn tổng quát và mới về vấn đề này: Số lần bắt tay trong một n-người bên bằng tổng của bên thứ nhất n − 1 số nguyên dương.

Hãy nghĩ lại cách tiếp cận ban đầu của chúng tôi. trong một n-người trong nhóm, mỗi người sẽ bắt tay người kia n − 1 người. Tích $latex n (n-1)$ tính mỗi lần bắt tay hai lần, vì vậy tổng số lần bắt tay là $latex frac{n(n-1)}{2}$. Nhưng vì các phương pháp khác nhau của chúng ta tính cùng một thứ nên chúng phải mang lại kết quả giống nhau. Đặc biệt, điều này có nghĩa là:

$latex 1 + 2 + 3 + cdots + (n-1) = frac{n(n-1)}{2}$

Bằng cách kết nối các cách tiếp cận khác nhau với bài toán bắt tay, chúng ta có được một công thức đóng cho tổng của công thức đầu tiên. n − 1 số nguyên dương. Nhưng chúng ta còn nhận được nhiều hơn thế: biểu thức $latex frac{n(n-1)}{2}$ bao gồm một phân số, nhưng vì nó bằng tổng của các số nguyên nên nó cũng phải là một số nguyên. Điều này chứng tỏ một thực tế đơn giản của lý thuyết số: Với mọi số nguyên n, $latex frac{n(n-1)}{2}$ là số nguyên.

Kiểu lập luận tương tự này tiếp tục tạo sức mạnh cho toán học hiện đại. Lấy một ví dụ, các nhà nghiên cứu vào đầu những năm 2000 đã chứng minh một số kết quả đáng ngạc nhiên về các chuỗi đệ quy được gọi là chuỗi Somos bằng cách chỉ ra rằng chúng cũng có giá trị nào đó. Thông qua sức mạnh của những kết nối sáng tạo, các nhà toán học một lần nữa khám phá ra nơi họ có thể đi tới bằng cách hiểu rõ họ đã ở đâu.

Các bài tập

1. Tìm công thức đóng cho dãy được xác định đệ quy như sau
$latex a_1 = 1$
$latex a_n = a_{n-1} + 2n – 1$

2. Ở cuối cột, biểu thức $latex frac{n(n-1)}{2}$ được hiển thị là một số nguyên mặc dù biểu thức bao gồm một phân số, bởi vì $latex frac{n(n-1 )}{2}$ là kết quả của việc đếm thứ gì đó. Ngoài ra còn có một lập luận lý thuyết số cho thấy biểu thức này phải là số nguyên. Nó là gì?

3. Tìm số hạng đầu tiên của dãy đệ quy
$latex a_1 = 1$
$latex a_n = frac{1}{1+a_{n-1}}$

4. Tìm số hạng đầu tiên của dãy đệ quy
$latex a_1 = 1$
$latex a_2 = 1$
$latex a_n = a_{n-1} – a_{n-2}$