Chapter 4 歸納(Induction)與遞迴(Recursion) Discrete Mathematics Chapter 4 歸納(Induction)與遞迴(Recursion) 大葉大學 資訊工程系 黃鈴玲

4.1 數學歸納法 已知： 1. 我們能到達梯子的第一階。 2. 假設能到達梯子的某一階，就必能到達梯子的下一階。 例：爬「無限長」的梯子 已知： 1. 我們能到達梯子的第一階。 2. 假設能到達梯子的某一階，就必能到達梯子的下一階。 問：我們是否能到達這個梯子的每一階？

P(n) : 一個命題式函數 (例如： n  2n) 1. 基礎步驟(Basis): 證明P(1)為真 (即：n代入1時公式成立) (若 n 從 0 開始則證 P(0)為真，要證明式子在n最小時會成立) 2. 歸納步驟(Inductive) : 證明當k為任意正整數時，若P(k)成立則P(k+1)也成立 (即：假設n代入k時公式成立， 利用此假設，證明假設n代入k+1時公式成立) 注意 : 數學歸納法只能用來證明某個公式的正確性，不能用來 找出公式.

Example 1 證明當n為正整數時， . Proof. (Basis) n=1時： 成立 (Inductive) 假設n=k時上式成立， 即： 當n=k+1時， 左式= 1+2+…+k+(k+1) = = = 右式，故由歸納法得證

Example 2. 使用歸納法證明首n個正奇數的和是n2. 注意：其實不用歸納法也可以得証： Pf : Basis : n=1時： 1 = 12 成立 Inductive : 假設n=k時上式成立，即: 1+3+5+…+(2k-1) = k2 當n=k+1時，左式= 1+3+5+…+(2k-1)+(2k+1) = k2 + 2k+1 = (k+1)2 =右式 故根據數學歸納法得證。

Example 5. 利用數學歸納法證明： “對所有正整數n，不等式 n < 2n 都成立”。 pf : Basis: n=1時，1 < 21 成立. Inductive : 假設n=k 時上式成立，即 k < 2k. 當 n=k+1時 : 左式= k + 1 < 2k + 1  2k + 1 =右式 ∴ k + 1 < 2k + 1 也成立 故根據數學歸納法得證。

Exercise 4.1 3. 證明當n為任意正整數時， 7. 證明當n為 0 的整數時，

(跳過) Example 7. The harmonic numbers Hk, k =1,2,3,…, are defined by . Use MI to show that whenever n is a nonnegative integer. Pf : Let P(n) be the proposition that “ ”. Basis step : P(0) is true, since . Inductive step : Assume that P(k) is true for some k, i.e., Consider P(k+1) :

By MI, P(n) is true for all nZ+. (跳過) ∴P(k+1) is true. By MI, P(n) is true for all nZ+. Exercise : 7, 13

4.2 Strong Induction(強數學歸納法) (跳過) 4.2 Strong Induction(強數學歸納法) Basis step 相同 Inductive step : Assume all the statements P(1), P(2), …, P(k) are true. Show that P(k+1) is also true.

Example 2. 證明若 n為 >1的整數，則 n 可以寫成質數的乘積。 (跳過) Example 2. 證明若 n為 >1的整數，則 n 可以寫成質數的乘積。 Pf : 令 P(n) 表示 “n 可以寫成質數的乘積” 這一命題. Basis : P(2) is true, 因為 2 是質數 Inductive : 假設 P(2), P(3), …, P(k) 都是true. 考慮 P(k + 1) : Case 1 : k + 1 is prime  P(k+1) is true Case 2 : k + 1 is composite, i.e., k + 1 = ab where 2  a  b ＜ k+1 根據歸納法的假設, a 及 b都可以寫成質數的乘積.  k + 1也是質數的乘積 故 P(k+1) is true. 根據強數學歸納法得證. Note: 此題無法僅用普通的歸納法證明

Basis : P(12) is true, since 12 = 4  3; (跳過) Example 4. Prove that every amount of postage of 12 cents or more can be formed using just 4-cent and 5-cent stamps. Pf : Let P(n) be the statement that the postage of n cents can formed using just 4-cent and 5-cent stamps. Basis : P(12) is true, since 12 = 4  3; P(13) is true, since 13 = 4  2 + 5  1; P(14) is true, since 14 = 4  1 + 5  2; P(15) is true, since 15 = 5  3; Inductive : Assume P(12), P(13), …, P(k) are true. Consider P(k+1) : Suppose k-3 = 4  m + 5  n. Then k+1 = 4  (m+1) + 5  n.  P(k+1) is true. By Strong MI, P(n) is true if nZ and n 12. (k-3  12) Exercise : 7

4.3 遞迴定義. Def. 使用一個物件本身來定義它自己的過程稱為recursion(遞迴). 4.3 遞迴定義. Def. 使用一個物件本身來定義它自己的過程稱為recursion(遞迴). 例: 定義一個無窮數列 1, 2, 4, 8, 16, 32, 64, …時 (1) 使用明確的公式，可寫成: an=2n, n=0,1,2,… (2) 使用遞迴的形式，可寫成: 初始值： a0=1, 遞迴式： an+1=2an, n=0, 1, 2, …

