1 of 35

Discrete Mathematics

Chapter 4 �歸納(Induction)與遞迴(Recursion)

大葉大學資訊工程系黃鈴玲

2 of 35

4.1 數學歸納法

例：爬「無限長」的梯子

Ch4-2

已知：�1. 我們能到達梯子的第一階。�2. 假設能到達梯子的某一階，就必能到達梯子的下一階。

問：我們是否能到達這個梯子的每一階？

3 of 35

Ch4-3

4 of 35

注意 : 數學歸納法只能用來證明某個公式的正確性，不能用來� 找出公式.

Ch4-4

P(n) : 一個命題式函數 (例如： n ≤ 2ⁿ)

使用數學歸納法來證明 “P(n) 對所有正整數n皆為真”� 包含以下兩個步驟:

1. 基礎步驟(Basis): � 證明P(1)為真

(即：n代入1時公式成立)

(若 n 從 0 開始則證 P(0)為真，要證明式子在n最小時會成立)

2. 歸納步驟(Inductive) :� 證明當k為任意正整數時，若P(k)成立則P(k+1)也成立

(即：假設n代入k時公式成立，� 利用此假設，證明假設n代入k+1時公式成立)

5 of 35

Example 1 證明當n為正整數時， .

Proof.

(Basis) n=1時：成立

(Inductive) 假設n=k時上式成立，

即：

當n=k+1時，

左式= 1+2+…+k+(k+1)

=

= = 右式，故由歸納法得證

Ch4-5

6 of 35

Example 2. 使用歸納法證明首n個正奇數的和是n².

注意：其實不用歸納法也可以得証：

Pf :�

Basis : n=1時： 1 = 1² 成立�

Inductive : 假設n=k時上式成立，即:

1+3+5+…+(2k−1) = k²

當n=k+1時，左式= 1+3+5+…+(2k−1)+(2k+1)

= k²+ 2k+1 = (k+1)²=右式

故根據數學歸納法得證。

Ch4-6

7 of 35

Example 5. 利用數學歸納法證明：�“對所有正整數n，不等式 n < 2ⁿ 都成立”。

pf :

Basis: n=1時，1 < 2¹成立.

Inductive :

假設n=k 時上式成立，即 k < 2^k.

當 n=k+1時 :

左式= k + 1

< 2^k+ 1

≤ 2^k^{+ 1} =右式

∴ k + 1 < 2^k^{+ 1} 也成立

故根據數學歸納法得證。

Ch4-7

8 of 35

Exercise 4.1

7. 證明當n為 ≥0 的整數時，

Ch4-8

3. 證明當n為任意正整數時，

9 of 35

Ch4-9

Example 7. The harmonic numbers H_k, k =1,2,3,…, are

defined by . Use MI to show that

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) :

whenever n is a nonnegative integer.

(跳過)

10 of 35

Ch4-10

∴P(k+1) is true.

By MI, P(n) is true for all n∈Z⁺.

Exercise : 7, 13

(跳過)

11 of 35

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.

Ch4-11

(跳過)

12 of 35

Ch4-12

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: 此題無法僅用普通的歸納法證明

(跳過)

13 of 35

Ch4-13

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.

Exercise : 7

(k−3 ≥ 12)

(跳過)

14 of 35

4.3 遞迴定義.

Def. 使用一個物件本身來定義它自己的過程稱為recursion(遞迴).

例: 定義一個無窮數列 1, 2, 4, 8, 16, 32, 64, …時

(1) 使用明確的公式，可寫成:

a_n=2ⁿ, n=0,1,2,…

(2) 使用遞迴的形式，可寫成:

初始值： a₀=1,

遞迴式： a_n₊₁=2a_n, n=0, 1, 2, …

Ch4-14

15 of 35

Ch4-15

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

16 of 35

Example 2. 寫出階乘函數 F(n) = n! 的遞迴定義。

Sol :

初始值 : F(0) = 1

遞迴式 : 因 F(n+1) = (n+1)!, F(n) =n! � 故 F(n+1) = F(n) ⋅ (n+1)

Ch4-16

Def1, Example 5. 費式數(Fibonacci numbers) f₀, f₁, f₂, …

定義如下: 初始值： f₀ = 0, f₁ = 1,

遞迴式： f_n = f_n₋₁ + f_n₋₂, for n = 2,3,4,…

What is f₅ ?

Sol :

f₂ = f₁ + f₀ =1

f₃ = f₂ + f₁ =2

f₄ = f₃ + f₂ =3

f₅ = f₄ + f₃ =5

17 of 35

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)²+ f(n) + 1

�

Ch4-17

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. 找出序列{a_n} (n = 1, 2, 3, …) 的遞迴定義，若� (a) a_n = 4n − 2 � (c) a_n = n (n − 1)

18 of 35

Example 6. Show that f_n > α ⁿ⁻² , where

Ch4-18

Pf: ( By Strong MI )

Let P(n) be the statement f_n>α ⁿ⁻² .

Basis: f₃ = 2 > α

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.

f_n_{+1 =}f_n + f_n₋₁ > α ⁿ⁻² + α ⁿ⁻³

= α ⁿ⁻³(α +1)

∵ α +1= α ²

∴ f_n₊₁ > α ⁿ⁻³⋅ α ² = α ⁿ⁻¹

We get that P(n+1) is true.

By Strong MI , P(n) is true for all n ≥ 3

