Fibonacci-Rekurrenz (Beweis)

04.06.2014, 15:58

Boom

Auf diesen Beitrag antworten »

Fibonacci-Rekurrenz (Beweis)

Meine Frage:
Moin.

Ich habe die Augabge, Fibonacci zu beweisen, folgendes ist gegeben:

Seien $\begin{eqnarray*} \alpha ,\beta \in \mathbb N _0 \end{eqnarray*}$ .
Sei ferner $\begin{eqnarray*} \mathbb N _0 \to\mathbb N _0 \end{eqnarray*}$ gegeben mit

$\begin{eqnarray*} f(n) & \leq = & \left\{ \frac{\alpha}{\beta + f(n-1) + f(n-2)} \right\} \\ \end{eqnarray*}$

$\begin{eqnarray*} \alpha : n\leq 1 \end{eqnarray*}$
$\begin{eqnarray*} \beta: sonst \end{eqnarray*}$

für alle $\begin{eqnarray*} n \in \mathbb N _0 \end{eqnarray*}$

Zu zeigen ist:
$\begin{eqnarray*} f(n)\leq \gamma (\phi^{n + 2} - 1) \end{eqnarray*}$ für alle $\begin{eqnarray*} n \in \mathbb N _0 \end{eqnarray*}$

Hinweise:
$\begin{eqnarray*} \phi \end{eqnarray*}$ ist der goldene Schnitt uns es gilt $\begin{eqnarray*} \phi = \frac{1 + \sqrt{5} }{2} \approx 1,618 \end{eqnarray*}$

Die Identität ist mit $\begin{eqnarray*} \phi = \phi^{2} - 1 \end{eqnarray*}$ ebenfalls gegeben.

Meine Ideen:
Ich dachte mir, dass man das ganze mit einer vollständigen Induktion lösen könnte. da Alpha ja für f(0) und f(1) gilt, würde ich beim I.A. beides beweisen, sprich das folgendes Beweise:

$\begin{eqnarray*} f(n) = f(0) \leq \alpha \leq \gamma (\phi^{n + 2} - 1) \end{eqnarray*}$

Doch genau hier harpert es bei mir. Meine Ausarbeit sieht im Moment folgender Maßen aus:

$\begin{eqnarray*} \gamma (\phi^{n + 2} - 1) \end{eqnarray*}$
$\begin{eqnarray*} \gamma (\phi^{0 + 2} - 1) \end{eqnarray*}$
$\begin{eqnarray*} \gamma(\phi^{2} - 1) \end{eqnarray*}$
$\begin{eqnarray*} \gamma(\phi) \end{eqnarray*}$
$\begin{eqnarray*} max\left\{ \alpha ,\beta \right\}\phi \end{eqnarray*}$
$\begin{eqnarray*} max\left\{ \alpha ,\beta \right\}1,618 \end{eqnarray*}$

Am Ende müsste ja nur noch Alpha stehen. Da $\begin{eqnarray*} n \leq 1<br /> \end{eqnarray*}$ gilt, rechnet man wohl Alpha mulitpliziert mit Phi. Da Alpha Null ist, würde auch Null als Ergebnis herauskommen.
Doch wenn ich das ganze mit n = 1 durchgehe, müsste ich am Ende ja Eins multiplitziert mit Phi rechnen. Doch dann bekomme ich ja keine 1 sondern die 1,618.

Könnt ihr mir sagen wo mein Fehler liegt?
Oder benutze ich generell die falsche Beweismethode?
Wenn ja, welche würde am besten passen?

04.06.2014, 17:12

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Boom
$\begin{eqnarray*} f(n) & \leq = & \left\{ \frac{\alpha}{\beta + f(n-1) + f(n-2)} \right\} \\ \end{eqnarray*}$

$\begin{eqnarray*} \alpha : n\leq 1 \end{eqnarray*}$
$\begin{eqnarray*} \beta: sonst \end{eqnarray*}$

für alle $\begin{eqnarray*} n \in \mathbb N _0 \end{eqnarray*}$

Das soll wohl eigentlich

$\begin{eqnarray*} f(n) \leq \begin{cases} \alpha & \;\mbox{für}\; n\leq 1 \\ \beta + f(n-1) + f(n-2) & \;\mbox{sonst} \end{cases} \end{eqnarray*}$

