離散 part3 - HackMD

--- title: 離散 part3 --- {%hackmd @NTNUCSIE112/S1VbPN1HU %} # Recursion/Mathematical induction 遞迴/數學歸納法 Ch.5 Induction and Recursion Reading assignments: 5.1, 5.2, 5.3 ## Euclidean algorithm 歐基里得演算法（熱身例子） $\text{For } a,b \in \mathbb{N},\text{let }\ a=b\cdot k+r, \text{where }k,r\in \mathbb{N} \cup \{0\}, 0 \leq r\leq b.$Then $\gcd(a,b) = \begin{cases}b,&\text{if }r = 0\\ \gcd(b,r), & \text{otherwise.}\end{cases}$ - Q: Why is it correct? - claim: The common divisor（因數） of a and b are the same as the common divisor of $b$ and $r$ :::spoiler proof - Let $d$ be a common divisor of $a$ and $b$ ; $a = k_1d$ and $b = k_2d$. - $a = bk + r \implies r = (k_1 - kk_2)d \implies d|r$ - Let $d'$ be a common divisor of $b$ and $r$; $b = k_1'd' \text{ and } r = k_2'd'$ - $a = bk + r = (kk_1 + k_2)d' \implies d'|a$. ::: Q: How many steps (#divisions) does Euclidean algorithm take to compute $\gcd( a , b)$? $\begin{aligned} \to &\text{Let #step be }n, \text{ and }r_0 = a, r_1 = b. \\ &\text{w.l.o.g (without lose of generality) assume that } r_0 \geq r_1.\\ &\text{step 1: }r_0 = r_1\cdot k_1 + r_2\\ &\text{step 2: }r_1 = r_2\cdot k_2 + r_3\\ &\text{step 3: }r_2 = r_3\cdot k_3 + r_4\\ &\vdots\\ &\text{step n: }r_{n-1} = r_n\cdot k_n + 0\\ &n = ? \end{aligned}$ $r_1 > r_2$ $r_1\cdot k_1 + r_2 = r_0> 2r_2$ $\vdots$ $r_{n-3}>2\cdot r_{n-1}$ $r_{n-1}>2\cdot r_{n+1}$ step i: $r_{i-1} = r_i \cdot k_i + r_{i+1}$ - Observation 1. the algorithms stops when $r_{i+1} = 0(<1)$ 2. $r_{i-1}> 2r_{i+1}$ $\to$ #steps n is upperbounded by a function $f(a)$( the maximum of a and b), satisfying $f(a)= \begin{cases}0, &\text{if } a \leq 1\\ 2+f(\lfloor\frac{a}{2}\rfloor),&\text{otherwise}\\ \end{cases}$ $\begin{aligned} f(a)&=2+f(\frac{a}{2})\\ &=2+(2+f(\frac{a}{4}))\\ &=2+2+\dots+2 \implies \frac{a}{2^x} \equiv 1 \implies x \approx log_2\ a \end{aligned}$ $\to f(r_0) = 2\cdot\log_2r_0$ ### Mathematical Induction Axiom If $S$ is a set of positive integers such that - 1 $\in S$, and - $\forall n \in \mathbb{N}, n \in S \implies n+1\in S$ then $S = \mathbb{N}$ Note: This is equivalent to the **"well-ordering axiom"**. ### (Weak) Mathematical Induction To prove that a predicate $P(n)$ is true for all positive integer $n$ (at least $x$), we complete two steps: - Basis step: verify that $P(x)$ is true. - Inductive step: verify that "$∀k ∈ N \text{ and } k ≥ x, P(k) ⟹ P(k + 1)$" is true. ### (Strong) Mathematical Induction To prove that a predicate $P(n)$ is true for all integer $n$( at least $x$), we complete two steps: - Basis step: verify that $P(x)$ is true - Inductive step: verify that "$\forall \in \mathbb{N}$ and $k\geq x, P(x) \land P(x+1)\land\cdots\land P(k)$" $\implies P(k+1)$ is true. Note: The condition stated in strong mathematical induction is equivalent to that stated in (weak) mathematical induction. ## Mersenne prime ## Example (不知道是誰的) e.g. Show that every amount of postage of 12 cents or more can be formed using just 4-cent or 5-cent stamps. Proof(is it easy to apply mathematical induction here)  I. basis: $n = 12 \implies 12=4+4+4$ Inductive hypothesis: For $k\in\mathbb{N}, P(k)$ is true Inductive step: Consider $P(k+1)$ using 4-cent $\implies k-3$ using 5-cent $\implies k-4$ ## Fibonacci sequence 費波那契數列 a sequence with the first two terms being 0 and 1, and the nth term is the sum of the previous two terms. $0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...$ Let $f(n)$ be the $n$-th Fibonacci number. We can define it as $f(n) = \begin{cases} 0, &\text{if } n = 0\\ 1, &\text{if } n = 1\\ f(n − 1) + f(n − 2), &\text{otherwise} \end{cases}$ Proposition: Let $f(n)$ be the Fibonacci number. Then $\forall n \geq 3, f(n) > \alpha^{n-2}$, where $\alpha = \frac{1+\sqrt{5}}{2}$ Proof. (by (strong) induction on $n$) 1. basis $f(3)=2 \geq \left(\frac{1+\sqrt{5}}{2}\right)^{3-2}$ 2. I.H. $P(3)\land P(4)\land\cdots\land P(k)$ 3. I.S. Consider $k+1$, $(f(k+1)>\alpha^{k-1})$ $\begin{aligned}f(k+1) &\overset{def}{=} f(k)+f(k-1)\\ &\overset{I.M.}{>}\alpha^{k-2}+\alpha{k-3}\\ &=\alpha^{k-3}(\alpha+1)\end{aligned}$ ### 5.3.2 #### 【Theorem】 Lame's 拉美定理 Let $n$ be the ..... e.g. $\gcd(100, 5012)$ 100 has 3 digits, 5012 has 4 digits, the number of divisions is at most 15. $\begin{aligned} 5012 &= 100 \times 50 + 12\\ 100 &= 12 \times 8 +4\\ 12 &- 4 \times 3 + 0 \end{aligned}$ The actual number of divisions is 3. The theorem provides only an upper bound. :::spoiler Proof ::: (Observation 1) $\forall i\in [n],k_i\geq1.$ It follows that $\begin{aligned} a = &r_0 = r_1k_1 + r_2 &\geq r_1 + r_2\\ b = &r_1 = r_2k_2 + r_3 &\geq r_2 + r_3\\ \vdots\\ &r_{n-3} = r_{n-2}\cdot k_{n-2} + r_{n-1} &\geq r_{n-2} + r_{n-1} \geq 5\\ &r_{n-2} = r_{n-1}\cdot k_{n-1} + r_n &\geq r_{n-1} + r_{n}\\ &r_{n-1} = r_{n}\cdot k_{n} + 0 &\geq r_{n} + 0\\ \end{aligned}$ (Observation 2) $r_n\geq1=f(2),k_n\geq2$, Thus, $\begin{aligned} a=&r_0=r_1\cdot k_1+r_2\geq r_1+r_2\\ b=&r_1=r_2\cdot k_2+r_3\geq r_2+r_3\geq f(n+1)\\ &r_2=r_3\cdot k_3+r_4\geq r_3+r_4\geq f(n)\\ \vdots\\ &r_{n-2}=r_{n-1}\cdot k_{n-1}+r_n\geq r_{n-1}+r_n\geq f(3)+f(2)=f(4)\\ &r_{n-1}=r_n\cdot k_n+0\geq f(1)+f(2)=f(3) \end{aligned}$ ### Example 握手  - n = 1