(跳過)

19 of 35

※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

Ch4-19

S = A

(跳過)

20 of 35

Definition 2. The set of strings over an alphabet ∑ � is denoted by ∑*. The empty string is denoted � by λ, λ ∈∑, and wx∈∑* whenever w∈∑* and x∈∑.�eg. ∑ = { a, b, c }�� ∑* = { λ, a , b , c , aa , ab , ac , ba , bb , bc, …� abcabccba, …}

Example 9. Give a recursive definition of l(w),� the length of the string w∈∑*

Sol :

initial value : l(λ)=0

recursive def : l(wx)=l(w)+1 if w∈∑*, x∈∑.

Ch4-20

λa

λb

λc

(跳過)

21 of 35

Exercise 13, 48, 49

Exercise 39. When does a string belong to the set A of bit strings defined recursively by

λ∈A

0x1∈A if x∈A.

Sol :

A={λ, 01 , 0011, 000111, …}

∴當bit string α = 000…011…1 時

α∈A

Ch4-21

n個

0λ1

(跳過)

22 of 35

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.

Ch4-22

(跳過)

23 of 35

4.4 遞迴演算法

※ 有時，我們能將有特定輸入集合的問題簡化，變成輸 � 入值較小的相同問題。

例. gcd(a, b) = gcd(b mod a, a) (when a < b)� 重複此法至b mod a = 0，就找到gcd了

Def 1. 藉由把問題簡化到更小輸入的相同問題來解決問題的演算法，稱為遞迴演算法。

Ch4-23

24 of 35

Example 1. 求出計算 n!的遞迴演算法, 其中 n為� 非負整數.

Ch4-24

Sol : n! 的遞迴定義:

初始值: 0! =1

遞迴式: n! = n ⋅ (n−1)!.

Algorithm 1.

Procedure factorial(n : nonnegative integer)

if n = 0 then factorial(n):=1

else factorial(n):= n × factorial(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

25 of 35

Ch4-25

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))

遞迴呼叫自己

也可改寫為:

26 of 35

用Algorithm 1求出4!的過程：

Ch4-26

Algorithm 1.

Procedure factorial(n : nonnegative integer)

if n = 0 then factorial(n):=1

else factorial(n):= n × factorial(n−1)

factorial(4) = 4 × factorial(3)

= 3 × factorial(2)

= 2 × factorial(1)

= 1 × factorial(0) = 1 × 1=1

= 2 × 1 =2

= 3 × 2 =6

= 4 × 6 = 24

27 of 35

Example 2. 求出計算 aⁿ,的遞迴演算法, 其中 a為實數，n為非負整數。

Ch4-27

Sol :

aⁿ的遞迴定義 :

初始值: a⁰=1

遞迴式: aⁿ = a ⋅ aⁿ⁻¹.

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).

∴

28 of 35

Exercise 4.4

補充: 根據演算法2的步驟，以a=2, n=4為輸入， � 詳細寫出求出2⁴的值之過程。

Ch4-28

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).

29 of 35

Example 4. 寫出求 gcd(a,b) 的遞迴演算法，其中 a<b.

Sol :

Ch4-29

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).

遞迴式:gcd(a,b) := gcd(b mod a, a)

初始值:gcd(0,b) := b

30 of 35

Exercise 4.4

6. 根據演算法4的步驟，求出gcd(8, 13)的值。

Ch4-30

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項，其中 � a₀=1，a₁=2，而a_n= a_n₋₁× a_n₋₂，n=2, 3, …。

31 of 35

Ch4-31

Example 5. Search x in a₁, a₂,…,a_n by Linear Search

Sol :

Alg. 5

procedure search (i, j, x: integers)

if a_i= x then location := i

else if i = j then location := 0

else search(i+1, j, x)

從a_i,a_i₊₁,…a_j 中找 x

call

search(1, n, x)

(跳過)

32 of 35

Example 6. Search x from a₁,a₂,…,a_n by binary search (recursive version).

Sol :

Ch4-32

Alg. 5

procedure binary_search (x , i , j: integers)

m := ⎣(i+j) / 2⎦

if x = a_m then location := m

else if (x < a_m and i < m) then

binary_search(x, i, m−1)

else if (x > a_m and j > m) then

binary_search(x, m+1, j)

else location := 0

call binary_search(x, 1, n)

search x from a_i, a_i₊₁, …, a_j

表示左半邊� a_i, a_i₊₁, …, a_m₋₁

至少還有一個元素

(跳過)

33 of 35

Example 1. Give the value of n!, n∈Z⁺

Ch4-33

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! }

(跳過)

34 of 35

※ iterative alg. 的計算次數通常比 recursive alg.少

※ Find Fibonacci numbers

(Note : f₀=0, f₁=1, f_n=f_n₋₁+f_n₋₂ for n≥2)

Ch4-34

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)

(跳過)

35 of 35

Ch4-35

Alg.8 (Iterative Fibonacci)

procedure iterative_fibonacci (n: nonnegative integer)

if n = 0 then y := 0 // y = f₀

else begin

x := 0

y := 1 // y = f₁

for i := 1 to n−1

begin

z := x + y

x := y

y := z

end

{y is f_n }

Exercise : 11, 35

	i = 1	i = 2	i = 3
z	f₂	f₃	f₄
x	f₁	f₂	f₃
y	f₂	f₃	f₄

(跳過)