151026 Vorlesung

Folgen

$a:\mathbb{N}\to \mathbb{R}$ statt $a(n)$ schreiben wir $a_n$

2. Bildungsvorschriften

1. verbal: Bsp.: $a_n=\text{ n-te Primzahl}$ $a=(a_1,a_2,a_3,\dots )=(2,3,5,7,\dots )$
2. explizit:
   • $a_n=c+n\cdot dn\ge 0c,d\in \mathbb{R}$ arithmetische Folge $a=(a_0,a_1,a_2,\dots )=(c,c+d,c+2d,\dots )$
   • $a_n=b\cdot x^{n}n\ge 0x,b\in \mathbb{R}$ geometrische Folge $a=(b,b\cdot x,b\cdot x^2,\dots )$
3. rekursiv:
   • $\left\{\begin{array}{c}{a}_1=2\text{Anfangsglied}\\ a_n=\frac{1}{a_{n-1}}+\frac{a_{n-1}}{2}n\ge 2\text{Rekursionsformel}\end{array}\right\}$ $a_1=2,a_2=\frac{1}{2}+\frac{2}{3}=\frac{3}{2},a_3=\frac{2}{3}+\frac{3}{4}=\frac{17}{12},\dots$ $a_n\text{xlongrightarrow}n\to \infty \sqrt{2}$ Beweis folgt eventuell später (Übung 1)
   • $\left\{\begin{array}{c}{a}_1=1a_2=1\\ a_n=a_{n-1}+a_{n-2}n\ge 3\end{array}\right\}$ Fibonacci-Folge $a=(1,1,2,3,5,8,\dots )$

2.2 Beweise mit vollständiger Induktion !

2.2.1 Abspaltregel der Aussagenlogik

Sind Aussagen A u. $A⟹B$ (aus A folgt B) wahr, dann ist auch B wahr $(A\wedge B\to B)\to B$ ist Tautologie (immer war)

Merksatz 2.2.1

Aus zwei wahren Aussagen A und $A⟹B$ folgt zwingend, dass auch B wahr ist.

2.2.2 Aussageform / Prädikat

$A(n):{\sum }_{k=1}^{n}k=1+2+3+4+\cdots +n=\frac{n\cdot (n+1)}{2}$ keine Aussage (abhängig von n)

• $A(1):{\sum }_{k=1}^{1}k=1=\frac{1\cdot (1+1)}{2}$ wahre Aussage
• $A(2):{\sum }_{k=1}^{2}k=1+2=3=\frac{2\cdot (2+1)}{2}$ wahre Aussage
• $\forall n\in \mathbb{N}A(n)$ für alle n gilt A(n)

direkter Beweis: $\left\{\begin{array}{c}(\begin{array}{c}1+2+\cdots +n\\ n+n-1+\cdots +1\end{array})=2\cdot {\sum }_{k=1}^n\\ n+1+n+1+\cdots +n+1=n\cdot (n+1)\end{array}\right\}⟹{\sum }_{k=1}^{n}k=\frac{n\cdot (n+1)}{2}$

Warum steht da $2S$?

$S$ wird zweimal hingeschrieben: einmal vorwärts ($1+2+\cdots +n$), einmal rückwärts ($n+(n1)+\cdots +1$). Beide Zeilen stellen denselben Wert $S$ dar, also ist ihre Summe $S+S=2S$ – unabhängig davon, wie man die Zeilen dann spaltenweise addiert.

Merksatz 2.2.2

Eine Aussageform wird erst durch Einsetzen eines konkreten n zu einer echten, wahren oder falschen Aussage.

2.2.3 Beweise durch vollständige Induktion Tiefe 1

$\left(\begin{array}{c}A(1)\\ A(1)⟹A(2)\\ A(2)⟹A(3)\\ \dots \end{array}\right)\equiv \underset{\forall n\in \mathbb{N}:A(n)}{\underbrace{\left(\begin{array}{c}A(1)\\ A(2)\\ A(3)\\ \dots \end{array}\right)}}$ folgt aus Abspaltregel $\underset{\text{Induktionsanfang}}{\underbrace{A(1)\wedge \forall n\in \mathbb{N}}}:\underset{Induktionsschritt}{\underbrace{A(n)⟹A(n+1)}}$

Bsp.:

$\underset{A(n)}{\underbrace{\forall n\in \mathbb{N}:\sum _{k=1}^{n}k=\frac{n(n+1)}{2}}}$

Induktionsanfang: (n=1)

Behauptung: Aussage gilt für n=1 also ${\sum }_{k=1}^{1}k=\frac{1(1+1)}{2}$ Beweis: ${\sum }_{k=1}^{1}k=1=\frac{1(1+1)}{2}$ richtig

Induktionsschritt $\forall n:A(n)⟹A(1+n)$

Voraussetzung: ${\sum }_{k=1}^{n}k=\frac{n(n+1)}{2}A(n)$ Behauptung: ${\sum }_{k=1}^{n+1}k=\frac{(n+1)(n+1+1)}{2}=\frac{(n+1)(n+2)}{2}A(n+1)$ Beweis: ${\sum }_{k=1}^{n+1}k=1+2+\cdots +n+(n+1)={\sum }_{k=1}^{n}k+(n+1)$ Vor. $\frac{n(n+1)}{2}+(n+1)=\frac{n(n+1)+2(n+1)}{2}=\frac{(n+1)(n+2)}{2}$

