Discrete Math

notes from Kenneth H. Rosen's Discrete Mathematics and Its Applications, 7th ed. miscellaneous topics in discrete mathematics.

• induction and recursion

• induction

First used by Maurolico in 16th century to prove the sum of first n odd positive integers equals $n^{2}$ $(TeX formula: n^2)$ . De Morgan was the first to formalize it in proofs in 1838, and coined the term "mathematical induction".

despite its name, mathematical induction is not an induction. it's a completely deductive argument, although it might seem inductive (because an infinite number of cases are proven automatically).

Basis step: prove that conjecture holds true for first case
Inductive step: prove that if assumed true for an arbitrary case, then the next case must also be true.

In combination, both facts imply that all cases are true. The truth at the basis step "trickles down" to every case by virtue of also proving step 2.

$P (1) \land$ $(TeX formula: P(1) \; ∧ )$

$\frac{\forall k (P (k) ⟹ P (k + 1))}{\forall k P (k)}$ $(TeX formula: \frac{∀k \; (P(k) \implies P(k+1))}{∀k \; P(k)} )$

assumes well-ordering of set
doesn't give new formulas or conjectures, only proves them
no insight as to why theorem is true

• 1+2+3+...

triangular numbers: $n \in ℕ; \forall n (1 + 2 + \dots + n = \frac{n (n + 1)}{2})$ $(TeX formula: n ∈ \mathbb{N} ; ∀n \left( 1+2+ \ldots + n = \frac{n(n+1)}{2} \right))$

basis step: $1 = \frac{1 (1 + 1)}{2} = 1$ $(TeX formula: 1=\frac{1(1+1)}{2}=1)$

inductive step:

$\begin{aligned} \ 1+\ldots+k = \frac{k(k+1)}{2} \implies 1+\ldots+k+(k+1) = \frac{(k+1)((k+1)+1)}{2} = \frac{(k+1)(k+2)}{2} \ \underbrace{\frac{k(k+1)}{2}}_{1+\ldots+k}+(k+1) = \frac{(k+1)(k+2)}{2} \ \frac{k(k+1)+2(k+1)}{2} = \frac{k^{2}+k+2 k+2}{2} = \frac{k^{2}+3 k+2}{2} = \frac{(k+1)(k+2)}{2} \end{aligned}$ $(TeX formula: \begin{aligned} \ 1+\ldots+k = \frac{k(k+1)}{2} \implies 1+\ldots+k+(k+1) = \frac{(k+1)((k+1)+1)}{2} = \frac{(k+1)(k+2)}{2} \\ \underbrace{\frac{k(k+1)}{2}}_{1+\ldots+k}+(k+1) = \frac{(k+1)(k+2)}{2} \\ \frac{k(k+1)+2(k+1)}{2} = \frac{k^{2}+k+2 k+2}{2} = \frac{k^{2}+3 k+2}{2} = \frac{(k+1)(k+2)}{2} \end{aligned} )$

alternative algebraic proof by child Gauss:

$1+2+\ldots+(n-1)+n=\underbrace{(n+1)+\ldots+(n+1)}_{n/2 \text { times }}=\frac{n}{2}(n+1)$ $(TeX formula: 1+2+\ldots+(n-1)+n=\underbrace{(n+1)+\ldots+(n+1)}_{n/2 \text { times }}=\frac{n}{2}(n+1) )$

• 1+3+5+...

conjecture: $\sum_{i = 0}^{n} 2 i + 1 = [1, 4, 9, 16, 25, \dots] = [1^{2}, 2^{2}, 3^{2}, 4^{2}, 5^{2}, \dots] = n^{2}$ $(TeX formula: ∑_{i=0}^n 2 i+1 = [1,4,9,16,25, \ldots] = [1^{2}, 2^{2}, 3^{2}, 4^{2}, 5^{2}, \ldots] = n^{2})$

basis step: $1 = 1^{2}$ $(TeX formula: 1=1^{2})$

inductive step:

$\begin{aligned} \ 1+3+5+\ldots+(2k-1) = k^2 \implies 1+3+\ldots+(2k-1)+(2k+1)=(k+1)^2 \ \underbrace{1+3+5+\ldots+(2k-1)}_{k^2} + (2k+1) = (k+1)^2 \ k^2 + (2k+1) = (k+1)^2 = k^2 + 2k + 1 \end{aligned}$ $(TeX formula: \begin{aligned} \ 1+3+5+\ldots+(2k-1) = k^2 \implies 1+3+\ldots+(2k-1)+(2k+1)=(k+1)^2 \\ \underbrace{1+3+5+\ldots+(2k-1)}_{k^2} + (2k+1) = (k+1)^2 \\ k^2 + (2k+1) = (k+1)^2 = k^2 + 2k + 1 \end{aligned} )$

