Vollständige Induktion – Erklärung an der Gauß'schen Summenformel

Vollständige Induktion – Erklärung an der Gauß'schen Summenformel Übung

• Beschreibe, was du in dem jeweiligen Schritt der vollständigen Induktion tust.

  Tipps

  Im ersten Schritt der vollständigen Induktion zeigst du, dass die zu beweisende Aussage für ein $n\in\mathbb{N}$ gilt.

  Wenn du dann noch gezeigt hast, dass die Aussage für ein $n\in\mathbb{N}$ und deren Nachfolger gilt, kannst du bestätigen, dass die zu beweisende Aussage für alle $n\in\mathbb{N}$ gilt.

  Lösung

  Aussagen über natürliche Zahlen wie die Gauß’sche Summenformel können wir mit der vollständigen Induktion beweisen. Dabei gehen wir immer nach folgendem Muster vor:

  1. Induktionsanfang
  Wir zeigen für ein $n\in\mathbb{N}$, dass die zu beweisende Aussage erfüllt ist. In der Regel nehmen wir hier die erste natürliche Zahl, nämlich die $1$.

  2. Induktionsannahme
  Wir nehmen an, dass die Aussage für eine natürliche Zahl $n$ stimmt.

  3. Induktionsschritt
  Zu beweisen ist: Wenn die Aussage $A(n)$ gilt, dann muss auch die Aussage $A(n+1)$ gelten. Es muss also die zu beweisende Aussage ebenfalls für den Nachfolger von $n$ gelten.

  4. Induktionsschluss
  Da wir im Induktionsanfang gezeigt haben, dass die Aussage für die erste Zahl stimmt, und wir im Induktionsschritt bewiesen haben, dass die Aussage auch für die darauffolgende Zahl stimmt, muss sie folglich für alle natürlichen Zahlen gelten.

  Und damit ist unser Beweis fertig!

• Gib den Beweis mittels vollständiger Induktion an.

  Tipps

  Zeige zunächst, dass die Aussage für die erste natürliche Zahl erfüllt ist.

  Im Induktionsschritt musst du beweisen, dass die Aussage auch für die auf $n$ folgende Zahl gilt. Der Nachfolger einer natürlichen Zahl $n$ ist die natürliche Zahl $n+1$.

  Lösung

  Zu beweisen ist die Gauß’sche Summenformel $\sum\limits_{k=1}^nk=\frac{n(n+1)}{2}$ für alle $n\in\mathbb{N}$ mittels vollständiger Induktion.

  1. Induktionsanfang

  Für $n=1$ gilt:
  $A(1)$: $\sum\limits_{k=1}^1k=1=\frac{1\cdot (1+1)}{2}$
  Dies ist eine wahre Aussage.

  2. Induktionsannahme

  Es gelte $A(n)$ für ein $n\in\mathbb{N}$.

  3. Induktionsschritt

  Zu zeigen:
  Gilt $A(n)$ für ein $n\in\mathbb{N}$, dann gilt auch $A(n+1)$ mit $\sum\limits_{k=1}^{n+1}k=\frac{(n+1)(n+2)}{2}$.

  Wir betrachten zunächst die linke Seite der Aussage $A(n+1)$:
  $\sum\limits_{k=1}^{n+1}k=\sum\limits_{k=1}^{n}k+(n+1)\overset{\text{Induktionsannahme}}{=}\frac{n(n+1)}{2}+(n+1)=\frac{n(n+1)+2(n+1)}{2}=\frac{(n+1)(n+2)}{2}$

  Wir nutzen von oben die Induktionsannahme mit $\sum\limits_{k=1}^nk=\frac{n\cdot (n+1)}{2}$.
  Der dadurch erhaltene Bruchterm entspricht der rechten Seite der zu beweisenden Aussage $A(n+1)$.

  Und damit ist dieser Beweis fertig. Man sagt dann „quod erat demonstrandum“, also „was zu beweisen war“.

  4. Induktionsschluss

  Da die Aussage $A(n)$ für ein $n\in\mathbb{N}$ sowie für die darauffolgende Zahl stimmt, muss sie für alle $n\in\mathbb{N}$ gelten.