Example 1. 假設函數 f 以遞迴方式定義如下： f(0)=3, f(n+1) = 2f(n)+3 求出 f(1), f(2), f(3), f(4). Sol : f(1) = 2f(0) + 3 =9 f(2) = 2f(1) + 3 =21 f(3) = 2f(2) + 3 =45 f(4) = 2f(3) + 3 =93

Example 2. 寫出階乘函數 F(n) = n! 的遞迴定義。 Sol : 初始值 : F(0) = 1 遞迴式 : 因 F(n+1) = (n+1)!, F(n) =n! 故 F(n+1) = F(n)  (n+1) Def1, Example 5. 費式數(Fibonacci numbers) f0, f1, f2, … 定義如下: 初始值： f0 = 0, f1 = 1, 遞迴式： fn = fn-1 + fn-2, for n = 2,3,4,… What is f5 ? Sol : f2 = f1 + f0 =1 f3 = f2 + f1 =2 f4 = f3 + f2 =3 f5 = f4 + f3 =5

Exercise 4.3 1. 根據 f(0)=1 與下列遞迴定義的 f(n) (n = 0, 1, 2, …)， 求出 f(1), f(2), f(3), f(4)。 (b) f(n+1) = 3f(n) (d) f(n+1) = f(n)2 + f(n) + 1 3. 根據 f(0)= -1，f(1)= 2 與下列遞迴定義的 f(n) (n = 0, 1, 2, …)，求出 f(2), f(3), f(4), f(5)。 (a) f(n+1) = f(n) + 3f(n-1) 8. 找出序列{an} (n = 1, 2, 3, …) 的遞迴定義，若 (a) an = 4n - 2 (c) an = n (n - 1)

Example 6. Show that fn > a n-2 , where (跳過) Example 6. Show that fn > a n-2 , where Pf: ( By Strong MI ) Let P(n) be the statement fn >a n-2 . Basis: f3 = 2 > a so that P(3) and P(4) are true. Inductive: Assume that P(3), P(4), …, P(n) are true. We must show that P(n+1) is true. fn+1 = fn + fn-1 > a n-2 + a n-3 = a n-3(a +1) ∵ a +1= a 2 ∴ fn+1 > a n-3  a 2 = a n-1 We get that P(n+1) is true. By Strong MI , P(n) is true for all n  3

