2 歸納定義與證明

2.11 完全歸納

說到遞迴定義，費氏數(Fibonacci number) 是最常見的教科書例子之一。 簡而言之，第零個費氏數是 0, 第一個費氏數是 1, 之後的每個費氏數是之前兩個的和。 寫成遞迴定義如下：

fib :: Nat -> Nat
fib 0      = 0
fib 1      = 1
fib (2+n)  = fib (1+n) + fib n

但這和我們之前談到的歸納定義稍有不同。 我們已知定義 f (Suc n) 時可假設 f 在 n 之上已有定義。 但在 fib 的定義中，fib (2+n) 用到了 fib 的前兩個值。這樣的定義是可以的嗎？

函數 fib 的定義可以視為完全歸納% （又稱作強歸納）的例子。 回顧：先前介紹的數學歸納法中，使 P n 成立的前提之一是「對所有 n, 若 P n 成立， P (Suc n) 亦成立」。完全歸納則把這個前提增強如下：

給定述語P :: Nat -> Bool. 若

  • 對所有小於 n 的值 i，P i 皆 成立，則 P n 亦成立，

則我們可得知 P 對所有自然數皆成立。

以更形式化的方式可寫成：

  (∀ n . P n)   <==  (∀ n . P n  <== (∀ i < n . P i))     (2.9 )

請注意：前提 P n <== (∀ i < n . P i) 隱含 P 0 成立，因為當 n := 0, 由於沒有自然數 i 滿足 i < n, 算式 (∀ i < n . P i) 可化簡為 True.

在完全歸納法之中，證明 P n 時，我們可假設 P 對所有小於 n 的值都已成立了。 對寫程式的人來說，有了完全歸納法，表示我們日後定義自然數上的函數 f :: Nat -> a 時，每個 f n 都可以自由使用 f 在所有小於 n 的輸入之上的值。因此 fib (2+n) 可以用到 fib (1+n) 與 fib n, 因為 n < 1+n < 2+n.

例 2.15

關於完全歸納，離散數學教科書中的一個常見例子是「試證明所有自然數都可寫成不相同的二的乘冪的和」，例如 $50 = 2^5 + 2^4 + 2$. 這可用完全歸納證明。我們以半形式的方式論述如下： 令 P n 為「$n$可寫成一串不相同的二的乘冪的和」. 對所有 n, 我們想要證明 P n <== (∀ i < n . P i). 當 n 為 Zero, 這一串數字即是空串列。 當 n 大於零，

  • 我們可找到最接近 n 但不超過 n 的二之乘冪，稱之為 m（也就是 $m = 2^k$ 而且 $m \leq n < 2\times m$）.

  • 由於 $n$ 不是 Zero, $m$ 也不是 Zero. 也因此 n - m < n.

  • 依據歸納假設 (∀ i < n . P i), 以及 n - m < n, P (n-m) 成立 --- n - m 可以寫成不相同的二的乘冪的和。

  • 也因此 n 可寫成不相同的二的乘冪的和 --- 把 n-m 加上 $m$ 即可.

上述證明僅用口語描述，因為如果形式化地寫下這個證明，就等同於寫個將自然數轉成一串二的乘冪的程式，並證明其正確性！下述函數 binary 做這樣的轉換，例如，binary 50 = [32,16,2]:

binary :: Nat -> List Nat
binary Zero  = []
binary n     = m : binary (n - m) 
   where  m     = last (takeWhile (<=n) twos)
          twos  = iterate (2 *:) 1

函數 binary 是一個完全歸納定義，和上述的證明對應得相當密切：串列 twos 是 [1,2,4,8...] 等等所有二的乘冪，m 是其中最接近而不超過 n 的。 遞迴呼叫 binary (n - m) 是許可的，因為 n - m < n, 而根據完全歸納，我們已假設對所有 i < n, binary i 皆有定義。

有了完全歸納法，我們在定義自然數上的函數時可允許更靈活的函數定義：

f :: Nat -> a
f b = ....                 {- 一些基底情況 -}
f n = ... f m ... f k ...  {- 如果 m < n 且 k < n -}

