Beweisen durch vollständige Induktion

Question

Aufgabe:

In dieser Aufgabe beschäftigen wir uns mit dem Prinzip der vollständigen Induktion: Es sei \( n_{0} \in \mathbb{N}_{0} \) und für jedes \( n \geq n_{0} \) sei \( \mathcal{A}(n) \) eine Aussage (wie etwa die Richtigkeit einer Gleichung, die von \( n \) abhängt, Teilbarkeitsregeln, etc.). Es soll gezeigt werden, dass \( \mathcal{A}(n) \) für jedes \( n \geq n_{0} \) richtig ist. Dies kann mittels eines Beweises durch vollständige Induktion erreicht werden, indem man wie folgt vorgeht:
(a) Induktionsanfang: Es wird gezeigt, dass \( \mathcal{A}\left(n_{0}\right) \) richtig ist.
(b) Induktionsschluss: Dieser setzt sich zusammen aus:
( \( \alpha \) ) Induktionsvoraussetzung: Es sei \( n \in \mathbb{N}_{0} \) mit \( n \geq n_{0} \) und \( \mathcal{A}(n) \) sei richtig.
\( (\beta) \) Induktionsschritt \( (n \rightarrow n+1): \) Man zeigt, dass aus \( (\alpha) \) mittels logischer Schlüsse (wie etwa Áquivalenzumformungen) und bereits wahr erkannter Aussagen die Richtigkeit von \( \mathcal{A}(n+1) \) abgeleitet werden kann.
Dann ist \( \mathcal{A}(n) \) für jedes \( n \geq n_{0} \) richtig.
Wir demonstrieren das Induktionsprinzip anhand eines Beispiels. Wir zeigen, dass für jedes \( n \in \mathbb{N}_{0} \) gilt:
\(\sum \limits_{k=0}^{n} k=0+1+\ldots+k=\frac{n(n+1)}{2}\)
Induktionsanfang: Für \( n=0 \) gilt
\(\sum \limits_{k=0}^{0} k=0=\frac{0 \cdot 1}{2}\)
und wir sehen, dass die Formel für \( n=0 \) erfüllt ist.
Induktionshypothese: Es sei \( n \in \mathbb{N} \) beliebig. Wir nehmen an, dass obige Formel für dieses \( n \) richtig ist.
Induktionsschritt \( (n \rightarrow n+1): \) Für \( n+1 \) gilt dann
\( \begin{aligned} \sum \limits_{k=0}^{n+1} k &=\sum \limits_{k=0}^{n} k+(n+1) \stackrel{(\mathrm{IH})}{=} \frac{n(n+1)}{2}+(n+1)=\frac{n(n+1)}{2}+\frac{2(n+1)}{2} \\&=\frac{n(n+1)+2(n+1)}{2}=\frac{(n+1)(n+2)}{2}=\frac{(n+1)((n+1)+1)}{2}\end{aligned}\)
Dies entspricht genau der zu zeigenden Formel, wenn wir \( n \) durch \( n+1 \) ersetzen. Nach dem Prinzip der vollständigen Induktion ist die Formel also für jedes \( n \in \mathbb{N} \) gültig.
Man zeige nun mittels vollständiger Induktion:
(a) \( \sum \limits_{k=0}^{n} k^{2}=\frac{n(n+1)(2 n+1)}{6} \) für alle \( n \in \mathbb{N}_{0} \).
(b) \( \prod \limits_{k=2}^{n}\left(1-\frac{1}{k}\right):=\left(1-\frac{1}{2}\right) \cdot\left(1-\frac{1}{3}\right) \cdots\left(1-\frac{1}{n}\right)=\frac{1}{n} \) für \( n \geq 2 \)
(c) Für jedes \( n \geq 2 \) gilt \( n+1<2^{n} \).
(d) \( n^{3}-6 n^{2}+14 n \) ist durch 3 teilbar für alle \( n \in \mathbb{N}_{0} \).

Problem/Ansatz:

Hallo hier mal eine etwas längere Aufgabe.

Comments

Hallo,

sinnvoll gekürzt wäre die Aufgabe ab

"Man zeige nun mittels vollständiger Induktion:"

:-)

Answer 1

\( \sum \limits_{k=0}^{n} k^{2}=\frac{n(n+1)(2 n+1)}{6} \) für alle \( n \in \mathbb{N}_{0} \).

Für n=0 stimmt es : Die Summe enthält nur den Summanden 0 und

rechts ergibt sich auch 0.

Induktionshypothese: Es sei \( n \in \mathbb{N} \) beliebig.und es gelte

\( \sum \limits_{k=0}^{n} k^{2}=\frac{n(n+1)(2 n+1)}{6} \) 

Induktionsschritt:

==> \( \sum \limits_{k=0}^{n+1} k^{2}= \sum \limits_{k=0}^{n} k^{2} + n^2 \)

Hypothese einsetzen :

              \(= \frac{n(n+1)(2 n+1)}{6} + n^2 \)

Durch Umformen (Klammer auflösen etc.) zeigen,

dass dies mit der rechten Seite der Formel für n+1

übereinstimmt, also zeigen, dass für alle n gilt:

  \( \frac{n(n+1)(2 n+1)}{6} + n^2 =  \frac{(n+1)(n+2)(2 n+3)}{6} \)