Rekursionsgleichung per Induktion Lösen

05.07.2016, 19:14	rth	Auf diesen Beitrag antworten »
Rekursionsgleichung per Induktion Lösen Meine Frage: Hallo ich sitze vor einer Aufgabe bei der ich eine Rekursionsgleichung. Ich soll per vollständiger Induktion zeigen, dass es ein $\begin{eqnarray} c > 1 \end{eqnarray}$ gibt, sodass für alle Potenzen von 3 $\begin{eqnarray} n = 3^k \end{eqnarray}$ mit $\begin{eqnarray} k \in \mathbb N \end{eqnarray}$ die Ungleichung $\begin{eqnarray} T(n) \leq c \cdot n \end{eqnarray}$ erfüllt ist. Die Rekursionsgleichung lautet: $\begin{eqnarray} T(1) = 4 \end{eqnarray}$ $\begin{eqnarray} T(n) = 2 \cdot T(\frac{n}{3})+21 \end{eqnarray}$ Das Mastertheorem darf dabei leider nicht verwendet werden. Meine Ideen: Meine Vermutung ist, dass durch das $\begin{eqnarray} T(\frac{n}{3}) \end{eqnarray}$ in der Formel ja etwas Logarithmisches entstehen muss. Und bei $\begin{eqnarray} 2log(n) + const \end{eqnarray}$ könnte man schnell erkennen, dass $\begin{eqnarray} 2log(n) +const \leq c \cdot n \end{eqnarray}$ gilt (vorausgesetzt $\begin{eqnarray} c \geq const \end{eqnarray}$ ). Leider ist das nur so ein Gedanke mit dem ich nicht so richtig etwas anfangen kann. Ich hoffe ihr könnt mir den ein oder anderen Denkanstoß geben, damit ich da weiterkomme (vl. bin ich ja jetzt schon ganz falsch am Weg).
05.07.2016, 19:26	HAL 9000	Auf diesen Beitrag antworten »
Es geht um die Werte $\begin{align} T\left(3^k\right) \end{align}$ , da kommt man z.B. durch die Substitution $\begin{align} a_k=T\left(3^k\right)+21 \end{align}$ zur rekursiven Folge $\begin{align} a_0 &= 25\\ a_k &= 2a_{k-1} \end{align}$ . Die ist nun wirklich nicht schwer in eine explizite Form überführbar.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »