Vollständige Induktion bei einer Rekurrenzgleichung

09.11.2012, 13:23

MadCookieMonster

Vollständige Induktion bei einer Rekurrenzgleichung

Hallo Leute,
eigentlich tue ich mich nicht so schwer mit Induktionsbeweisen aber bei dieser Rekurrenzgleichung komme ich irgendwie nicht weiter.

Folgende Aufgabe:
Beweisen Sie durch Induktion die Lösung $\begin{eqnarray*} B_{N} = \left[log N\right] + 1 \end{eqnarray*}$ für die Rekurrenzgleichung

$\begin{eqnarray*} B_{N} = B_{\left[\frac{N}{2} \right] } + 1 \end{eqnarray*}$ für $\begin{eqnarray*} N \geq 2 \end{eqnarray*}$
$\begin{eqnarray*} B_{1} = 1 \end{eqnarray*}$

(Mit $\begin{eqnarray*} \left[...\right] \end{eqnarray*}$ ist das Aufrunden gemeint.)

Mein Ansatz:

Zunächst der Induktionsanker:
Für $\begin{eqnarray*} N = 2 \end{eqnarray*}$ :

$\begin{eqnarray*} B_{2} = N_{\left[\frac{2}{2} \right]} + 1 = 2 \end{eqnarray*}$

und
$\begin{eqnarray*} B_{2} = \left[log 2 \right] + 1 = 2 \end{eqnarray*}$

Der Induktionsanker passt also.

Nun die Induktionsannahme:

Nun muss ich zeigen, dass wenn $\begin{eqnarray*} B_{N} \end{eqnarray*}$ für ein $\begin{eqnarray*} N \end{eqnarray*}$ gültig ist, ich daraus folgern kann, dass $\begin{eqnarray*} B_{N+1} \end{eqnarray*}$ wahr ist.

Als letztes der Induktionsschritt:

$\begin{eqnarray*} B_{N + 1} = B_{\left[\frac{N+1}{2}\right]} +1 \end{eqnarray*}$

An dieser Stelle komme ich nicht weiter.
Ich weiß nicht, wie ich $\begin{eqnarray*} B_{\left[\frac{N+1}{2}\right]} \end{eqnarray*}$ auseinander ziehen kann, sodass ich einen Teil durch $\begin{eqnarray*} B_{N} = \left[log N\right] + 1 \end{eqnarray*}$ ersetzen kann.

Ich habe überlegt, ob man $\begin{eqnarray*} B_{\left[\frac{N+1}{2}\right]} \end{eqnarray*}$ zu $\begin{eqnarray*} B_{\left[\frac{N}{2}\right]} + B_{\left[\frac{1}{2}\right]} \end{eqnarray*}$ umformen darf. verwirrt

Hat irgendwer nen Tipp?

MCM

09.11.2012, 13:29

HAL 9000

Auf diesen Beitrag antworten »

Anscheinend meinst du mit $\begin{eqnarray*} \log \end{eqnarray*}$ den binären Logarithmus. Es wäre günstig, das gleich so zu kennzeichnen, d.h. deine Behauptung lautet $\begin{eqnarray*} B_N = \left\lceil \log_2( N) \right\rceil + 1 \end{eqnarray*}$ .

09.11.2012, 13:42

MadCookieMonster

Auf diesen Beitrag antworten »

Hmm in der Aufgabenstellung stand nicht wirklich um welchen Logarithmus es sich handelt. Ursprünglich stammt die Aufgabe aus der Informatik.
Ich habe jetzt mit dem natürlichen Logarithmus gerechnet, weil bei uns auch in Mathe in eigentlich allen Fällen mit $\begin{eqnarray*} log (N) \end{eqnarray*}$ der natürliche logarithmus gemeint war.

Aber sicher bin ich mir da gerade irgendwie nicht...

MCM

09.11.2012, 13:49

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von MadCookieMonster
Ich habe jetzt mit dem natürlichen Logarithmus gerechnet

Mit dem wäre die Behauptung bereits bei $\begin{eqnarray*} N=5 \end{eqnarray*}$ falsch: Es ist nach Rekursion

$\begin{eqnarray*} B_5 = B_3+1 = B_2+2 = B_1+3 = 4 \end{eqnarray*}$ ,

aber $\begin{eqnarray*} \lceil \ln(5) \rceil+1 = \lceil 1.61 \rceil+1 = 3 \end{eqnarray*}$ .

09.11.2012, 14:25

MadCookieMonster

Auf diesen Beitrag antworten »

Okay habe gerade nachgefragt!
Es ist wirklich der binäre Logarithmus gemeint!

09.11.2012, 17:00

HAL 9000

Auf diesen Beitrag antworten »

Du solltest dir klarmachen, dass die Behauptung umgeformt so geschrieben werden kann:

Zitat:

Für $\begin{eqnarray*} k\in\mathbb{N} \end{eqnarray*}$ sowie $\begin{eqnarray*} 2^{k-1} < N \leq 2^k \end{eqnarray*}$ gilt $\begin{eqnarray*} B_N = k+1 \end{eqnarray*}$ .

Das lässt sich dann durch vollständige Induktion über $\begin{eqnarray*} k \end{eqnarray*}$ beweisen.

09.11.2012, 17:20

MadCookieMonster

Auf diesen Beitrag antworten »

Hmm iwie komm ich da nicht ganz mit. verwirrt

Ich bin ja noch nicht so weit, dass ich meine Induktionsannahme in meinem Induktionsschritt verwenden darf..
Oder habe ich da irgendwas übersehen?

MCM

09.11.2012, 17:45

HAL 9000

Auf diesen Beitrag antworten »

Wenn du denn partout bei deiner Induktion über $\begin{eqnarray*} N \end{eqnarray*}$ bleiben willst (statt meinen Vorschlag zu überdenken):

Ein Induktionsschritt $\begin{eqnarray*} N\to N+1 \end{eqnarray*}$ wird dir da nie gelingen, sondern allenfalls einer der Form $\begin{eqnarray*} (\leq N) \to N+1 \end{eqnarray*}$ . Augenzwinkern

09.11.2012, 17:54

MadCookieMonster

Auf diesen Beitrag antworten »

Okay ich bin gerne für Vorschläge offen. Augenzwinkern

Ich soll also anstatt $\begin{eqnarray*} N \end{eqnarray*}$ dein $\begin{eqnarray*} k \end{eqnarray*}$ mit den genannten Eigenschaften verwenden?

Ich versuche gerade die Induktion neu aufzuschreiben, aber irgendwie bin ich schon beim Induktionsanker verwirrt..

Dann wird ja erstmal aus meiner Startfunktion:

$\begin{eqnarray*} B_{k} = B_{\left[\frac{k}{2} \right] } +1 \end{eqnarray*}$ oder?

Iwie verstehe ich nicht wirklich, wie ich das neue k am Anfang verwenden muss oder ich stelle mich gerade extrem blöd an..

MCM

09.11.2012, 18:03

HAL 9000

Auf diesen Beitrag antworten »

Vorschlag: Berechne mal die ersten paar $\begin{eqnarray*} B_N \end{eqnarray*}$ streng nach gegebener Rekursionsformel, also z.B. für $\begin{eqnarray*} N=1,2,\ldots,10 \end{eqnarray*}$ . Damit du überhaupt erstmal ein "Gefühl" für diese Folge kriegst, das geht dir nämlich anscheinend hier völlig ab.

Neue Frage »

Antworten »

Vollständige Induktion bei einer Rekurrenzgleichung

Verwandte Themen