Mathe Doppelinduktion

lima81

Well-known member
ID: 259034
L
10 September 2007
135
10
Moin,
hab mein Mathestudium begonnen und erste Woche ganz gut überstanden. Haben in lineare Algebra auch gleich den ersten Übungszettel bekommen und die ersten 4 1/2 Aufgaben gingen auch ganz gut. Nur sitze ich jetzt schon seit Freitag an der letzten Teilaufgabe auf dem Zettel.
Es geht darum mit Hilfe der Doppelinduktion zu zeigen, dass die Menge
b21f6f8a916a851a691fab0ac9ca3187.gif
genau
d7d34426406c5a6359cb5a529b2c1550.gif
Elemente besitzt.
Mein Kumpel hat die Aufgabe gestern Abend geschafft nur seine Lösung gefällt mir nicht. Er setzt da schon viel vorraus was wir noch nicht bewiesen haben. Hab aber den Tipp bekommen den k=0 Fall anzuschauen und dann über k zu induzieren. Dann gibt es ja immer nur ein Element, nämlich k=0+0+0... und das n-mal. Hab dann versucht k+1 in den Binominalkoeffizienten einzusetzen und irgendwie damit rumzurechnen, indem ich mit den Fakultäten rechne. Aber komm da zu keinem Ergebnis. Könnte mir da evtl. einer helfen?
 
Also induktiv würde ich so vorgehen: Wenn man die Anzahl der Elemente für ein bestimmtes n kennt, dann findet man daraus die Anzahl für n+1, in dem man die Summe umschreibt als

a[sub]1[/sub]+...+a[sub]n[/sub] = k - a[sub]n+1[/sub].

Dabei darf a[sub]n+1[/sub] jetzt Werte von 0 bis k annehmen. Für jeden dieser Werte kennt man die Anzahl aus dem Induktionsschritt, sie ist jeweils C(k- a[sub]n+1[/sub]+n-1,n-1), wobei ich mal C(n,k) als Kurzschreibweise für n über k nehme. Das muss man jetzt üb er alle möglichen Werte für a[sub]n+1[/sub] summieren.

Zu zeigen ist letztlich, dass

Summe[sub]i=0[/sub][sup]k[/sup] C(k-i+n-1,n-1) = C(k+n,n)

oder äquivalent

Summe[sub]i=0[/sub][sup]k[/sup] C(i+n-1,n-1) = C(k+n,n)


Und das nun wieder induktiv. Diesmal ist der Induktionsschritt leichter: von k auf k+1 kommt links genau ein Term dazu, nämlich C(k+1+n-1,n-1) = C(k+n,n-1). Die Induktionsvermutung ist also

C(k+n,n) + C(k+n,n-1) = C(k+n+1,n), falls ich mich jetzt nicht vertan hab. Und das sieht mir sehr nach der Definition der Binonialkoeffizienten über das Pascalsche Dreieck aus (bzw. lässt es sich auch leicht über die Fakultätsdarstellung zeigen, falls ihr die bewiesen habt).
 
Morgen,
danke dir. Hab es selber auch noch gelöst bekommen gestern. Hab dafür einfach das Pascalsche Gesetz bewiesen, aber war hart darauf zu kommen. Gleich bei der ersten Übung gemerkt wieso alle meinten man trainiert die Frustrationstoleranz in Mathe ^^