Rekurrenzgleichung mit Hilfe vollständiger Induktion beweisen

09.03.2015, 11:51

Elaice

Rekurrenzgleichung mit Hilfe vollständiger Induktion beweisen

Hallo,

ich hänge gerade an einer Aufgabe, in der eine Rekurrenzgleichung mit Hilfe von vollständiger Induktion bewiesen werden soll.
Folgende Aufgabe:

[attach]37424[/attach]

Ich versteht den Induktionsschritt überhaupt nicht und weiß nicht genau wie ich die Gleichung auflösen soll.
Im Induktionsschritt würde ich folgendes beweisen wollen:
$\begin{eqnarray*} 2^{\frac{n-1}{3})} + 2^{\frac{n-2}{3}} + 2 >= 2^{{n+1}{3}} \end{eqnarray*}$

Was muss ich denn für t(n-2) bzw. t(n-3) einsetzen?

Leider komme ich hier auf keine richtige Lösung. Kann mir jemand auf die Sprünge helfen? Ich glaube ich habe irgendetwas bei der Induktion von Rekurrenzgleichungen nicht verstanden..

09.03.2015, 15:16

HAL 9000

Auf diesen Beitrag antworten »

RE: Rekurrenzgleichung mit Hilfe vollständiger Induktion beweisen

Zitat:

Original von Elaice
Im Induktionsschritt würde ich folgendes beweisen wollen:
$\begin{eqnarray*} 2^{\frac{n-1}{3})} + 2^{\frac{n-2}{3}} + 2 >= 2^{{n+1}{3}} \end{eqnarray*}$

Anscheinend meinst du $\begin{eqnarray*} 2^{\frac{n-1}{3}} + 2^{\frac{n-2}{3}} + 2 \geq 2^{\frac{n+1}{3}} \end{eqnarray*}$ . Hinreichend dafür wäre bereits $\begin{eqnarray*} 2^{\frac{n-1}{3}} + 2^{\frac{n-2}{3}} \geq 2^{\frac{n+1}{3}} \end{eqnarray*}$ , und das lässt sich problemlos nachweisen.

Neue Frage »

Antworten »

Rekurrenzgleichung mit Hilfe vollständiger Induktion beweisen

Verwandte Themen