f(n) = n^2 +1 per vollst. Induktion beweisen -Fehler

Question

ich komme bei meinem Induktionsbeweis nicht weiter.

Die Funktion sei für alle n ∈ ℕ durch

f(0) = 0

f(n) = 2 f(n-1) +1 für n ≥ 1

definiert.

Behauptung (mit der geschlossenen Form)

Es gilt f(n) =  n² +1  für alle n ∈ ℕ.

Beweis durch vollständige Induktion über n ∈ ℕ.

Induktionsanfang

Sei n = 0.

Dann gilt f(n) = f(0) = 0+1 = n² +1

Induktionsannahme

Die Behauptung f(n) = n² +1  gelte für ein n ∈ ℕ.

Induktionsschluss

Zeige f(n+1) = (n+1)² +1

f(n+1) = 2*f(n) +1

= 2 * (n² +1)  + 1  (Induktionsannahme einsetzen)

= 2 n² +2 +1

≠ Die beiden Gleichungen ist ungleich!

≠ n² + 2n +1 + 1
             = (n+1)² +1

Danke

Comments

Die Behauptung muss lauten: f(n) = 2ⁿ - 1.

Answer 1

Du darfst n=0 nicht als Induktionsanfang nehmen, weil die Behauptung für n=0 nicht gilt. Laut Definition von f ist nämlich f(0) = 0, laut Behauptung ist aber f(0)= 0²+1=1.

Entweder bei euch ist 0∈ℕ. Dann ist die Behauptung falsch. Oder es ist 0∉ℕ. Dann sagt die Behauptung nichts über n=0 aus und du solltest die Induktion bei 1 starten.

Allerdings ist ein Beweisversuch auch unter der Bedingung 0∉ℕ aussichtslos, weil die Behauptung auch für n≥1 nicht stimmt. Zum Beispiel ist laut Definition f(1)=2·0+1=1, f(2)=2·1+1=3, aber laut Behauptung f(1)=1²+1=2, f(2)=2²+1=5.

Comments

hi,

ja, macht irgendwie Sinn :). Das hab ich ja total übersehen.

Bei uns ist 0∈ℕ, somit stimmt die Behauptung nicht. Die habe ich dann wohl falsch ermittelt, bzw. . sie müsste gelten für n≥2.

Wir sollen für die (ganz oben angegebene) rekursive Funktion eine geschlossene Darstellung finden und diese dann beweisen.

Aber selbst bei gleicher Funktion, allerdings   n≥2 werd ich beim Induktionsschritt das gleiche Problem haben...

oder?

---

Ja, wirst du. Deine Vermutung über die geschlossene Form ist unzutreffend.

---

jaa, ich hab's :).

Danke euch beiden für die hilfe :)

Ist das denn mathematisch formal korrekt aufgeschrieben, oder gibt's da was zu bemängeln?

Behauptung (mit der geschlossenen Form)

Es gilt f(n) =  2ⁿ -1  für alle n ∈ ℕ.

Beweis durch vollständige Induktion über n ∈ ℕ.

Induktionsanfang

Sei n = 0.

Dann gilt f(n) = f(0)= 0= 1-1= 2⁰ - 1= 2ⁿ-1

Induktionsannahme

Die Behauptung f(n) = 2ⁿ -1  gelte für ein n ∈ ℕ.

Induktionsschluss

Zeige f(n+1) = 2ⁿ⁺¹ -1

f(n+1)  = 2*f(n) +1

= 2 * (2ⁿ -1)  + 1  (Induktionsannahme einsetzen)

= 2¹ *2ⁿ -2 +1

=  2ⁿ⁺¹ -1

---

Sieht gut aus. Wer vollständige Induktion kennt, der sollte deinen Beweis verstehen.