heißen - oder? verwirrt

verwirrt

P.S.: Es fehlen übrigens Angaben, wie groß $\begin{eqnarray*} \gamma \end{eqnarray*}$ denn da sein soll - vermutlich irgendein Ausdruck in $\begin{eqnarray*} \alpha,\beta \end{eqnarray*}$ ? verwirrt

verwirrt

04.06.2014, 17:14

Boom

Auf diesen Beitrag antworten »

ja aber habs nicht hingekriegt, es auf diese Weise mit LaTex zu schreiben Hammer

Hammer

04.06.2014, 17:18

Boom

Auf diesen Beitrag antworten »

Achja, was ich vergessen habe zu erwähnen:

$\begin{eqnarray*} \gamma := max\left\{\alpha ,\beta \right\} \end{eqnarray*}$

04.06.2014, 17:24

HAL 9000

Auf diesen Beitrag antworten »

Wo ist denn dann beim IA noch ein Problem? Wegen $\begin{eqnarray*} 1~{\color{red}<}~\phi \end{eqnarray*}$ sowie $\begin{eqnarray*} \alpha~{\color{blue}\leq}~\gamma \end{eqnarray*}$ ist dann

$\begin{eqnarray*} f(0)\leq \alpha ~{\color{red}\leq}~ \alpha \phi ~{\color{blue}\leq}~ \gamma \phi = \gamma(\phi^2-1) \end{eqnarray*}$ ,

04.06.2014, 17:41

Boom

Auf diesen Beitrag antworten »

Also, war mein Gedanke doch nicht falsch Freude

Freude

obwohl da $\begin{eqnarray*} \leq \end{eqnarray*}$ steht, habe ich ständig an das Gleichheitszeichen gedacht.
Für den I.S dann einfach für n+1 beweisen.

Bei weiteren fragen werde ich mich dann wieder melden smile

smile

Anzeige

05.06.2014, 03:06

Boom

Auf diesen Beitrag antworten »

Ich habe nun nen Problem im I.S.

Soweit bin ich gerade:

$\begin{eqnarray*} f(n+1)\leq \beta + f((n+1)-1) + f((n+1) -2) \end{eqnarray*}$
$\begin{eqnarray*} f(n+1)\leq \beta + f(n) + f(n-1) \end{eqnarray*}$
$\begin{eqnarray*} f(n+1)\leq \beta + \gamma(\phi^{n+2}-1) + f(n-1) \end{eqnarray*}$
$\begin{eqnarray*} f(n+1)\leq \beta + \gamma(\phi) + f(n-1) \end{eqnarray*}$
$\begin{eqnarray*} f(n+1)\leq \beta + max\left\{ \alpha, \beta\right\} (\phi) + f(n-1) \end{eqnarray*}$
$\begin{eqnarray*} f(n+1)\leq max\left\{ \alpha, \beta\right\} + max\left\{ \alpha, \beta\right\} (\phi) + f(n-1) \end{eqnarray*}$

Doch irgentwie bringt mich das ganze nicht wirklich weiter traurig

traurig

Ich hatte folgende Idee:

$\begin{eqnarray*} f(n+1)\leq max\left\{ \alpha, \beta\right\} + max\left\{ \alpha, \beta\right\} (\phi) + f(n-1) \end{eqnarray*}$
$\begin{eqnarray*} f(n+1)\leq max\left\{ \alpha, \beta\right\} + max\left\{ \alpha, \beta\right\} (\phi) + f(-n) \end{eqnarray*}$
$\begin{eqnarray*} f(n+1)\leq max\left\{ \alpha, \beta\right\} + max\left\{ \alpha, \beta\right\} (\phi) + -max\left\{ \alpha, \beta\right\} \end{eqnarray*}$
$\begin{eqnarray*} f(n+1)\leq + max\left\{ \alpha, \beta\right\} (\phi) \end{eqnarray*}$
$\begin{eqnarray*} f(n+1)\leq + max\left\{ \alpha, \beta\right\} (\phi^{n+2}-1) \end{eqnarray*}$

