Vollständige Induktion – Beweismethode und Beispiele

Vollständige Induktion – Beweismethode und Beispiele Übung

• 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

  Mittels vollständiger Induktion ist zu beweisen, dass der Ausdruck $5^n+7$ für alle $n\in\mathbb{N}$ durch $4$ teilbar ist.

  1) Induktionsanfang

  Für $n=1$ gilt:

  $5^1+7=12$

  Da $12$ durch $4$ teilbar ist, denn $12:4=3$, ist dies eine wahre Aussage.

  2) Induktionsannahme

  $5^n+7$ ist für ein $n\in\mathbb{N}$ durch $4$ teilbar.

  3) Induktionsschritt

  Zu zeigen:
  Ist $5^n+7$ für ein $n\in\mathbb{N}$ durch $4$ teilbar, dann ist auch $5^{n+1+}7$ durch $4$ teilbar.

  $5^{n+1}+7=5\cdot 5^n+7=5\cdot (5^n+7)-4\cdot 7$

  An dieser Stelle nutzen wir die Induktionsannahme. Da $5^n+7$ für ein $n\in\mathbb{N}$ durch $4$ teilbar ist, ist auch $5(5^n+7)$ durch $4$ teilbar. Zudem ist jedes Produkt, dessen Faktor eine $4$ ist, durch $4$ teilbar. Also ist auch $4\cdot 7$ durch $4$ teilbar und somit auch die obige Differenz.

  4) Induktionsschluss

  Da der Ausdruck $5^n+7$ für ein $n\in\mathbb{N}$ sowie für die darauf folgende Zahl durch $4$ teilbar ist, muss er auch für alle $n\in\mathbb{N}$ durch $4$ teilbar sein!

• Gib den Beweis mittels vollständiger Induktion wieder.

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

  Für die hier zu beweisende Aussage erhalten wir dann:

  Induktionsanfang

  Für $n=1$ gilt:

  $1\cdot 2=\dfrac {1(1+1)(1+2)}{3}=\dfrac{6}{3}=2$

  Das ist eine wahre Aussage.

  Induktionsannahme

  $1\cdot 2+2\cdot 3+ \dots +n(n+1)=\dfrac{n(n+1)(n+2)}{3}$ gelte für ein $n\in\mathbb{N}$.

  Induktionsschritt

  Gilt die Aussage für ein $n\in\mathbb{N}$, dann gelte auch : $1\cdot 2+2\cdot 3+ \dots +n(n+1)+(n+1)(n+2)=\dfrac{(n+1)(n+2)(n+3)}{3}$

  Wir beginnen mit der linken Seite der Gleichung und stellen den Term durch Anwendung der Induktionsannahme wie folgt um:

  $\begin{array}{lll} 1\cdot 2+2\cdot 3+ \dots +n(n+1)+(n+1)(n+2) &=& \dfrac{(n)(n+1)(n+2)}{3}+(n+1)(n+2) \\ &&\\ &=& \dfrac{(n)(n+1)(n+2)}{3}+\dfrac{3(n+1)(n+2)}{3} \\ &&\\ &=& \dfrac{(n)(n+1)(n+2)+3(n+1)(n+2)}{3} \\ &&\\ &=& \dfrac{(n+1)(n+2)(n+3)}{3} \\ \end{array}$

  Wir erhalten am Ende die rechte Seite der zu beweisenden Aussage. Und damit ist dieser Beweis fertig. Man sagt dann quod erat demonstrandum, also was zu beweisen war.

  Induktionsschluss

  Da die Aussage für ein $n\in\mathbb{N}$ sowie für die darauf folgende 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.

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

  Sieh dir folgendes Beispiel zum Summenzeichen an:

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

  Lösung

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

  Beispiel 1: $~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!

  Beispiel 2: $~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!

  Beispiel 3: $~\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!

  Beispiel 4: $~\sum\limits_{k=1}^{n}k=\frac{n(n+1)}{2}$

  Induktionsanfang: $~n=1$

  linke Seite:

  • $\sum\limits_{k=1}^{1}k=1$

  rechte Seite:

  • $\frac{1(1+1)}{2}=\frac 22=1$

  Somit liefert der Induktionsanfang eine wahre Aussage!

  Beispiel 5: $~3^n\leq n^3$

  Induktionsanfang: $~n=1$

  linke Seite:

  • $3^1=3$

  rechte Seite:

  • $1^3=1$

  Da $3>1$ gilt, liefert der Induktionsanfang eine falsche Aussage!

• Bestimme, nach welchem Gleichheitszeichen die Induktionsannahme verwendet wird.

  Tipps

  Die Induktionsannahme besagt, dass $\sum\limits_{k=1}^{n}\frac{1}{(3k-2)(3k+1)}=\frac n{3n+1}$ für ein $n\in\mathbb{N}$ gilt.

  Überprüfe, an welcher Stelle der Ausdruck $\sum\limits_{k=1}^{n}\frac{1}{(3k-2)(3k+1)}$ durch den Ausdruck $\frac n{3n+1}$ ersetzt wird.

  Lösung

  Im Folgenden siehst du den gesamten Beweis mittels vollständiger Induktion der folgenden Aussage $A(n)$:

  $A(n):~\sum\limits_{k=1}^{n}\frac{1}{(3k-2)(3k+1)}=\frac n{3n+1}$ für $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, dass also 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.

• Vervollständige die Erklärung zur vollständigen Induktion von Richard Dedekind.

  Tipps

  Der Nachfolger einer natürlichen Zahl $n$ ist die natürliche Zahl $n+1$.

  Lösung

  Mittels der vollständigen Induktion können wir Aussagen über natürliche Zahlen beweisen. Die Idee dahinter wird durch folgende Formulierung von Richard Dedekind erläutert:

  • Um zu beweisen, dass ein Satz für alle natürlichen Zahlen $n\geq m$ gilt, genügt es zu zeigen, dass er für $n=m$ gilt und dass aus der Gültigkeit des Satzes für eine Zahl $n\geq m$ stets seine Gültigkeit auch für die folgende Zahl $n+1$ folgt.

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

  Tipps

  Nachdem die Induktionsannahme eingesetzt wird, müssen die Terme gleichnamig gemacht und so umgeformt werden, dass die rechte Seite der Aussage $A(n+1)$ folgt.

  Es gilt:

  $\sum\limits_{k=1}^5k=\sum\limits_{k=1}^4k+5$

  Lösung

  Im Folgenden beweisen wir 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!