Vollständige Induktion: Zeige: zu einer n-elementigen Menge A gibt es n^k verschiedene Tupel (a1,,,,,,ak)

Question

zu einer n-elementigen Menge A gibt es n^k verschiedene Tupel (a₁,,,,,,a_k) mit a_j ε A für j = 1,,,,,,,k für

beliebiges k <=n.

wie beweis man mit hilfe vollständiger induktion.

Danke

Comments

Man kann das auch ohne Induktion zeigen :)

Answer 1

Sei n=1: A besitzt also 1 Element und dann gibt es nur ein Tupel (a₁) mit k=n=1 und 1¹ = 1

Ind. Schluß: Sei A’ eine (n+1)-elementige Menge und sei k beliebig gewählt mit 1 ≤ k ≤ n

Die Anzahl der möglichen k-Tupel setzt sich folgendermaßen zusammen:

a) die k-Tupel enthalten nur die bisherigen n Elemente a_n Diese Anzahl ist nach Ind. Annahme gleich n^k   = $$\begin{pmatrix} k\\k \end{pmatrix}*n^{k}$$

b) das k-Tupel enthält nur das neue Element a_n+1.   Diese Anzahl ist genau 1 = $$\begin{pmatrix} k\\0 \end{pmatrix}*n^{0}$$

c) das k-Tupel enthält alle Kombination von (n+1) Elementen, in denen a_n+1 einmal vorkommt. Diese Anzahl ist  $$\begin{pmatrix}k\\1\end{pmatrix}*n^{1}$$

usw. Die Gesamtanzahl beträgt daher:

$$\sum \limits_{j=0}^{k}\begin{pmatrix} k\\j \end{pmatrix}n^{j} = (n+1)^{k}$$

was zu zeigen war.

Comments

Einfacher wäre eine Induktion über k.

Warum eigentlich k<=n?

---

Natürlich, aber würde das dieselbe Aussage zeigen?

---

Welches wäre die 2 unterschiedlichen Aussagen?

---

Frage mit Gegenfrage beantworten?

---

Also gut, die Antwort ist ja: Die Anzahl der k-Tupel ist n^k, auch wenn ich es per Induktion über k beweise.

---

OK, Im Prinzip ist das eine komische Aufgabe. Für einen Beweis benötigt man überhaupt keine Induktion. Da sie nun mal gefordert war und die über k mehr oder weniger trivial ist, habe ich mich für die interessantere Variante entschieden - in der Annahme, dass das die Idee hinter dieser Aufgabe war wenn man denn schon Beweis per Induktion fordert.