小明行樓梯2

史丹福回家時要行上很長的樓梯，途中經常會思考到有趣的數學問題。之前史丹福就討論過一條「小明上樓梯」的問題。今次我們再轉換一下情景。

假如小明要行上一道100級的樓梯，假如這次小明的腿變短了，他可以每次最少行上1級，最多只可以一次上2級。問他有多少種方法去行上這道100級的樓梯？

沒有頭緒？當做數學題做到毫無頭緒的時候，我們不妨試試由較簡單的問題入手，再找找規律。

設小明只可以每步只可以上一級或兩級樓梯，他共要上n級樓梯，總共有s_n個方法。我們的問題要求的是s₁₀₀。

如果他需上零級樓梯，那麼他當然只有一個方法，就是企定定一級都不上，所以s₀ = 1。如果他需上一級樓梯，那麼也只有一個方法，就是行一步上一級，所以s₁ = 1。如果他需上兩級樓梯，有兩個方法，就是一步上兩級，或者分兩步各上一級，s₂ = 2。 之後，我們也不難計算到s₃ = 3，s₄ = 5，s₅ = 8，s₆ = 13...

1, 1, 2, 3, 5, 8, 13... 聰明的你可能認得，這不就是大名鼎鼎的斐波那契數列（Fibonacci sequence）嗎？

斐波那契數列中，每個數字都是數列中前兩個數字的和，1 + 1 = 2，1 + 2 = 3，2 + 3 = 5，3 + 5 = 8，5 + 8 = 13... 為甚麼這個神奇的數列會出現在這樣的一條排列組合問題中呢？

試想想，假如小明要行上n級樓梯，他的最後一步有兩個可能性，行一級或兩級。假如最後一步是上一級，那麼他行上之前的手n - 1級有a_n-1個方法；假如最後一步是上兩級，那麼他行上之前的n - 2級有s_n-2個方法。因此行上n級樓梯有s_n-1 + s_n-2個方法，也就是說s_n = s_n-1 + s_n-2。這正正就是斐波那契數列生成的方法。

至於如何求s₁₀₀，也就是斐波那契數列中的第101項呢？我們當然可以慢慢加上攞去，不過這樣又麻煩又廢時，幸好我們有更聰明優雅的方法，就是利用公式：

至於這公式是如何得出呢？原來當有a_n + ba_n-1 + ca_n-2 = 0的關係時，a_n必定等如 C₁ λ₁ⁿ + C₂ λ₂ⁿ，其中λ₁與λ₂為λ² + bλ + c = 0的兩個根，而C1與C2為常數。

對斐波那契數列來說，a_n - a_n-1 - a_n-2 = 0。λ² - λ - 1 = 0的兩個根就是(1 + √5) /2及(1 - √5) /2。設a_n = C₁ [(1 + √5) /2]ⁿ + C₂ [(1 - √5) /2]ⁿ，代入a₁ = 1及a₂ = 1，就可以得到這公式。

最後，代入公式，得到573147844013817084101，也就是說小明有573147844013817084101種方法行上樓梯。