Aber glaube kaum, dass dies so richtig ist.

05.06.2014, 08:48

HAL 9000

Auf diesen Beitrag antworten »

Entschuldige, wenn ich das so deutlich sage:

Was du da treibst, ist sinnlose Termpfuscherei ohne Sinn und Verstand. Die wesentliche Aussage der Behauptung ist doch, dass $\begin{eqnarray*} f(n) \end{eqnarray*}$ exponentiell wächst, also im Grunde bestimmt durch $\begin{eqnarray*} \phi^{n+2} \end{eqnarray*}$ .

Diese Information, die ja auch in die Induktionsvoraussetzung eingeht, vernichtest du bereits in diesem Schritt

Zitat:

Original von Boom
$\begin{eqnarray*} f(n+1)\leq \beta + \gamma(\phi^{n+2}-1) + f(n-1) \end{eqnarray*}$
$\begin{eqnarray*} f(n+1)\leq \beta + \gamma(\phi) + f(n-1) \end{eqnarray*}$

vollständig - so kann das ja nun überhaupt nicht klappen. unglücklich

unglücklich

Das bleibt also erstmal erhalten, tatsächlich sollte die Induktionsvoraussetzung nicht nur für $\begin{eqnarray*} n \end{eqnarray*}$ , sondern auch für $\begin{eqnarray*} n-1 \end{eqnarray*}$ eingesetzt werden (was übrigens bedeutet, dass du n=1 im Induktionsanfang "nachrüsten" musst):

$\begin{eqnarray*} f(n+1)\leq \beta + \gamma(\phi^{n+2}-1) + \gamma(\phi^{n-1+2}-1) \leq \gamma ( 1 + \phi^{n+2} - 1 + \phi^{n+1} - 1) \end{eqnarray*}$ ,

letzteres $\begin{eqnarray*} \leq \end{eqnarray*}$ wegen $\begin{eqnarray*} \beta\leq \gamma \end{eqnarray*}$ .

05.06.2014, 17:14

Boom

Auf diesen Beitrag antworten »

mein Fehler. Es heißt ja schließlich $\begin{eqnarray*} \phi = \phi^{2} -1 \end{eqnarray*}$ und nicht $\begin{eqnarray*} \phi = \phi^{n+2} -1 \end{eqnarray*}$ .
Des Weiteren müsste ich ja den I.S. für n+2 beweisen, nicht für n+1, da ich ja n = 1 im I.A. bewiesen habe, oder etwa nicht?

Kannst du mir eventuell genauer erklären, wieso du am ende $\begin{eqnarray*} \leq \gamma (1+\phi^{n+2}-1 + \phi^{n+1}-1) \end{eqnarray*}$ hinzufügt?

Mir ist zwar bewusst, dass Beta kleiner gleich Gamma ist. Aber von selbst wäre ich auf sowas nicht gekommen, sprich die Funktion auf diese Weise zu erweitern.

05.06.2014, 17:40

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Boom
Kannst du mir eventuell genauer erklären, wieso du am ende $\begin{eqnarray*} \leq \gamma (1+\phi^{n+2}-1 + \phi^{n+1}-1) \end{eqnarray*}$ hinzufügt?

Noch genauer? Da fällt mir allenfalls noch $\begin{eqnarray*} \beta\leq \gamma = \gamma\cdot 1 \end{eqnarray*}$ ein, und dann kannst du aus allen Termen rechts den Faktor $\begin{eqnarray*} \gamma \end{eqnarray*}$ ausklammern. Wüsste nicht, was es da sonst noch zu erklären gibt.

05.06.2014, 17:59

Boom

Auf diesen Beitrag antworten »

Die eigentliche Funkion lautet ja
$\begin{eqnarray*} f(n+2) \leq \beta + f((n+2)-1) + f((n+2)-2) \end{eqnarray*}$

Was ich mich dann halt gefragt habe ist, wieso man das $\begin{eqnarray*} \leq \gamma (1+\phi^{n+2}-1 + \phi^{n+1}-1) \end{eqnarray*}$ anfügen kann, sodass die Funktion am Ende zwei " $\begin{eqnarray*} \leq \end{eqnarray*}$ " hat, obwohl die Funktion zu Anfang ja nur einen hat.