• Ermittle, welche der Aussagen $A(n)$ mit $n\in\mathbb{N}$ im Induktionsanfang eine wahre Aussage liefern.

  Tipps

  Im Induktionsanfang überprüfst du, ob die Aussage für die erste natürliche Zahl $n$ erfüllt ist.

  Schaue dir folgendes Beispiel an:

  $A(n)$: $\sum\limits_{k=1}^{n}(2k-1)^2=\frac{n\cdot (2n-1)\cdot (2n+1)}{3}$

  Induktionsanfang: $A(1)$

  • linke Seite: $\sum\limits_{k=1}^{1}(2k-1)^2=(2\cdot -1)^2=1^2=1$

  • rechte Seite: $\frac{1\cdot (2\cdot 1-1)\cdot (2\cdot 1+1)}{3}=\frac{1\cdot 1\cdot 3}{3}=1$

  Somit liefert der Induktionsanfang eine wahre Aussage.

  Lösung

  Im Induktionsanfang überprüfen wir, ob die Aussage für die erste natürliche Zahl $n$ erfüllt ist. Diese ist in allen vier Beispielen $n=1$. Wir setzen also $n=1$ in alle vier Aussagen ein und vergleichen die linke und rechte Seite der Aussage.

  Aussage 1

  $A_1(n)$: $\sum\limits_{k=1}^{n}(2k-1)=n^2$

  Induktionsanfang: $n=1$

  • linke Seite: $\sum\limits_{k=1}^{1}(2\cdot k-1)=1$

  • rechte Seite: $1^2=1$

  Somit liefert der Induktionsanfang eine wahre Aussage.

  Aussage 2

  $A_1(n)$: $\sum\limits_{k=1}^{n}\frac{1}{(3k-2)(3k+1)}=\frac n{3n+1}$

  Induktionsanfang: $n=1$

  • linke Seite: $\sum\limits_{k=1}^{1}\frac{1}{(3k-2)(3k+1)}=\frac{1}{(3\cdot 1-2)(3\cdot 1+1)}=\frac 1{1\cdot 4}=\frac 14$

  • rechte Seite: $\frac 1{3\cdot 1+1}=\frac 14$

  Somit liefert der Induktionsanfang eine wahre Aussage.

  Aussage 3

  $3^{2n+4} − 2^{n−1}$ ist durch $5$ teilbar.

  Induktionsanfang: $n=1$

  $3^{2\cdot 1+4} − 2^{1−1}=3^6-2^0=729-1=728$ ist nicht durch $5$ teilbar.

  Somit liefert der Induktionsanfang eine unwahre Aussage.

  Aussage 4

  $n^3-n$ ist durch $3$ teilbar.

  Induktionsanfang: $n=1$

  $1^3-1=0$ ist durch $3$ teilbar, denn es ist $3\cdot 0=0$.

  Somit liefert der Induktionsanfang eine wahre Aussage.

• Bestimme, nach welchem Gleichheitszeichen die Induktionsannahme verwendet wird.

  Tipps

  Die Induktionsannahme lautet:

  $A(n)$ gilt für ein $n\in\mathbb{N}$.

  Überprüfe, nach welchem Gleichheitszeichen der Ausdruck $\sum\limits_{k=1}^{n}(2k-1)$ mit dem Ausdruck $n^2$ ersetzt wird.

  Lösung

  Die Summe aller ungeraden Zahlen von $1$ bis $2n-1$ ist gleich dem Quadrat von $n$. Es gilt also:

  $A(n)$: $\sum\limits_{k=1}^{n}(2k-1)=n^2$ für alle $n\in\mathbb{N}$.

  Diese Aussage werden wir nun mittels vollständiger Induktion beweisen.

  1. Induktionsanfang

  $A(1)$: $\sum\limits_{k=1}^{1}(2k-1)=2\cdot 1-1=1=1^2$ ist eine wahre Aussage.

  2. Induktionsannahme

  $A(n)$ gilt für ein $n\in\mathbb{N}$.

  3. Induktionsschritt

  Zu zeigen:

  $\sum\limits_{k=1}^{n+1}(2k-1)=(n+1)^2$

  Es folgt:

  $\sum\limits_{k=1}^{n+1}(2k-1)=\sum\limits_{k=1}^{n}(2k-1)+(2(n+1)-1)\overset{\text{Induktionsannahme}}{=}n^2+(2(n+1)-1)=n^2+2n+1=(n+1)^2$

  4. Induktionsschluss

  $A(n)$ gilt somit für alle $n\in\mathbb{N}$.

