30 Tage kostenlos testen:
Mehr Spaß am Lernen.

Überzeugen Sie sich von der Qualität unserer Inhalte.

Vollständige Induktion – Erklärung an der Gauß'schen Summenformel 06:57 min

Textversion des Videos

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

Carl Friedrich Gauß war seiner Zeit voraus. In der Schule hat er sich nur gelangweilt. Aber so etwas sah der Lehrer gar nicht gern. Damit Gauß beschäftigt war, sollte er alle Zahlen von 1 bis 100 addieren. Doch dafür musste Gauß nicht lange überlegen! Wie hat er das so schnell geschafft? Schauen wir uns doch einmal an, was Gauß sich da ausgedacht hat! Wir wollen alle natürlichen Zahlen von 1 bis 100 addieren. Innerhalb der Addition ist die Reihenfolge egal wir können die Zahlen also auch paarweise zusammenfassen: 1 plus 100 ergibt zusammen 101. Und 2 plus 99 ergibt auch 101. 3 plus 98 ? ebenfalls 101! Das funktioniert so für alle diese Paare. Und wie viele Paare ergeben sich aus hundert Zahlen? Hundert Halbe - also 50! Also muss die Summe insgesamt 100 Halbe mal 101 ergeben und das ist 5050. Wir können dieses Produkt auch anders schreiben. Nämlich als den größten Summanden — also 100 — mal den 'größten Summanden plus 1' und das Ganze geteilt durch 2. Vielleicht können wir dieses Schema auch bei anderen Summen anwenden? Addieren wir mal die Zahlen von 1 bis 5! Das Ergebnis ist 15. Dann überprüfen wir, ob unsere Vermutung hier auch funktioniert. Wir multiplizieren also den größten Summanden, 5, mit 'fünf plus eins' und teilen durch 2. Zusammengefasst ergibt das 30 Halbe also 15 - stimmt! Ob diese Methode auch für die Summe aller natürlichen Zahlen bis hin zu einer BELIEBIGEN ZAHL n funktioniert? Das beweisen wir mit Hilfe der vollständigen Induktion. Dieser Ausdruck heißt "Summenzeichen". Er bedeutet, dass du für DIESES k alle Zahlen von 1 bis n einsetzen sollst und sie dann addierst. Laut der Gauß'schen Summenformel ist das das Gleiche wie n mal 'n plus 1' Halbe. Aussagen über alle natürlichen Zahlen kannst du mit der vollständigen Induktion beweisen. Dafür kannst du immer nach einem Muster vorgehen: Du beginnst mit dem Induktionsanfang:
Hier nimmst du deine erste Zahl - in der Regel die 1 - und prüfst dafür die Aussage. Wenn die Aussage für die erste Zahl stimmt, kommt als nächster Schritt die Induktionsannahme. Man nennt sie auch Induktionsvoraussetzung. Dabei nimmst du an, dass die Aussage für irgendeine natürliche Zahl n stimmt. Als nächstes kommt der Induktionsschritt. Dabei ist es das Ziel, aus A von n zu folgern, dass die Aussage auch für 'n plus 1', also den Nachfolger von n, gilt. Das ist der wichtigste und meistens auch schwierigste Teil. Du musst nämlich die Induktionsannahme an irgendeiner Stelle benutzen, sonst läuft etwas falsch. Aber wenn dir das gelingt, hast du es fast geschafft! Denn jetzt kommt der Induktionsschluss! Weil du im Induktionsanfang gezeigt hast, dass die Aussage für die erste Zahl stimmt und du im Induktionsschritt bewiesen hast, dass die Aussage immer auch für die nächste Zahl stimmt muss sie für alle natürlichen Zahlen gelten! Und damit ist dein Beweis fertig – man sagt: quod erat demonstrandum, also: was zu beweisen war! Nun möchten wir wissen, ob die Formel von Gauß stimmt und zwar für alle natürlichen Zahlen n: Im Induktionsanfang untersuchen wir die Aussage für n gleich 1. Die Summe aller natürlichen Zahlen von 1 bis 1 muss natürlich 1 ergeben
und das erhalten wir auch mit der Formel. In der Induktionsannahme nehmen wir nun an, dass die Gauß'sche Summenformel für IRGENDEIN n gilt. Nun der Induktionsschritt: wir untersuchen wir die Aussage für die darauffolgende Zahl "n plus 1". Wir wollen also zeigen, dass die Summenformel auch für 'n plus 1' gilt also, dass wir überall 'n' durch 'n plus 1' ersetzen können und die Gleichung immer noch stimmt. Die Summe aller natürlichen Zahlen von 1 bis "n plus 1" besteht zum einen Teil aus der Summe aller natürlichen Zahlen von 1 bis n und zusätzlich aus dem letzten Summanden "n plus 1" Den lassen wir erst einmal stehen. Kommt dir dieser Ausdruck bekannt vor? Laut der Induktionsannahme können wir ihn durch dieses Produkt ersetzen. Nun fassen wir noch geschickt zusammen: Wir bringen beide Terme auf einen Nenner, und fassen sie zu einem Bruch zusammen. Fällt dir etwas auf? Wir können "n plus 1" ausklammern!
Und weil 'n plus 2' natürlich 'n plus 1 plus 1' ist haben wir genau die gesuchte Form gefunden. Also ist der Induktionsschritt geschafft. Damit sagt der Induktionsschluss dass die Formel für alle natürlichen Zahlen gilt. QED! Fassen wir doch noch einmal zusammen: Mit der Vollständigen Induktion kannst du Aussagen über alle natürlichen Zahlen beweisen Im Induktionsanfang überprüfst du die Aussage für die erste Zahl. Für die Induktionsannahme nimmst du an, dass die Aussage für irgendeine natürliche Zahl n gilt. Im Induktionsschritt schließt du aus dieser Aussage über n auf die Aussage über die nachfolgende Zahl "n plus 1". Und damit kannst du im Induktionsschluss sicher sagen, dass die Aussage für alle natürlichen Zahlen gilt. Du kannst dir das Vorgehen wie Dominosteine vorstellen: Wenn du den ersten Stein umwirfst, ist das der Induktionsanfang und dass jeder Stein den nächsten mitnimmt, entspricht dem Induktionsschritt und dass sie dann alle umfallen, ist der Induktionsschluss. Gauß war eben wirklich seiner Zeit voraus und sein Lehrer – der war völlig raus.

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

Du möchtest dein gelerntes Wissen anwenden? Mit den Aufgaben zum Video Vollständige Induktion – Erklärung an der Gauß'schen Summenformel kannst du es wiederholen und üben.

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

    Tipps

    Schau 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$ und
    • $\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$.
  • 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 wäre 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}$
    Diese 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!

  • 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 Folgendes gilt:

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

    Somit folgt:

    $\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)}=...$

    Nun 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. Es folgt dann:

    $...=\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 nun 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.

  • 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.

    Schau 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 falsche 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~$ 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}$.