• 1+2+4+8+...

¿ $1 + 2 + 2^{2} + 2^{3} + \dots + 2^{n} = 2^{n + 1} - 1$ $(TeX formula: 1+2+2^2+2^3+\ldots+2^n = 2^{n+1} - 1)$ ?, $\forall n (n \in ℕ)$ $(TeX formula: ∀n (n ∈ \mathbb{N}))$

basis step: $P (0) = 0^{2} = 2^{0 + 1} - 1 = 1$ $(TeX formula: P(0) = 0^2 = 2^{0+1}-1 = 1)$

inductive step:

$\begin{aligned} \ 2^0 + 2^1 + \ldots + 2^k = 2^{k+1}-1 \implies 2^0 + 2^1 + \ldots + 2^k + 2^(k+1) = 2^{k+2}-1 \ \underbrace{2^0 + 2^1 + \ldots + 2^k}_{2^{k+1}-1} + 2^(k+1) = 2^{k+2}-1 \ (2^{k+1}-1) + 2^(k+1) = 2^{k+2}-1 \ 2(2^{k+1}) - 1 = 2^{k+2} - 1 \ 2^{k+2} - 1 = 2^{k+2} - 1 \end{aligned}$ $(TeX formula: \begin{aligned} \ 2^0 + 2^1 + \ldots + 2^k = 2^{k+1}-1 \implies 2^0 + 2^1 + \ldots + 2^k + 2^(k+1) = 2^{k+2}-1 \\ \underbrace{2^0 + 2^1 + \ldots + 2^k}_{2^{k+1}-1} + 2^(k+1) = 2^{k+2}-1 \\ (2^{k+1}-1) + 2^(k+1) = 2^{k+2}-1 \\ 2(2^{k+1}) - 1 = 2^{k+2} - 1 \\ 2^{k+2} - 1 = 2^{k+2} - 1 \end{aligned} )$

• general geometric series

$∑_{j=0}^{n} a r^{j} = a + ar +ar^{2} + \ldots + ar^{n} = \frac{ar^{n+1}-a}{r-1}; \; r ≠ 1$ $(TeX formula: ∑_{j=0}^{n} a r^{j} = a + ar +ar^{2} + \ldots + ar^{n} = \frac{ar^{n+1}-a}{r-1}; \; r ≠ 1 )$

basis step:

$\begin{aligned} \ P(0): ∑_{j=0}^{0} a r^{j}=a r^{0}=\frac{a r^{0+1}-a}{r-1} \ a = \frac{a r^{1}-a}{r-1} = \frac{a(r-1)}{(r-1)} = a \ \end{aligned}$ $(TeX formula: \begin{aligned} \ P(0): ∑_{j=0}^{0} a r^{j}=a r^{0}=\frac{a r^{0+1}-a}{r-1} \\ a = \frac{a r^{1}-a}{r-1} = \frac{a(r-1)}{(r-1)} = a \\ \end{aligned} )$

inductive step:

$\begin{aligned} \ P(1): ar^{0} + ar^{2}+ \ldots + ar^{k} = \frac{a r^{k+1}-a}{r-1} \ \implies \underbrace{ar^{0} + ar^{1} + \ldots + ar^{k}}_{\frac{ar^{k+1}-a}{r-1}} + ar^{k+1} = \frac{ar^{k+2}-a}{r-1} \ \frac{ar^{k+1}-a}{r-1} + ar^{k+1} = \frac{ar^{k+2}-a}{r-1} \ ar^{k+1}-a + (r-1)(ar^{k+1}) = ar^{k+2} - a \ ar^{k+1} - a + ar^{k+2} - ar^{k+1} = ar^{k+2} - a \ ar^{k+2}-a = ar^{k+2}-a \end{aligned}$ $(TeX formula: \begin{aligned} \ P(1): ar^{0} + ar^{2}+ \ldots + ar^{k} = \frac{a r^{k+1}-a}{r-1} \\ \implies \underbrace{ar^{0} + ar^{1} + \ldots + ar^{k}}_{\frac{ar^{k+1}-a}{r-1}} + ar^{k+1} = \frac{ar^{k+2}-a}{r-1} \\ \frac{ar^{k+1}-a}{r-1} + ar^{k+1} = \frac{ar^{k+2}-a}{r-1} \\ ar^{k+1}-a + (r-1)(ar^{k+1}) = ar^{k+2} - a \\ ar^{k+1} - a + ar^{k+2} - ar^{k+1} = ar^{k+2} - a \\ ar^{k+2}-a = ar^{k+2}-a \end{aligned} )$