• Beschreibe, wie du bei einem Beweis durch vollständige Induktion vorgehst.

  Tipps

  Schaue dir folgendes Beispiel an:

  $\sum\limits_{k=1}^{4}k=1+2+3+4=10$

  Mit diesem mathematischen Ausdruck kannst du alle Quadratzahlen berechnen.

  Für $n=5$ liefert der gegebene Ausdruck folgendes Ergebnis:

  $ \sum\limits_{k=1}^{5}(2k-1)= \underbrace{(2\cdot 1-1)}_{1}+\underbrace{(2\cdot 2-1)}_{3}+\underbrace{(2\cdot 3-1)}_{5}+\underbrace{(2\cdot 4-1)}_{7}+\underbrace{(2\cdot 5-1)}_{9}=25 $

  Lösung

  Aussagen über natürliche Zahlen können wir mit der vollständigen Induktion beweisen. Dabei handelt es sich oftmals um Ausdrücke, in denen Summenzeichen vorkommen. Also ist es sinnvoll, den Umgang mit Summenzeichen zu üben. Hierzu betrachten wir folgenden mathematischen Ausdruck:

  $\sum\limits_{k=1}^{n}(2k-1)$

  Wir bestimmen die Summen für $n=1$, $n=2$, $n=3$ und $n=4$. Es folgt für diese:

  $\sum\limits_{k=1}^{1}(2k-1)=2\cdot 1-1=1$

  $\sum\limits_{k=1}^{2}(2k-1)=(2\cdot 1-1)+(2\cdot 2-1)=1+3=4$

  $\sum\limits_{k=1}^{3}(2k-1)=(2\cdot 1-1)+(2\cdot 2-1)+(2\cdot 3-1)=1+3+5=9$

  $\sum\limits_{k=1}^{4}(2k-1)=(2\cdot 1-1)+(2\cdot 2-1)+(2\cdot 3-1)+(2\cdot 4-1)=1+3+5+7=16$

• Zeige mittels vollständiger Induktion, dass die gegebene Aussage gilt.

  Tipps

  Die Induktionsannahme lautet: $A(n)$ gilt für ein $n\in\mathbb{N}$.
  Diese muss im Induktionsschritt verwendet werden.

  Nachdem die Induktionsannahme eingesetzt wird, müssen die Terme gleichnamig gemacht und so umgeformt werden, dass der Ausdruck $\frac {n+1}{3(n+1)+1}=\frac {n+1}{3n+4}$ folgt.

  Lösung

  Im Folgenden führen wir die vollständige Induktion für die Aussage $A(n)$ durch:

  $A(n)$: $\sum\limits_{k=1}^{n}\frac{1}{(3k-2)(3k+1)}=\frac n{3n+1}$ für alle $n\in\mathbb{N}$

  1. Induktionsanfang

  $A(1)$: $\sum\limits_{k=1}^{1}\frac{1}{(3k-2)(3k+1)}=\frac{1}{(3\cdot 1-2)(3\cdot 1+1)}=\frac{1}{4}=\frac 1{3\cdot 1+1}$

  2. Induktionsannahme

  $A(n)$ gilt für ein $n\in\mathbb{N}$.

  3. Induktionsschritt

  Zu zeigen ist, dass für alle $n\in\mathbb{N}$ die Aussage $A(n+1)$ erfüllt ist, also dass gilt:

  $\sum\limits_{k=1}^{n+1}\frac{1}{(3k-2)(3k+1)}=\frac {n+1}{3(n+1)+1}$

  Demnach ergibt sich:

  $\sum\limits_{k=1}^{n+1}\frac{1}{(3k-2)(3k+1)}=\sum\limits_{k=1}^{n}\frac{1}{(3k-2)(3k+1)}+\frac{1}{(3(n+1)-2)(3(n+1)+1)}=...$

  Danach wird die Induktionsannahme verwendet. Dann folgt:

  $...=\frac n{3n+1}+\frac{1}{(3(n+1)-2)(3(n+1)+1)}=\frac n{3n+1}+\frac{1}{(3n+1)(3n+4)}=...$

  Nun machen wir beide Bruchterme gleichnamig:

  $...=\frac {n\cdot (3n+4)}{(3n+1)\cdot (3n+4)}+\frac{1}{(3n+1)(3n+4)}=\frac {n\cdot (3n+4)+1}{(3n+1)\cdot (3n+4)}=...$

  Wir multiplizieren jetzt die Klammer im Zähler aus und zerlegen diesen anschließend in Linearfaktoren, sodass sich der Ausdruck $3n+1$ kürzt:

  $...=\frac {3n^2+4n+1}{(3n+1)\cdot (3n+4)}=\frac {(3n+1)\cdot (n+1)}{(3n+1)\cdot (3n+4)}=\frac {n+1}{3n+4}=...$

  Das entspricht dem zu beweisenden Ausdruck. Denn es gilt:

  $\frac {n+1}{3n+4}=\frac {n+1}{3(n+1)+1}$

  q. e. d.

  4. Induktionsschluss

  Somit ist die Aussage $A(n)$ für alle $n\in\mathbb{N}$ erfüllt.