Merksatz 2.2.3

Induktionsanfang (ein Startfall) plus Induktionsschritt ($A(n)⟹A(n+1)$) beweisen die Aussage für alle n.

2.2.4 Beweis durch vollständige Induktion Tiefe 2

$\underset{A(1)\wedge A(2)\wedge \forall n:(A(n)\wedge A(n+1))=A(n+2)}{\underbrace{\left(\begin{array}{c}A(1)A(2)\\ A(1)\wedge A(2)⟹A(3)\\ A(2)\wedge A(3)⟹A(4)\\ \dots \end{array}\right)}}\equiv \underset{\forall n\in \mathbb{N}:A(n)}{\underbrace{\left(\begin{array}{c}A(1)A(2)\\ A(3)\\ A(4)\\ \dots \end{array}\right)}}$

Beispiel: Sei ($a_n$) die Fibonacci-Folge

also $\left\{\begin{array}{c}{a}_1=1a_2=1\\ a_{n+2}=a_{n+1}+an\ge 1\end{array}\right\}$ Dann gilt für alle $n\in \mathbb{N}{a}_n\ge {\sqrt{2}}^{n-2}$ $\forall n\in \mathbb{N}:a_n\ge {\sqrt{2}}^{n-2}$

Beweis mit v. Induktion

Induktionsanfang: Behauptung: A(1) und A(2) stimmen d.h. $a_1\ge {\sqrt{2}}^{1-2},a_2\ge {\sqrt{2}}^{2-2}$ Beweis: $a_1=1\ge \frac{1}{\sqrt{2}}={\sqrt{2}}^{-1}={\sqrt{2}}^{1-2},a_2=1\ge 1={\sqrt{2}}^0={\sqrt{2}}^{2-2}$

Induktionsschritt: $A(n)\wedge A(n+1)⟹A(n+2)$ Voraussetzung: $a_n\ge {\sqrt{2}}^{n-2},a_{n+1}\ge {\sqrt{2}}^{n+1-2}={\sqrt{2}}^{n-1}$ Behauptung: $a_{n+2}\ge {\sqrt{2}}^{n+2-2}={\sqrt{2}}^n$ Beweis: \begin{align} a_{n+2} &= a_{n+1}+a_{n} \quad\text{Rekursionsformel} \\ &\geq \sqrt{2}^{n-1}+\sqrt{2}^{n-2} = \sqrt{2}\cdot\sqrt{2}^{n-2}+\sqrt{2}^{n-2} \\ &= \sqrt{2}^{n-2}\cdot(\sqrt{2}+1) \\ &> \sqrt{2}^{n-2}\cdot 2 = \sqrt{2}^{n-2}\cdot\sqrt{2}^{2} \\ &= \sqrt{2}^{n} \end{align} Insgesamt $a_{n+2}>{\sqrt{2}}^n$

Merksatz 2.2.4

Wenn die Rekursion zwei Vorgänger braucht, braucht der Beweis auch zwei Startfälle und zwei Voraussetzungen im Induktionsschritt.

2.2.5 Allgemeine vollständige Induktion

$\underbrace{\forall n:A(n)}=\underbrace{A(1)\wedge \forall n\in \mathbb{N}:(A(1)\wedge A(2)\wedge \cdots \wedge A(n))⟹A(n+1)}$ Aufpassen ab welchen n der Induktionsschritt funktioniert Typische Anwendung von Induktion Summenformel ${\sum }_{k=1}^n{k}^2=1^2+2^2+3^2+\cdots +n^2=\frac{n\cdot (n+1)(2n+1)}{6}$

n-te Ableitung $f(x)=e^{2x}$ $f^{\prime }(x)=2x\cdot e^{2x}$ $f^{\prime \prime }(x)=2\cdot 2\cdot e^{2x}=4\cdot e^{2x}$ $f^{\prime \prime \prime }(x)=4\cdot 2\cdot e^{2x}=8\cdot e^{2x}$ $f^n(x)=2^n\cdot e^{2x}$ für alle n

Induktionsanfang für n=0 Behauptung: $f^0(x)=e^{2x}\cdot 2^0$ Beweis: $f^0(x)=e^{2x}=2^0\cdot e^{2x}$

Induktionsschritt: Voraussetzung: $f^n(x)=2^n\cdot e^{2x}$ Behauptung: $f^{n+1}(x)=2^{n+1}\cdot e^{2x}$ Beweis: $f^{n+1}(x)=(f^n(x){)}^{\prime }$ $(2^n\cdot e^{2x}{)}^{\prime }=2^n\cdot (e^{2x}{)}^{\prime }=2^n\cdot 2\cdot e^{2x}=2^{n+1}\cdot e^{2x}$

Merksatz 2.2.5

Im Induktionsschritt darf man sich auf alle vorherigen Fälle $A(1),\dots ,A(n)$ stützen, nicht nur auf den unmittelbaren Vorgänger.