Euklid-Algorithmus und die Fibonacci-Folge

23.04.2018, 15:33

NicoBe

Euklid-Algorithmus und die Fibonacci-Folge

Hi,

ich habe folgendes Problem, bei dem ich nicht ganz weiter kommen. Es geht darum, folgenden Satz zu beweisen:

Es gelte:

Der Euklid Algorithmus wird $\begin{eqnarray*} k \geq 1 \end{eqnarray*}$ mal aufgerufen und es gelte x > y.

Zeige:

$\begin{eqnarray*} x \geq F_{k+2} \end{eqnarray*}$ und $\begin{eqnarray*} y \geq F_{k+1} \end{eqnarray*}$

mit

$\begin{eqnarray*} F_{n} \end{eqnarray*}$ - die n-te Fibonacci Zahl.

Mir fehlt absolut der Ansatz für diesen Beweis, hat jemand eine Idee?

LG,
Nico

23.04.2018, 15:49

HAL 9000

Auf diesen Beitrag antworten »

Schräg formuliert - gemeint ist wohl sinngemäß folgende Behauptung:

Zitat:

Der auf $\begin{eqnarray*} x,y \end{eqnarray*}$ mit $\begin{eqnarray*} x>y>0 \end{eqnarray*}$ angewandte Euklidische Algorithmus benötigt $\begin{eqnarray*} k \end{eqnarray*}$ Iterationsschritte bis zum Ergebnis. Man zeige, dass dann $\begin{eqnarray*} x\geq F_{k+2} \end{eqnarray*}$ und $\begin{eqnarray*} y\geq F_{k+1} \end{eqnarray*}$ gelten muss.

23.04.2018, 16:09

NicoBe

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Schräg formuliert - gemeint ist wohl sinngemäß folgende Behauptung:

Zitat:

Ja, genau das ist gemeint. (Y)

23.04.2018, 16:40

HAL 9000

Auf diesen Beitrag antworten »

Naja, der Beweis geht sehr gut per vollständiger Induktion über $\begin{eqnarray*} k \end{eqnarray*}$ . Ich gehe mal nur im Detail auf den Start des Induktionsschritts $\begin{eqnarray*} k\to (k+1) \end{eqnarray*}$ ein:

Dort wendet man einen (den ersten!) Euklid-Algorithmus-Schritt auf das Paar $\begin{eqnarray*} (x,y) \end{eqnarray*}$ an. Der besteht in der Rechnung $\begin{eqnarray*} r:= x-k\cdot y \end{eqnarray*}$ , wobei man $\begin{eqnarray*} k:=\left\lfloor \frac{x}{y}\right\rfloor \end{eqnarray*}$ setzt, es entsteht das neue Paar $\begin{eqnarray*} (x',y')=(y,r) \end{eqnarray*}$ . Da wir nun aber davon ausgehen, dass $\begin{eqnarray*} (x,y) \end{eqnarray*}$ genau ( $\begin{eqnarray*} k+1) \end{eqnarray*}$ Schritte benötigt, wissen wir damit, dass $\begin{eqnarray*} (x',y') \end{eqnarray*}$ genau $\begin{eqnarray*} k \end{eqnarray*}$ Schritte benötigt. Wenn nun noch ordentlich begründet wird, dass $\begin{eqnarray*} x'>y'>0 \end{eqnarray*}$ gilt, darf auf $\begin{eqnarray*} (x',y') \end{eqnarray*}$ die Induktionsvoraussetzung angewandt werden...

23.04.2018, 17:12

NicoBe

Auf diesen Beitrag antworten »

Alles klar, vielen Dank schonmal!
Ich werde mich mal ransetzen. smile

LG,
Nico

Neue Frage »

Antworten »

Euklid-Algorithmus und die Fibonacci-Folge

Verwandte Themen