TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 1

Aus VoWi
< TU Wien:Algebra und Diskrete Mathematik UE (diverse)‎ | Übungen SS19
Version vom 28. September 2019, 09:57 Uhr von Gittenborg (Diskussion | Beiträge) (use Template:Thema)
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)
Zur Navigation springen Zur Suche springen

Man überprüfe die Gleichung

 1^2 + 2^2 + 3^2 + ... + n^2 = \frac{n(n+1)(2n+1)}{6} \qquad \forall n \in \mathbb{N}

für die ersten fünf natürlichen Zahlen und beweise sodann die Gültigkeit für alle natürlichen Zahlen durch vollständige Induktion.

Hilfreiches

Vollständige Induktion
Vollständige Induktion[Bearbeiten, WP]
  1. Induktionsanfang (IA)
  2. Induktionsschritt (IS): Induktionsvoraussetzung (IV) \Rarr Induktionsbehauptung (IB)

Lösung von samuelp

Gültigkeit für die ersten fünf natürlichen Zahlen

n links rechts
 1  1  \frac{6}{6}
 2  5  \frac{30}{6}
 3  14  \frac{84}{6}
 4  30  \frac{180}{6}
 5  55  \frac{330}{6}

Alle stimmen überein. Der Induktionsanfang n=0 ist damit auch gelöst.

Induktionsschritt n \rightarrow n+1

Induktionshypothese: \sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}

Induktionsbehauptung: \sum_{k=1}^{n+1} k^2 = \frac{(n+1)(n+2)(2n+3)}{6}

Linke Seite:


\begin{align}
\sum_{k=0}^{n+1} k^2 
&= \sum_{k=0}^{n} k^2 + (n+1)^2 \\
&\overset{I.H.}{=} \frac{n(n+1)(2n+1)}{6} + (n+1)^2 \\
&= \frac{(n^2+n)(2n+1)}{6} + \frac{6(n^2+2n+2)}{6} \\
&= \frac{2n^3+3n^2+n}{6} + \frac{6n^2+12n+6}{6} \\
&= \frac{2n^3+9n^2+13n+6}{6}
\end{align}

Rechte Seite:


\begin{align}
\frac{(n+1)(n+2)(2n+3)}{6}
&=\frac{(n^2+3n+2)(2n+3)}{6}\\
&=\frac{2n^3+9n^2+13n+6}{6}\\
\end{align}

Beide Seiten sind gleich somit ist die Induktionsbehauptung wahr.