Induction

Allgemein

Beweise $A(k)$ für alle $k\in \mathbb{N}$

• Induktionshypothese (IH): $A(k)$
• Induktionsanfang (IA): zeige $A(1)$
• Induktionsschritt (IS): zeige dass $A(k+1)$ gilt, falls $A(k)$ gilt

Example

NOTE

$S_k=1+2+2^2+..+2^{k-1}=2^k-1$ for all $k\in \mathbb{N}$

Proof:

• Induktionsanfang: $s_1=1$
• Induktionsschritt:
  • $k\to k+1$
  • $S_{k+1}=S_k+2^k$
  • $=2^{k-1}+2^k=2^k-1$

Example: Bernoulli Ungleichung

Für alle $x\ge -1$ und $u\in \mathbb{N}$

$$(1+x{)}^n\ge 1+nx$$

IA: n=1: $(1+x)\ge 1+x$ IS: $n\to n+1$

• $(1+x{)}^{n+1}=(1+x{)}^n(1+x)$
• $(1+x{)}^{n+1}\ge (1+nx)(1+x)$
• $=1+x(n+1)+n{x}^2\ge 1+x(n+1)$

Example: Star Suche

Finde einen Star unter n Personen $p_1,\dots p_n$ Definition: $p_s$ ist ein Star wenn alle $p_s$ kennen, und $p_s$ niemand kennt Operation: Frage $p_i$ über $p_j$

Idee 1

Finde Lösung für $n$ basierend auf einer Lösung von $n-1$ Personen

• Schicke einen raus (z.B. $p_n$)
• Finde Star $p_s$ unter $p_1\dots p_{n-1}$
  • Time: $F(n-1)$
• Ist $p_s$ auch Star unter $p_1\dots p_n$
  • Time: $2$
• Ist $p_n$ Star unter $p_1\dots p_n$
  • Time: $2(n-1)$

Time Complexity Analysis (best case)

• $F(n)=F(n-1)+2$
• $F(2)=2$ $⟹F(n)=2(n-1)$

Time Complexity Analysis (worst case)

• $F(n)=F(n-1)+2(n-1)$
• $F(n)=n(n-1)=n^2-1$

Idee 2

Stelle sicher keinen Star rauszuschicken

• Neues Schritt 0: Schicke einen aus: $p_i{\to }^{?}{p}_j$ ja: $p_i$ kein Star nein: $p_j$ kein Star
  • Time: $1$
• Finde Star $p_s$ unter $p_1\dots p_{n-1}$
  • Time: $F(n-1)$
• Ist $p_s$ auch Star unter $p_1\dots p_n$
  • Time: $2$

Time Complexity Analysis (worst case)

• $F(n)=F(n-1)+3$
• $F(n)=3n-4$ deutlich besser