Vollständige Induktion - Allgemein

Question

ich hoffe ihr versteht was ich im Folgenden meine: :D

ich weiß wie der Induktionsanfang, Annahme und der Induktionsschritt geht. Ich habe aber immer Probleme, wie ich dann meine Terme richtig aufschreibe um dann den Beweiß endgültig zu machen. z.B Term = Term =Term+ Term -> soll Term raus kommen.

Ich versuch mal eine Induktions Aufgabe ganz allgemein darzustellen:

Aufgabe z.B  An = Bn

Annahme: An = Bn

Schritt(n+1): (An+1) = (Bn+1)

Was muss ich dann machen? An + (An+1) = Bn+(An+1) = Bn+1 . So? Muss ich das immer so machen? (Außer bei Teilbarkeit und Ungleichung)

Answer 1

Im Induktionsschritt sollst du zeigen: Aus $A_n=B_n$ folgt $A_{n+1}=B_{n+1}$. Dazu musst Du $A_n$ in $A_{n+1}$ wiederfinden: $$A_{n+1}=\Phi(A_n, n+1).$$ Das ist die erste Eigenleistung, die Du zu erbringen hast. Dann wird die Induktionsvoraussetzung $A_n=B_n$ investiert: $$A_{n+1}=\Phi(A_n, n+1)=\Phi(B_n,n+1).$$ Schliesslich ist noch $\Phi(B_n,n+1)=B_{n+1}$ per Rechnung zu zeigen. Das ist die zweite zu erbringende Eigenleistung. Insgesamt sieht es also so aus: $$A_{n+1}=\Phi(A_n, n+1)=\Phi(B_n,n+1)=B_{n+1}.$$ So geht das ganz allgemein und abstrakt, was Du ja offensichtlich haben wolltest.

Comments

Ich habe Φ(An, n+1) noch nicht verstanden. Zu An (n+1) addieren?

---

Warum nur addieren und warum ausgerechnet n+1? Eine Funktion Φ bietet doch viel mehr Moeglichkeiten, als ihre Argumente nur zu addieren.

Finde A_n = 1 + 2 + ... + n in A_n+1 = 1 + 2 + ... + (n+1) wieder.

Finde A_n = 1² + 2² + ... + n² in A_n+1 = 1² + 2² + ... + (n+1)² wieder.

Finde A_n = n! in A_n+1 = (n+1)! wieder.

Finde A_n = (1+x)ⁿ in A_n+1 = (1+x)ⁿ⁺¹ wieder.

Finde A_n = f⁽ⁿ⁾ in A_n+1 = f⁽ⁿ⁺¹⁾ wieder.

Etc.

---

Und dann? An ist ja in An+1. Was schreibe ich dann hin? Dann hätte ich ja wieder An (Ich habe schon viele Aufgaben angeschaut und versucht, aber ich komm einfach nicht dahinter.

---

Ich hab Dir fuenf Beispiele hingeschrieben. Bestimme einfach zur Uebung Φ in allen Faellen. Beispielsweise ist beim ersten Φ(x, y) = x + y und beim letzten Φ(f) = f' (ein zweites Argument wird nicht gebraucht).

Des weiteren steckt ja im ersten Beispiel der Kleine Gauss: A_n = 1 + 2 + ... + n, B_n =n(n+1)/2 und Φ(x, y) = x + y wie angegeben. Daran kannst Du das ganze Programm aus der Antwort haarklein Stueck für Stueck nachstellen. (Das ist ebenfalls eine Uebungsaufgabe.)

---

Induktionsschluss zu der Kleine Gauss:

Erster Schritt. Finde $A_n$ in $A_{n+1}$ wieder:

$$\underbrace{1+\cdots+(n+1)}_{=A_{n+1}}=\underbrace{\underbrace{(1+\cdots+n)}_{=A_n}+(n+1)}_{=\Phi(A_n,n+1)}=\ldots$$

Zweiter Schritt. Benutze die Induktionsvoraussetzung $A_n=B_n$, d.h. ersetze $A_n$ durch $B_n$:

$$\ldots=\underbrace{\underbrace{\frac{1}{2}n(n+1)}_{=B_n}+(n+1)}_{=\Phi(B_n,n+1)}=\ldots$$

Dritter Schritt. Forme das erhaltene zu $B_{n+1}$ um:

$$\ldots=\frac{1}{2}(n+1)(n+2).$$