Wie viele Elemente hat die Menge Μ := {(k1, k2, k3) ∈ ℕ : k1 + k2 +k3 = n}

Question

Wie viele Elemente hat die Menge

Μ_n := {(k1, k2, k3) ∈ ℕ³ : k₁ + k₂  +k₃ = n} 

für vorgegebenes n ∈ ℕ₀?  Beweisen Sie Ihre Vermutung mittels vollständiger Induktion!

Also mein Ansatz sieht bisher wie folgt aus:

Ich habe ein kleines Programm geschrieben, was für ein n die Anzahl möglicher Tupel bestimmt dabei kam z.B raus:

(0/0/0) Für n = 0  gibt es: 1 Kombinationen!
(0/0/1) (0/1/0) (1/0/0) Für n = 1  gibt es: 3 Kombinationen!
(0/0/2) (0/1/1) (0/2/0) (1/0/1) (1/1/0) (2/0/0) Für n = 2  gibt es: 6 Kombinationen!
(0/0/3) (0/1/2) (0/2/1) (0/3/0) (1/0/2) (1/1/1) (1/2/0) (2/0/1) (2/1/0) (3/0/0) Für n = 3  gibt es: 10 Kombinationen!

Es fällt erstmal auf, dass die Anzahl der Kombinationen sich jedes um 2 dann um 3 dann um 4 und so weiter erhöht, dieser Trend scheint dauerhaft zu bestehen kontrolliert bis 100.

Also habe ich eine Rekursive Funktion aufgestellt

Φ(n) := Φ(n-1) + n+1 sowie definiert:

Φ(0) := 1

Nun die Frage, wie kann ich die vollständige Induktion darauf anwenden? 

Mein Versuch sah bisher so aus:

Induktionsverankerung:

Φ(0) = 1 ✓

Φ(1) = 3 ✓

Induktionsschritt:

n → n+1

z.Z Φ(n+1) = Φ(n) + n + 2

was ja aber schon quasi nach der Definition der Funktion gleich ist!

   Φ(n+1) = Φ((n +1) -1) + (n +1) +1

= Φ(n+1) = Φ(n) + n + 2

= Φ(n) + n + 2   qed

Ich mache mir gerade ein wenig Sorgen, dass ich da vollkommen falsch liegen könnte, diese Aufgabe gibt ganz schön viele Punkte auf dem Übungsblatt und dafür fand ich die Induktion am Ende zu trivial.

Answer 1

Mit der Definition setzt du voraus, was du erst nachweisen willst. Das ist kein Beweis.

Vielleicht hilft die Summenformel 1+2+...+n = n(n+1)/2

Comments

Also man kann eine modifizierte Version der Summenformel verwenden nämlich

\( \frac{(n+1)(n+2)}{2} \)

aber wie kann ich denn nun beweisen, dass diese Formel für das Problem Lösungen liefert? Ich könnte sicher einfach wieder jetzt für n n+1 einsetzen, aber das zeigt ja nur, dass die Formel auch für n+1 gilt aber eben nicht, dass die Formel mit dem Problem überhaupt was zu tun hat.

---

Ich denke gerade über deine Aufgabe nach.

Vielleicht ist folgende Idee sinnvoll:

Die jeweils neuen Tripel für n+1 kann man so bilden:

Ich addiere jeweils zur 3. Koordinate der alten Tripel (mit n) 1. Dann habe ich genauso viele Tripel für n+1 wie für n. Zusätzlich kommen  n+2 Tripel hinzu, deren 3. Koordinate 0 ist.

Nun muss noch gezeigt werden, dass das n+2 Tripel sind, was vielleicht mit vollständiger Induktion möglich ist.