(跳過) ※Recursively defined sets. Example 7. Let S be defined recursively by 3S x+yS if xS and yS. Show that S is the of positive integers divisible by 3 (i.e., S = { 3, 6, 9, 12, 15, 18, … } Pf: Let A be the set of all positive integers divisible by 3. We need to prove that A=S. (i) A  S : (By MI) Let P(n) be the statement that 3nS … (ii) S  A : (利用S的定義) (1) 3  A , (2) if xA,yA, then 3|x and 3|y.  3|(x+y)  x+yA ∴S  A S = A

recursive def : l(wx)=l(w)+1 if w*, x. (跳過) Definition 2. The set of strings over an alphabet is denoted by *. The empty string is denoted by l, l , and wx* whenever w* and x. eg.  = { a, b, c } * = { l, a , b , c , aa , ab , ac , ba , bb , bc, … abcabccba, …} la lb lc Example 9. Give a recursive definition of l(w), the length of the string w* Sol : initial value : l(l)=0 recursive def : l(wx)=l(w)+1 if w*, x.

0x1A if xA. ∴當bit string a = 000…011…1 時 aA Exercise 13, 48, 49 (跳過) Exercise 13, 48, 49 Exercise 39. When does a string belong to the set A of bit strings defined recursively by lA 0x1A if xA. Sol : A={l, 01 , 0011, 000111, …} ∴當bit string a = 000…011…1 時 aA 0l1 n個

A(m-1, A(m, n-1)) if m  1 and n  2 (跳過) Ackermann’s function A(m, n) = 2n if m = 0 0 if m  1 and n = 0 2 if m  1 and n = 1 A(m-1, A(m, n-1)) if m  1 and n  2 Exercise 49 Show that A(m,2)=4 whenever m  1 Pf : A(m,2) = A(m-1, A(m,1)) = A(m-1,2) whenever m  1. A(m,2) = A(m-1,2) = A(m-2,2) = … = A(0,2) = 4.

4.4 遞迴演算法 ※ 有時，我們能將有特定輸入集合的問題簡化，變成輸 入值較小的相同問題。 ※ 有時，我們能將有特定輸入集合的問題簡化，變成輸 入值較小的相同問題。 例. gcd(a, b) = gcd(b mod a, a) (when a < b) 重複此法至b mod a = 0，就找到gcd了 Def 1. 藉由把問題簡化到更小輸入的相同問題來解決問題的演算法，稱為遞迴演算法。

Example 1. 求出計算 n!的遞迴演算法, 其中 n為 非負整數. Sol : n! 的遞迴定義: 初始值: 0! =1 遞迴式: n! = n  (n-1)!. 要求出4! 時: 4! = 43!, 3! = 32!, 2! = 21!, 1! = 10!, 0! = 1, 代回得到 1! = 1, 2! = 2, 3! = 6, 4! = 24 Algorithm 1. Procedure factorial(n : nonnegative integer) if n = 0 then factorial(n):=1 else factorial(n):= n  factorial(n-1) ∴

Algorithm 1. Procedure factorial(n : nonnegative integer) if n = 0 then factorial(n):=1 else factorial(n):= n  factorial(n-1) 遞迴呼叫自己 也可改寫為: Algorithm 1. Procedure factorial(n : nonnegative integer) if n = 0 then return(1) else return(n  factorial(n-1))

用Algorithm 1求出4!的過程： factorial(4) = 4  factorial(3) = 4  6 = 24 = 3  2 =6 = 2  factorial(1) = 2  1 =2 = 1  factorial(0) = 1  1=1 Algorithm 1. Procedure factorial(n : nonnegative integer) if n = 0 then factorial(n):=1 else factorial(n):= n  factorial(n-1)

Example 2. 求出計算 an,的遞迴演算法, 其中 a為實數，n為非負整數。 Sol : an的遞迴定義 : 初始值: a0=1 遞迴式: an = a  an-1. Algorithm 2. Procedure power(a : number, n : nonnegative integer) if n = 0 then power(a, n):=1 else power(a, n):= a  power(a, n-1). ∴

Exercise 4.4 補充: 根據演算法2的步驟，以a=2, n=4為輸入， 詳細寫出求出24的值之過程。 Algorithm 2. Procedure power(a : number, n : nonnegative integer) if n = 0 then power(a, n):=1 else power(a, n):= a  power(a, n-1).

Example 4. 寫出求 gcd(a,b) 的遞迴演算法，其中 a<b. Sol : 遞迴式:gcd(a,b) := gcd(b mod a, a) 初始值:gcd(0,b) := b Algorithm 4. procedure gcd(a,b : nonnegative integers with a<b) if a=0 then gcd(a,b) := b else gcd(a,b) := gcd(b mod a, a).

Exercise 4.4 6. 根據演算法4的步驟，求出gcd(8, 13)的值。 Algorithm 4. procedure gcd(a,b : nonnegative integers with a<b) if a=0 then gcd(a,b) := b else gcd(a,b) := gcd(b mod a, a). 29. 設計一個遞迴演算法來找出數列的第n項，其中 a0=1，a1=2，而an= an-1 an-2，n=2, 3, …。

Example 5. Search x in a1, a2,…,an by Linear Search Sol : Alg. 5 (跳過) Example 5. Search x in a1, a2,…,an by Linear Search Sol : 從ai,ai+1,…aj 中找 x Alg. 5 procedure search (i, j, x: integers) if ai = x then location := i else if i = j then location := 0 else search(i+1, j, x) call search(1, n, x)

procedure binary_search (x , i , j: integers) m := (i+j) / 2 (跳過) Example 6. Search x from a1,a2,…,an by binary search (recursive version). search x from ai, ai+1, …, aj Sol : Alg. 5 procedure binary_search (x , i , j: integers) m := (i+j) / 2 if x = am then location := m else if (x < am and i < m) then binary_search(x, i, m-1) else if (x > am and j > m) then binary_search(x, m+1, j) else location := 0 表示左半邊 ai, ai+1, …, am-1 至少還有一個元素 call binary_search(x, 1, n)

Example 1. Give the value of n!, nZ+ (跳過) Example 1. Give the value of n!, nZ+ Sol : Note : n! = n  (n-1)! Alg. 1 (Recursive Procedure) procedure factorial (n: positive integer) if n = 1 then factorial (n) := 1 else factorial (n) := n  factorial (n-1) Alg. (Iterative Procedure) procedure iterative_factorial (n : positive integer) x := 1 for i := 1 to n x := i  x { x = n! }

※ iterative alg. 的計算次數通常比 recursive alg.少 (跳過) ※ iterative alg. 的計算次數通常比 recursive alg.少 ※ Find Fibonacci numbers (Note : f0=0, f1=1, fn=fn-1+fn-2 for n2) Alg. 7 (Recursive Fibonacci) procedure Fibonacci (n : nonnegative integer) if n = 0 then Fibonacci (0) := 0 else if n = 1 then Fibonacci (1) := 1 else Fibonacci (n) := Fibonacci (n-1)+Fibonacci (n-2)

(跳過) Alg.8 (Iterative Fibonacci) procedure iterative_fibonacci (n: nonnegative integer) if n = 0 then y := 0 // y = f0 else begin x := 0 y := 1 // y = f1 for i := 1 to n-1 begin z := x + y x := y y := z end {y is fn } i = 1 i = 2 i = 3 z f2 f3 f4 x f1 y Exercise : 11, 35