§3–1 Recurrence Relations
▪Definition & Example
▪The Fibonacci sequence
▪Modeling with Recurrence Relations
§3–2 Closed-Form Solutions and Induction
▪Guessing a Closed-Form Solution 猜
▪Polynomial Sequences: Using Differences
▪Inductively Verifying a solution 數學歸納法
§3–3 Recursive Definitions
▪Definition & Ex.
▪Writing Recursive Definition
▪Recursive Geometry
//▪Recursive Jokes
§3–4 Proof by Induction
▪The Principle
▪Ex.
▪Strong Induction
▪Structural induction
§3–5 Recursive Data Structures
▪Lists
▪Efficiency
▪Binary Search Trees Revisited
========================================
§3–1 Recurrence Relations
Evaluation：
TopDown evaluation
BottomUp evaluation
=======================================
§3–2 Closed-Form Solutions and Induction
▪Guessing a Closed-Form Solution
▪Polynomial Sequences: Using Differences
▪Inductively Verifying a solution
=======================================
§3–3 Recursive Definitions
▪Definition & Ex.
▪Writing Recursive Definition
▪Recursive Geometry
//▪Recursive Jokes
=======================================
§3–4 Proof by Induction
▪The Principle of Induction
▪Ex.
▪Strong Induction
Example — — — — — —
強數學歸納法(The Principle of Strong Mathematical induction)
對一含有自然數n之命題，若我們能證明：
1.n=n0時，命題成立。
2.假設n0<=n<=K命題成立時，n=k+1命題亦成立。
則在n>=n0時，此命題皆可成立。
例：
我們欲證明大於或等於2的正整數為質數或質數的乘積
1.當n=2時，2為質數，故命題成立。
2.假設2<=n<=k時，命題成立。
考慮整數k+1的情況，若k+1為質數，命題成立。
或k+1非質數，則k+1可分解為p,q，其中p<=k，且q<=k。
根據假設，p及q必為質數或質數之乘積，故k+1亦為質數的乘積。
綜上所述，k+1為質數或質數之乘積。
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
▪Structural induction
=======================================
§3–5 Recursive Data Structures
▪Lists
▪Efficiency
