Benutze doch die (bekannte?) Formel
(a+1b)=(ab−1)+(ab)
oder beweise sie zunächst durch dein Umschreiben auf die Fakultäten.
Induktion über n könnte dann so aussehen:
l=0∑n+1(n+1l)∗(mk−l)
und das müsste man unter Verwendung der Ind.vor. umformen zu
(n+1+mk)
Zuerst mal den ersten und den letzten Summanden extra schreiben
=(n+10)∗(mk)+l=1∑n(n+1l)∗(mk−l)+(n+1n+1)∗(mk−n−1)
Jetzt die besagte Formel anwenden und die extra geschriebenen vereinfachen
=(mk)+l=1∑n((nl−1)+(nl))∗(mk−l)+(mk−n−1)
In der Summe die Klammer auflösen und zwei Summen draus machen
=(mk)+l=1∑n(nl−1)∗(mk−l)+l=1∑n(nl)∗(mk−l)+(mk−n−1)
Der erste Binomialkoeffizient ist genau der 0-te Summand der 2. Summe, also
hat man schon mal
=l=1∑n(nl−1)∗(mk−l)+l=0∑n(nl)∗(mk−l)+(mk−n−1)
und man kann für die 2. Summe die Ind.vor. einsetzen
=l=1∑n(nl−1)∗(mk−l)+(n+mk)+(mk−n−1)
In der verbleibenden Summe den Index verschieben gibt
=l=0∑n−1(nl)∗(mk−l−1)+(n+mk)+(mk−n−1)
Dann ist der letzte Binomialkoeffizient genau der n-te Summand dieser Summe, also gibt es
=l=0∑n(nl)∗(mk−l−1)+(n+mk)
Das ist genau die Formel aus Indvoraussetzung für k-1an Stelle von k.
Also kann man das Ergebnis einsetzen und hat
=(n+mk−1)+(n+mk)
Und mit der eingangs zitierten Formel ergibt sich - wie gewünscht -
(n+1+mk)