Binomialkoeffizient aus rekursiver Funktion herleiten

06.01.2020, 22:38	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 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)) = 20+2f(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)) = 2f(1,x-1,0)+2f(1,x-1,1) = 2(2^x-1) + 2f(1,x-1,1) = (2^x)*x
07.01.2020, 09:29	HAL 9000	Auf diesen Beitrag antworten »
Mit "Herleiten" meinst du, wie man die Formel $\begin{eqnarray} f(1,x,y)=2^x\binom{x}{y} \end{eqnarray}$ beweist? Naja, das geht z.B. per Vollständiger Induktion über $\begin{eqnarray} x \end{eqnarray}$ der Aussage $\begin{eqnarray} A(x) \end{eqnarray}$ : Für alle $\begin{eqnarray} y \end{eqnarray}$ mit $\begin{eqnarray} 0\leq y\leq x \end{eqnarray}$ gilt $\begin{eqnarray} f(1,x,y)= 2^x\binom{x}{y} \end{eqnarray}$ . Induktionsanfang $\begin{eqnarray} x=0 \end{eqnarray}$ : Hier ist nur $\begin{eqnarray} y=0 \end{eqnarray}$ zu betrachten, und damit $\begin{eqnarray} f(1,0,0)= 2^0\binom{0}{0}=1 \end{eqnarray}$ nachzuweisen, was mit der dritten Fallzeile deiner Iterationsgleichung auch gelingt. Induktionsschritt $\begin{eqnarray} x\to x+1 \end{eqnarray}$ : Hier sind gesondert die drei Fälle $\begin{eqnarray} y=0 \end{eqnarray}$ , $\begin{eqnarray} 1\leq y\leq x \end{eqnarray}$ sowie $\begin{eqnarray} y=x+1 \end{eqnarray}$ zu betrachten, wobei natürlich die Induktionsvoraussetzung einfließen darf - dann mal ran!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »