Một con châu chấu nhảy từ O(0;0) đến A(9;0), mỗi lần nhảy 1 hoặc 2 bước. Hỏi có bao nhiêu cách nhảy?

Giải chi tiết:

Gọi x là số lần nhảy 1 bước, y là số lần nhảy 2 bước.

Ta có:

  \[x + 2y = 9,\quad x,y \in \mathbb{N}.\]

Các nghiệm nguyên:

  \[(9,0),(7,1),(5,2),(3,3),(1,4).\]

Với mỗi cặp (x,y), số cách sắp xếp là: \[C_{x + y}^x.\]

Tổng số cách:

  \[C_9^9 + C_8^7 + C_7^5 + C_6^3 + C_5^1 = 1 + 8 + 21 + 20 + 5 = 55.\]

Mở rộng:

·        Công thức tổng quát: Bài toán bước nhảy 1 hoặc 2 → số cách chính là số Fibonacci.

  \({F_{n + 1}} = F\_n + {F_{n - 1}}\)

·        Với 9 bước, số cách nhảy \( = \;{F_{10}} = 55\).