---
# System prepended metadata

title: Recursion and Mathematical Induction
tags: [Discrete Mathematics, 必修, NTNU, CSIE]

---

---
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)$
<!--  他是差在哪？看不懂 就indutive step不一樣-->
#### 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}$

<!-- -------0------i-------j------n---- -->
```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)
<!-- https://hackmd.io/@NTNUCSIE112/rkyKic8OI -->