forked from sandro-felicioni/analysis
/
induktion.tex
executable file
·36 lines (35 loc) · 2.01 KB
/
induktion.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
\section{Vollständige Induktion}\index{Induktion}
Grundlegende Struktur um die Aussage $A(n)$ zu beweisen:
\begin{enumerate}
\item \textbf{Verankerung/Induktionsanfang:} Die Aussage wird für $n = A$ bewiesen.
$A$ ist dabei meistens der erste Wert für die gegebene Eingabemenge.
Der Beweis wird meist durch direktes ausrechnen gemacht.
\item \textbf{Induktionsschritt}
\begin{enumerate}[label*=\arabic*.]
\item \textbf{Annahme/Induktionsvoraussetzung:} Hier schreibt man,
dass man davon ausgeht die Aussage sei gültig für ein bestimmtes $n \in \N$ (damit man sie im Beweis
einsetzen kann). Man kopiert also im Grunde, was man zu beweisen hat mit einigen Zierwörter.
\item \textbf{Induktionsbehauptung:} Hier schreibt man, dass die Aussage auch für (n + 1) gilt.
\item \textbf{Beweis:} Hier beweist man, dass unter der Annahme, dass die Induktionsvoraussetzung gilt, die Induktionsbehauptung folgt. Oder anders gesagt, wir beweisen dass wenn die Aussage für n gilt, dass es dann auch für (n + 1) gelten muss. Dazu wird die Induktionsvoraussetzung verwendet.
\end{enumerate}
\end{enumerate}
Merke: Schritt 2.1 und 2.2 werden oft weggelassen, falls trivial!
\textbf{Beispiel}\\
Es ist zu beweisen, dass für jedes $n \in \N$ folgendes gilt:\\
$1 + 2 + 3 + \ldots + n = \frac{n(n + 1)}{2}$
{\small
\begin{enumerate}
\item \textbf{Verankerung:} Für $n = 1$ gilt: $1 = \frac{1 (1 + 1)}{2} = \frac{2}{2} = 1 \quad \checkmark$
\item \textbf{Induktionsschritt:}
\begin{enumerate}[label*=\arabic*.]
\item \textbf{Ind.voraussetzung:} $1 + 2 + \ldots + n = \frac{n(n+1)}{2}, \; \text{gilt für} \; n$
\item \textbf{Induktionsbehauptung:} Wenn die Aussage für n gilt, dann gilt sie auch für (n + 1).
\item \textbf{Beweis:} Für $n \to n+1$ gilt:
\begin{align*}
\hspace{-0.5cm} 1 + \ldots + n + (n+1) &\overset{\text{Ind.vs.}}{=} \frac{n(n+1)}{2} + (n + 1)\\
&= \frac{n(n+1)}{2} + \frac{2n + 2}{2} = \frac{n^2 + n + 2n + 2}{2} \\
&= \frac{(n + 1)(n + 2)}{2} _\square
\end{align*}
\end{enumerate}
\end{enumerate}
}