Euklidischer-Algorithmus: Beweis Ungleichung Nachfolger

10.11.2013, 14:54

sleeepyjack

Euklidischer-Algorithmus: Beweis Ungleichung Nachfolger

Meine Frage:
Hallo zusammen!

Gestellt ist folgende Aufgabe:

Beim Bestimmen des ggT zweier natürlicher Zahlen $\begin{eqnarray*} a_{0}>a_{1}>0 \end{eqnarray*}$ mit dem Euklidischen-Algorithmus entstehen

die Zahlen $\begin{eqnarray*} a_{0}>a_{1}>..>a_{n}=ggT(a_{0},a_{1}) \end{eqnarray*}$ .

Zeigen Sie: $\begin{eqnarray*} a_{k}a_{k+1} < \frac{a_{k-1}a_{k}}{2} \end{eqnarray*}$ mit $\begin{eqnarray*} 1\leq k\leq n-1 \end{eqnarray*}$

Zur Erinnerung nochmal der Euklidische-Algorithmus:

euklid(a,b){
IF(b==0)THEN
return a;
ELSE
return euklid(b,a mod b);
ENDIF
}

Danke für die Hilfe im Voraus!

Meine Ideen:
Mein Ansatz ist, dass ich zuerst versuche $\begin{eqnarray*} a_{k-1} \end{eqnarray*}$ zu ersetzen. Hierzu lässt sich aus dem Algorithmus ableiten, dass

$\begin{eqnarray*} a_{k+1} = a_{k-1\ } mod\ a_{k} \end{eqnarray*}$ ist und somit $\begin{eqnarray*} a_{k-1} = a_{k}*c+a_{k+1}\ \ ,\ c\in \mathbb N \end{eqnarray*}$

Dies ergibt folgende Ungleichung: $\begin{eqnarray*} a_{k}a_{k+1} < \frac{a_{k}^{2}c+a_{k+1}a_{k}}{2} \end{eqnarray*}$

Nun lässt sich hieraus folgendes ableiten: Für $\begin{eqnarray*} a_{k}>0 \end{eqnarray*}$ gilt $\begin{eqnarray*} a_{k+1}<c*a_{k} \end{eqnarray*}$

Leider fehlt mir ab hier das Gehirnschmalz um die Ungleichung zu belegen. Weiß vielleicht jemand wie es weitergehen könnte?

10.11.2013, 15:38

Captain Kirk

Auf diesen Beitrag antworten »

Hallo,

ich würd hier folgendes machen:
Da $\begin{eqnarray*} c\ge 1 \end{eqnarray*}$ und $\begin{eqnarray*} a_{i+1}<a_{i} \end{eqnarray*}$ für belibige i folgt aus

Zitat:

$\begin{eqnarray*} a_{k-1} = a_{k}*c+a_{k+1}\ \ ,\ c\in \mathbb N \end{eqnarray*}$ (*)

dass $\begin{eqnarray*} a_{k-1}<2ca_k \end{eqnarray*}$ .
Ersetze $\begin{eqnarray*} a_{k+1} \end{eqnarray*}$ mittels (*) im Term $\begin{eqnarray*} a_{k+1}a_k \end{eqnarray*}$ und setze die obere Ungleichung ein.

Neue Frage »

Antworten »

Euklidischer-Algorithmus: Beweis Ungleichung Nachfolger

Verwandte Themen