TU Wien:Diskrete Mathematik für Informatik UE (Drmota)/Übungen WS10/Beispiel 11

Der Trick: x=x-k+k ==> x^_k_ = (x-k)*x^_k_ + k*x^_k_ ==> x^_k_ = *x^_k+1_ + k*x^_k_

Beweis über Induktion: Summe mit x multiplizieren, x in die Summe hineinziehen, obige Formel anwenden, Summe in zwei Summen aufteilen, Indexverschiebung, Anwendung der Rekursionsformel

Lösungsvorschlag 2

In der obigen Formel fehlt IMHO etwas, die restliche Vorgangsweise ist gleich. Ich hab hier mal meine Version eingescannt:

mfg, woife

Anmerkung 1: Woher kommt das 1 + ...? Wenn k = 0, dann ist der Summand auch 0! Auch beim wieder hinzufügen gilt Sn,0 = 0. ++ von vale

Anmerkung 2: Die letzte Eingliederung von Sn,n hab ich mir so erklärt: Sn,n = Sn+1,n+1. Siehe Dreieck. Oder? Erst dann kann ichs in die Summe wieder Eingliedern.

ad Anmerkung 1: Sorry, mein Fehler. Ja, in dem Fall gehört in den drei Zeilen die mit 1 + ... beginnen eigentlich 0 + ...

ad Anmerkung 2: Ja, im letzten Schritt habe ich $S_{n,n}=S_{n+1,n+1}=1$ ausgenützt.

Danke für die Hinweise, mfg, woife