Bei einer Induktion bin ich bisher immer davon ausgegangen, dass man die Funktion nicht nur mit der I.V. "verändern" darf. Hier haben wir ja jetzt aber eine "kleiner Gleich" hinzugefügt.... verwirrt

verwirrt

05.06.2014, 18:10

HAL 9000

Auf diesen Beitrag antworten »

Wenn ich eins nicht leiden kann, dann wenn nicht gelesen wird:

Zitat:

Original von HAL 9000
tatsächlich sollte die Induktionsvoraussetzung nicht nur für $\begin{eqnarray*} n \end{eqnarray*}$ , sondern auch für $\begin{eqnarray*} n-1 \end{eqnarray*}$ eingesetzt werden (was übrigens bedeutet, dass du n=1 im Induktionsanfang "nachrüsten" musst)

Nachfragen gern - aber nicht so tun, als wäre gar nichts dazu geschrieben worden.

05.06.2014, 18:26

Boom

Auf diesen Beitrag antworten »

da ich ja f(1) bereits im I.A bewiesen habe, dachte ich, dass man im I.S. auf das n-1 im I.S. "verzichten" könne, da f(0) und f(1) im I.A. bewiesen worden sind und somit nur noch n+2 beweisen werden muss.

Aus dieser Annahme resultiert meine Frage.

Ich wollte auf keinen Fall dir unsterstellen, dass du gewisse Informationen nicht geschrieben hast unglücklich

unglücklich

05.06.2014, 18:34

HAL 9000

Auf diesen Beitrag antworten »

Man startet mit zwei Werten, und darf dann "als Belohnung" im Induktionsschritt nicht nur auf den letzten zurückliegenden, sondern auf die beiden letzten zurückliegenden Werte als Induktionsvoraussetzung zurückgreifen. Ist ein häufig praktiziertes Vorgehen, und durch das Induktionsprinzip auch seriös abgedeckt.

05.06.2014, 23:08

Boom

Auf diesen Beitrag antworten »

ich habe mich heute mit einem Komillitonen zusammen gesetzt und haben folgendes zustande gebracht:

$\begin{eqnarray*} f(n+1) \leq \beta +f((n+1)-1) + f((n+1)-2) \end{eqnarray*}$
$\begin{eqnarray*} f(n+1) \leq \beta +f(n) + f(n-1) \end{eqnarray*}$
$\begin{eqnarray*} f(n+1) \leq \beta +\gamma (\phi^{n+2}-1) + \gamma (\phi^{(n-1)+2}-1) \end{eqnarray*}$
$\begin{eqnarray*} f(n+1) \leq \gamma +\gamma (\phi^{n+2}-1) + \gamma (\phi^{(n-1)+2}-1) \end{eqnarray*}$
$\begin{eqnarray*} f(n+1) \leq \gamma (\phi^{n+2}-1 + \phi^{(n-1)+2}-1 +1) \end{eqnarray*}$
$\begin{eqnarray*} f(n+1) \leq \gamma (\phi^{n+2} + \phi^{n+1}-1 ) \end{eqnarray*}$
$\begin{eqnarray*} f(n+1) \leq \gamma (\phi^{n+3}-1 ) \end{eqnarray*}$

Aber scheint ja nicht ganz zu stimmen, da das End ergebnis $\begin{eqnarray*} f(n+1) \leq \gamma (\phi^{n+2}-1 ) \end{eqnarray*}$ sein sollte und nicht $\begin{eqnarray*} f(n+1) \leq \gamma (\phi^{n+3}-1 ) \end{eqnarray*}$

verwirrt

verwirrt

05.06.2014, 23:12

Boom

Auf diesen Beitrag antworten »

Korrektur:

Wenn ich $\begin{eqnarray*} f(n+1) \leq \gamma (\phi^{(n+3}-1 ) \end{eqnarray*}$ umforme in $\begin{eqnarray*} f(n+1) \leq \gamma (\phi^{(n+1)+2}-1 ) \end{eqnarray*}$ , gekomme ich doch das richtige herraus. smile

smile

Frage ist halt, ob es auch wirklich so richtig ist..... verwirrt

verwirrt

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »