Binomialkoeffizient aus rekursiver Funktion herleiten

Neue Frage »

Info-Karl-123 Auf diesen Beitrag antworten »
Binomialkoeffizient aus rekursiver Funktion herleiten
Meine Frage:
Hallo ich bearbeite die im Bild gezeigt Aufgabe.
Die Aufgabe geht eigentlich eher in Richtung Informatik, aber ich hoffe das mir trotzdem jemand helfen kann und möchte.
Ich habe bereits herausgefunden, das die Funktion folgende Formel berechnet:

(2^x)*(x über y) = (2^x)*(x!/(y!*(x-y)!))

Ich habe nur leider keine Idee, wie ich:

f(1,x,y) = (2^x)*(x über y)

Herleiten soll.
Ich bin über jede Antwort Dankbar smile




Meine Ideen:
Ich habe bereits folgendes Hergeleitet:

f(0,x,y) = 2x+2y
f(1,x,0) = f(0,0,f(1,x-1,0)) = 2*0+2*f(1,x-1,1) = 2*...*f(1,0,0) = 2^x * 1 = 2^x
f(1,x,1) = f(0,f(1,x-1,0),f(1,x-1,1)) = 2*f(1,x-1,0)+2*f(1,x-1,1)
= 2*(2^x-1) + 2*f(1,x-1,1)
= (2^x)*x
HAL 9000 Auf diesen Beitrag antworten »

Mit "Herleiten" meinst du, wie man die Formel beweist? Naja, das geht z.B. per Vollständiger Induktion über der Aussage

: Für alle mit gilt .

Induktionsanfang : Hier ist nur zu betrachten, und damit nachzuweisen, was mit der dritten Fallzeile deiner Iterationsgleichung auch gelingt.

Induktionsschritt : Hier sind gesondert die drei Fälle , sowie zu betrachten, wobei natürlich die Induktionsvoraussetzung einfließen darf - dann mal ran!
 
 
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »