Vollständigen Induktion mit Programmcode (n hoch 2)

Question

Hallo zusammen,

wir sollen eine vollständige Induktion anhand eines Programmcodes in Java-Script durchführen. Ich hoffe, dass ich hier nicht komplett falsch bin.

Aufgabe:

Zeigen Sie mit Hilfe der vollständigen Induktion, dass für alle natürlichen Zahlen n >= 1 gilt:

function berechne(n) {
  let sum = 0;

  for (let i = 1; i <= n; i++) {
      sum += 2*i-1;
  }
 
  return sum;
}

= n²

Problem:

Der Programmcode berechnet \( \sum\limits_{i=1}^{n}{(2n - 1)} \). Wenn statt des Programmcodes der Beweis von \( \sum\limits_{i=1}^{n}{(2n - 1)} \) = n² gefragt wäre, wüsste ich, wie ich die Aufgabe lösen kann.

Leider weiß ich ab dem Beweis nicht mehr weiter.

Mein Ansatz:

IA: berechne(1) = 1 = 1² = n²

IV: Wie gehen davon aus, dass berechne(n) = n² für alle natürlichen Zahlen n >= 1 gilt.

IS: Behauptung: berechne(n + 1) = (n + 1)² für alle natürlichen Zahlen n >= 1

Beweis: berechne(n + 1) = berechne(n) + ?????

Wenn das ganze als Summe dargestellt wäre, könnte ich ja einfach bei ????? (2(n+1) - 1) schreiben, oder?

Allerdings habe ich keine Idee, wie es jetzt mit dem Programmcode weiter geht.

Auch wenn dies kein Programmierforum ist, hoffe ich, dass ihr mir helfen könnt.

Vielen Dank!

Gruß Dennis

Answer 1

iA:

1 = 1^2

IS:

∑ (1 bis n) (2n - 1) + (2(n + 1) - 1) = (n + 1)^2

n^2 + (2(n + 1) - 1) = (n + 1)^2

n^2 + 2n + 2 - 1 = (n + 1)^2

n^2 + 2n + 1 = (n + 1)^2

Das stimmt nach der 1. binomischen Formel.

Comments

Vielen Dank für deine Antwort.

Ja, vielleicht habe ich mich nicht eindeutig ausgedrückt. Die von dir gezeigte Lösung ist mir bekannt. Mir geht es darum, wie ich den Programmcode in die vollständige Induktion einbaue. Du hast ja jetzt einfach mit der Summe gerechnet, was glaube ich nicht der Aufgabenstellung entspricht. Trotzdem Danke!

Vielleicht bin ich auch falsch hier und müsste die Frage eigentlich in das Programmierer-Forum stellen?

---

Du sollst schon zeigen das dort n^2 heraus kommt. Also du beweist per Vollständiger induktion der der Programmiercode genau n^2 berechnet.

---

Ja, da stimme ich dir zu, allerdings ist das nicht das was unser Professor möchte.

Hier ein Beispiel, wie eine ähnliche Aufgabe seiner Ansicht nach gelöst werden soll:

Aufgabe:

function tuEtwas(n) {
  let ergebnis = 1;
  for (i = 1; i <= n; i++) {
      ergebnis = ergebnis + ergebnis;
  }
  return ergebnis;
}

= 2ⁿ

Musterlösung vom Professor:

IA: tuEtwas(0) = 1 = 2⁰

IV: tuEtwas(n) = 2ⁿ

IS: Behauptung: tuEtwas(n + 1) = 2ⁿ⁺¹

Beweis: tuEtwas(n + 1) = tuEtwas(n) + tuEtwas(n)

= 2ⁿ + 2ⁿ

= 2 * 2ⁿ

= 2ⁿ⁺¹

Wie du siehtst baut der Prof den Programmcode in die vollständige Induktion ein. Ich habe nur keine Ahnung, wie man das bei der obigen Aufgabe machen könnte.

Sorry, wenn meine ursprüngliche Fragestellung nicht eindeutig war.

---

Dann würde das doch wie folgt lauten, oder nicht?

iA:

berechne(1) = 1

iS:

berechne(n + 1) = berechne(n) + 2(n + 1) - 1 = n^2 + 2n + 1 = (n + 1)^2

---

Wenn man das so machen "darf" (also das hier: "berechne(n) + 2(n + 1) - 1" ), dann wäre die Lösung ja garnicht so schwer.

Ich kann den Professor ja mal fragen, ob das aus seiner Sicht so richtig wäre.

Vielen Dank für deine Hilfe!