f n 的右手邊可以出現不只一個遞迴呼叫，只要參數都小於 n. 但我們必須確定上述定義中的幾個子句足以包含所有狀況，沒有狀況被遺漏。 例如，我們若 把 fib 定義中的 fib 1 = ... 基底狀況去掉， 計算 fib 2 = fib 1 + fib 0 時便會出錯。

練習 2.43

證明 sum (binary n) = n.

答案

使用完全歸納。

狀況 n := Zero: 等號兩邊都歸約為 [].

狀況 n > Zero。 假設對於任何 0 <= i < n, sum (binary i) = i.

   sum (binary n) =
=    {- 令 m = last (takeWhile (<=n) twos), sum 之定義 -}
   m + sum (binary (n - m))
=    {- 因 n - m < n, 歸納假設 -}
   m + (n - m)
=  n
練習 2.44

證明當 n >= 1, fib (2+n) > {-"\alpha^n"-}, 其中 $\alpha = (1+\sqrt{5})/2$. 這個證明可用 n := 1 和 n := 2 當基底狀況。

答案

本證明的關鍵性質是 $\alpha^2 = (3+\sqrt{5})/2 = \alpha + 1$. 使用完全歸納證明 fib (2+n) > {-"\alpha^n"-}，以 n := 1 和 n := 2 當基底狀況。

狀況 n := 1: fib 3 = 2 > {-"\alpha"-}.

狀況 n := 2: fib 4 = 3 > {-"(3+\sqrt{5})/2 = \alpha^2"-}.

狀況 n := 2+n 且 2+n > 4。 假設對於任何 3 <= i < 2+n, fib i > {-"\alpha^{i-2}"-}. 論證：

    fib (2+n)
 =  fib (1+n) + fib n
 >    {- 歸納假設 -}
    {-"\alpha^{n-1}"-} + {-"\alpha^{n-2}"-}
 =    {- 提出 $\alpha^{n-2}$-}
    {-"(\alpha + 1) \times \alpha^{n-2}"-}
 =    {- $\alpha^2 = \alpha + 1$ -}
    {-"\alpha^2 \times \alpha^{n-2}"-}
 =  {-"\alpha^n"-}

完全歸納 vs 簡單歸納   完全歸納有個較早的稱呼：強歸納(strong induction)。 原本的歸納法則相對被稱呼為簡單歸納或弱歸納。 強/弱歸納的稱呼可能使人以為完全歸納比簡單歸納更強 --- 意謂前者能證明出一些後者無法證明的定理。 事實上，完全歸納與簡單歸納是等價的：能用一個方法證出的定理，用另一個方法也能證出。 因此，使用哪一個純粹只是方便性的考量。

反應在程式設計上，給任一個完全歸納定義函數 f :: Nat -> A, 我們總能做出一個以簡單歸納定義的函數 fs :: Nat -> List A, 滿足 fs n = map f [n, n-1, ... 0]. 例如，函數 fibs n 傳回 [fib n, fib (n-1).., fib 0].

fibs :: Nat -> List Nat
fibs 0        = [0]
fibs 1        = [1,0]
fibs (Suc n)  = (x1+x0) : x1 : x0 : xs  
    where (x1:x0:xs) = fibs n

由 fib 到 fibs 的轉換可能令讀者想起演算法中的動態規劃(dynamic programming)。我們將在日後談到這個話題。

串列上的完全歸納   串列與自然數是類似的資料結構。串列上的完全歸納原則便是將 Zero 代換為 [], 將 Suc 代換為 (x:). 至於「小於」的關係，可定義為：

ys < xs  <=> ys ∈ tails xs ⋀ ys /= xs

也就是說 ys 是 xs 的一個後段，但不是 xs 自己。 有了如上定義，串列上的完全歸納法是：

(∀ xs . P xs)   <==  (∀ xs . P xs  <== (∀ ys < xs . P ys))

應用在程式設計上，當定義 f xs 時，遞迴呼叫可作用在 xs 的任何後段上。

但對許多串列上的函數而言，這樣的模式還不夠靈活。我們得用下一節說到的良基歸納。