Recursion and Mathematical Induction

--- tags: NTNU,CSIE,必修,Discrete Mathematics title: Recursion and Mathematical Induction description: breaks: true --- {%hackmd @NTNUCSIE112/S1VbPN1HU %} # Recursion and Mathematical Induction ## Recursion and induction ### Euclidean algorithm > $\forall a, b \in \mathbb{N}$, let $a = bk + r, \ k, r \in \mathbb{N}\cup\{0\}, \ 0 \leq r < b$ Then $\text{gcd}(a,b) = \text{gcd}(b,r)$ **Q**: How many steps does Euclidean algorithm need for computing $\text{gcd}(r_0,r_n)$? - Assume that it needs n steps, $r_0 = r_1k_1 + r_2 \ - \text{step 1}$ $r_1 = r_2k_1 + r_3 \ - \text{step 2}$ $r_2 = r_3k_1 + r_4 \ - \text{step 3}$ $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots$ $r_{n-1} = r_nk_n + r_{n-1}\ -\text{step n}$ 1. 算法於 $r_i\leq 1$ 停 2. $r_i \geq 2r_{i+2}, \ \forall i \geq 0$ > 由觀察**1**、**2**可假設函式$n(x)$為除法次數上限，其中 $n(x) = \begin{cases} 0 & , \text{ if } x \geq 1 \\ 2+n(\lfloor\frac{x}{2}\rfloor ) & , \ \text{otherwise} \end{cases}$ $\begin{aligned} (r_0\not=0)\\ n(r_0) &= 2 +n (\frac{r_0}{2})\\ &=2 + ( 2 + n(\frac{r+0}{2^2}))\\ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots\\ &= (2+2+...+2)+n(1)\\ &\approx 2\log_2{r_0} \end{aligned}\\ e.g.\forall n\in\mathbb{N}, n\geq 4, x\leq n!\\ 2^4=16, 4! = 24\\ 2^5 = 32, 5! = 120\\ 2^6 = 64, 6! = 720$ ([mathematical induction](###mathematical-induction)) ### Mathematical Induction 論證 $\forall n \geq x,${$P(n)$|Predicate} is true axiom : If $S$ is a set of positive integers such that - $1 \in S$ - $\forall n \in \mathbb{N}$, if $n \in S$ then $n+1 \in S$ - then $S = \mathbb{N}$ To prove that predicate $P(n)$ is true for all ($n \in \mathbb{N}$) $n x$, we complete 2 steps: - Basis step: verify that $P(X)$ is true. - Inductive step: $\forall k \geq x, p(k) \Rightarrow P(k+1)$(Inductive hypothesis) If both steps are then by mathematical induction, $P(n)$ is true $\forall n \geq x$. #### e.g. > $1+2+3+...+n = \frac{n(n+1)}{2},\ \forall n\geq 1$ $\text{pf:}$ Let $P(n)$ be the equality to be proved. Basis step: $n=1,\ 1=\frac{1(1+1)}{2}\rightarrow P(1)$ true Inductive step: to prove: $\forall k \geq 1, \ P(k)\rightarrow P(k+1)\\ P(k+1):\ 1+2+...+(k+1)=(1+2+3+...+k)+(k+1)\\ =\frac{k(k+1)}{2}+(k+1)=\frac{(k+1)(k+2)}{2}$ #### e.g. > $\forall n \geq 4,\ 2^n \leq n!$ $\text{pf:}$ We prove by induction on $n$ - Basis step: $2^4 = 16,\ 4! = 24\\ 2^4 < 4!$ - Inductive step: assume for fixed $k \geq 4,\ 2^k < k!$ Consider $2^{k+1}$ $\begin{aligned} 2^{k+1} &= 2 \times 2^k \\ &< 2 \times k! \\ &< (k+1) \times k! \\ &= (k+1)! \end{aligned}$ By mathematical induction, $\rightarrow 2^n < n!, \forall n \geq 4$ #### e.g. > 一對夫妻(男女主人)辦宴會邀請 $n$ 對夫妻(賓客) ($n \geq 1$)，進場前大家互相握手，握完後，男主問其他人握手次數，得到 $2n+1$個不同答案 Q:已知夫妻間不互握，問女主人握幾次？ - 先討論n = 1 的情況 ![](https://i.imgur.com/k2ongo0.jpg =x200) $\rightarrow$女主人握恰一次! - 再討論n = 2 的情況 ![](https://i.imgur.com/k87uIc2.jpg =x200) $\rightarrow$女主人握恰二次! - 再討論n = 3 的情況 - 猜當$n$ 對賓客時女主人握恰為n次 - pf We prove by induction on n - Basic Step: verified! - Inductive Step: - 對$K\geq 1$, $k$對賓客女主握k次 $\Rightarrow (k+1)$對時女主握k+1次$ - 已知 $k$對賓客時握$k$次，考慮再多一對賓客，$m_{k+1}f_{k+1}$ - 令$m_{k+1}$握$0$次 $f_{k+1}$握$2k+2$次 - ~~則握手狀況為符合所求，得證~~ - 問題改成Q:已知夫妻間不互握，問女主人**可能**握幾次？ - $\rightarrow$ **其實未得證，需證明(0, 2k+2)為夫妻** ![](https://i.imgur.com/PhyOOrw.jpg =x200) ![](https://i.imgur.com/CPMb7b3.jpg =x200) ### **(Strong)** Mathematical Induction - The same as the "weak" version except Inductive step: - $\forall k \geq x, P(x) \land P(x+1)\land ... \land P(k) \Rightarrow P(k+1)$  #### E.g. > Every amount of postage of 1 cents or more {can be formed using just 4-cent and 5-cent stamps|P(n)}.  pf. by induction of the postage n - Basic step: - 12 = 4 + 4 + 4 - Inductive step: - $\forall k \geq 12$ - $P(k)\rightarrow P(k+1)$ - using 4, $k+1\rightarrow k-3$ - using 5, $k+1\rightarrow k-4$ - $P(k-3),P(k-4)$ true pf.(modified) Basis: $P(12)\land P(13)\land P(14)\land P(15)\begin{cases} &12=4+4+4\\ &13=4+4+5\\ &14=4+5+5\\ &15=5+5+5\\ \end{cases}$ Inductive step: $\forall k \geq 15$,goal : $P(12)\land ...\land P(k)\rightarrow P(k+1)$ > Give $i,j\ (i,j\in {N} , i < j)$ determine whether the postage of $n$( $n\in \mathbb{N}$ ) cents can be formed by using only $i$-cent and $j$-cent stamps.i $\begin{cases} \text{false,}&\text{ if }n < i\\ \text{ true,}&\text{ if }n = i \text{ or } n = j\\ P(n-i),& \text{ if }\ i < n < j\\ P(n-i)\lor P(n - j ),&\text{ if }\ n >ｊ \end{cases}$  ```c= bool P(int n) { if ( n < i ) return false; else if( n == i || n == j) return true; else return (P(n-i)||P(n-j)); } ```    #### E.g. > Q: How many function calls do you need to compute P(n)? > Let T(n) be the requested number ( to compute P(n) ) > $T(n)=\begin{cases} 1, &\text{ if } n = 1 \text{ or } 2\\ T(n-1)+T(n-2)+2, &o.w. \end{cases}$ #### Fibonacci number $f(n)=\begin{cases} 0,&if(n = 0)\\ 1,&if(n = 1)\\ f(n - 1)+f(n - 2),&if(n \geqslant 2) \end{cases}$ #### Proposition > For $n \geq 3,\ f(n) > \alpha^{n-2},\\\text {where } \alpha = \frac{1+\sqrt{5}}{2}$ > ##### pf.prove by induction on n - basic step ( n = 3 ): $\because f(3)=2, \alpha^1=\frac{1+\sqrt{5}}{2}=1.6...$ $\therefore f(3)>\alpha^1$ - Inductive step ($\forall k\geqslant P(3)\land P(4)\land P(5)\land ...\land P(k)\rightarrow P(k+1)$) $\text{consider } f( k + 1 )$ $\begin{aligned} f(k+1) &= f(k) + f(k-1)\\ &>\alpha^{k-2}+\alpha^{k-3}\\ &=(\alpha +1)\times \alpha^{k-3}\\ &=\alpha^2 \times \alpha^{k-3}\\ &=\alpha^{k-1} \end{aligned}$ $\alpha^{2}=\frac{6+2\sqrt{5}}{4}=\frac{3+\sqrt{5}}{2}$ $\alpha^2=1+\alpha=\frac{3+\sqrt{5}}{2}$ by mathematical induction #### Theorem (Lame) > Let n be the number of divisions needed to compute gcd( a, b) by the Euclidean algorithm. Then n is at most **5 times the number of digits of min{ a, b}**. e.g. gcd( 100, 5012) $\begin{aligned} 5012&=100&\times& 50& +& 12&\\ 100&=12&\times& 8& +& 4&\\ 12& =4&\times& 3& +& 0&\\ \end{aligned}$ $\text{number of digits: a -> 3, b -> 4 --> upper bound: }5 \times 3 = 15$ ##### pf. $\text{Let } a,b\in \mathbb{N} \text{ ,and without loss of generality assume that }a > b.$ $\text{Then the }n\text{ divisions are}$ $\text{(Observation 1)} \forall i \in [n], k_i \geq 1. \text{ It follows that}$ $\begin{aligned} a=&r_0=r_1\cdot k_1+r_2\\ b=&r_1=r_2\cdot k_2+r_3&\geq f_{n+1}\\ &...\\ &r_{n-3}=r_{n-2}\cdot k_{n-2}+r_{n-1} \geq r_{n-2}+r_{n-1} &\geq f_5\\ &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\\ \end{aligned}$ $\text{(Observation 2)}r_n \geq 1 = f_2, k_n \geq 2 \text{(Recall (fibonacci sequnce: 0, 1, 1, 2, 3, ...))}$ $b \geq f_{n+1}> \alpha^{n-1} = (\frac{1+\sqrt{5}}{2})^{n - 1}$ $\to \log_{10}{b}>(n-1)\log_{10}{\alpha} > \frac{n-1}{5}$ $\to n < 5 \log_{10}{b} +1 \leq 5 (\lfloor \log_{10}b \rfloor+1)+1$ Q: Does $f_n$ grow faster than $\alpha^{n-2}$? Is there an "extra formula" for $f_n$? A:Yes! To get the formula, we have to "solve" the recurrence relation. The exact formula is calles a "close form", which is an expression consisting of "element operation" like $+$,$-$,$\times$...,$\div$,$\sqrt{}$ $(f_n = f_{n - 1}+f_{n - 2}, \forall n \geq 2)$ There is no known procedure to solve an arbitrary recurrence relation. #### Linear recurrence relation: A linear recurrence relation of degree k is a recurrnence relation of the form $T(n) = c_1 Y(n-1) - c_2 T(n-2)+ ...+c_k T(n-k)$ where each coeffieicnt $c_i$ is real number and $c_k \neq 0$ We introduce two methods for solving linear recurrence realstions: - Characteristic equation - Generate function ### Characteristic equation (e.g. $t_n = 3t_{n-1}-2t_{n-2}, n = 2, 3, 4, ..., t_0 = a, t_1 = b$) $t_0 = 1, t_1 = 0 \to 1, 0, -2, -6 ,-14...$ $t_0 = 0, t_1 = 1 \to 0,1,3,7,...$ (take $t_0 = 0, t_1 = 1$) (If $r_1$ and $r_2$ are the solutions to the characteristic equation, then $t_n = a_1r_{1}^{n} + a_2r_{2}^{n}$ where $a_1,a_2$, are two constant determined by $t_0$ and $t_1$.) - Steps: 1. let $t_n = r^n, r \in \mathbb{R}$ (to solve) 2. rewrite the recurrence as $r^n = 3r^{n-1} - 2r^{n-2} \rightarrow r^2 - 3r +2 = 0$ (characteristic equation) 3. $r = 2, 1 \rightarrow t_n = a_1 \times 2^n + a_2$ 4. $t_0 = 0 \rightarrow 0 = a_1 + a_2$ 5. $t_1 = 1 \rightarrow 1 = 2a_1 + a_2 \rightarrow a_1 = 1, a_2 = -1 \rightarrow t_n = 2^n - 1$ (0,1,3,7,...) e.g. solve $f_n = f_{n-1} + f_{n-2}, \ f_0 = 0, \ f_1 = 1$ let $f_n = r^n$ $f_n = r^n = r^{n-1} + r^{n-2}$ $\implies r^2 - r - 1 = 0 \implies r = \frac{1 \pm \sqrt{5}}{2}$ $\implies f_n = a_1(\frac{1 + \sqrt{5}}{2})^n + a_2(\frac{1 - \sqrt{5}}{2})^n$ Known that $a_1 + a_2 = 0$ and $a_1(\frac{1 + \sqrt{5}}{2}) + a_2(\frac{1 - \sqrt{5}}{2}) = 1$ $\implies a_1 = \frac{1}{\sqrt{5}}, \ a_2 = -\frac{1}{\sqrt{5}}$ $\therefore f_n = \frac{1}{\sqrt{5}}(\frac{1 + \sqrt{5}}{2})^n - \frac{1}{\sqrt{5}}(\frac{1 - \sqrt{5}}{2})^n$ e.g. $t_n = 3t_{n-1} - 2t_{n-2}$ $t_{n-1} = 1t_{n-1} + 0t_{n-2}$ $\implies \left[\begin{matrix}t_n\\t_{-1}\end{matrix}\right] = \left[\begin{matrix}3 &-2\\1 &0\end{matrix}\right]\left[\begin{matrix}t_{n-1}\\t_{n-2}\end{matrix}\right] = \left[\begin{matrix}3 &-2\\1 &0\end{matrix}\right]^2\left[\begin{matrix}t_{n-2}\\t_{n-3}\end{matrix}\right] = ... = \left[\begin{matrix}3 &-2\\1 &0\end{matrix}\right]^{n-1}\left[\begin{matrix}t_1\\t_0\end{matrix}\right]$ (compute eigenvalue of the matrix) ### Generating function _Define_: Given a sequence $a = a_1, a_2, ... a_n$, the generating function of $a$ is the power series $A(x) = a_0 + a_1x+a_2x^2+\cdots+a_nx^n+\cdots=\Sigma^{\infty}_{i=0}a_ix^i$ (assume that the series converge, i.e. the sum exits) e.g. $1+x+x^2+x^3+\cdots = \frac{1}{1 - x}$ e.g. $a_n = 8\cdot a_{n-1} + 10^n,\ a_0 = 6$ Consider $a_0,a_1, a_2 = 6,58\cdots$ The generating function $A(x)$ of $a$ is $a_0, a_1x, a_2x^2+\cdots +a_nx^n+\cdots$ $\begin{aligned} &A(x)= \sum^{\infty}_{i=0}a_ix^i \\ &= a_0+ \sum_{i=1}^{\infty}(8a_{i-1}+10^i)x^i \\ &= a_0+\sum_{i=1}^{\infty}8a_{i-1}x^i+ \sum_{i=1}^{\infty}10^i x^i \\ &= a_0 + 8x \sum^{\infty}_{i-1}a_ix^{i-1}+ \sum_{i=1}^{\infty}10^i x^i\\ &= 6+8xA(x) + \frac{10x}{1-10x} \end{aligned}$ $\to A(x) = \frac{6-50x}{(1-8x)(1-10x)} = \frac{A}{1-8x}+ \frac{B}{1-10x}$ $(A+B = 6,10A+8B = 50 \to A=1, B=5)$ $A(x)=\frac{1}{1-8x}+ \frac{5}{1-10x}= (1+8x)+(8x)^2 + \cdots + (8x)^n + \cdots ) + 5(1+10x+(10x)^2+\cdots + (10x)^n+\cdots)$ $\to a_n = 8^n +5 \cdot 10^n$ e.g. $f_n = f_{n-1}+ f_{n-2}, a_0 = 0, a_1 = 1$ Let $F(x) = \sum^{\infty}_{i=0}f_ix^i \\ =f_0 + f_1x + \sum_{i=2}^{\infty}f_ix^i\\ =x+ \sum_{i=2}^{\infty}(f_{i-1}+f_{i-2}x^i)\\ =x +\sum_{i = 2}^{\infty}f_{i-1}x^i + \sum^{\infty}_{i=2}f_{i-2}x^i\\ =x + xF(x) + x^2F(x)$ $\to F(x) = \frac{-x}{x^2+x-1}$ ###### [Next Chapter - Counting](https://hackmd.io/@NTNUCSIE112/rkyKic8OI)