Rekursive Funktion - vollständige Induktion

15.01.2020, 17:19	PandaAI	Auf diesen Beitrag antworten »
Rekursive Funktion - vollständige Induktion Meine Frage: Hi, ich sitze vor ein paar Aufgaben und bin mir dabei nicht 100%ig sicher, wie der Lösungsweg auszusehen hat. Ich weiß was rauskommen soll und habe mir das Ergebnis mehr oder weniger zurechtgeschustert, aber ob das einer kritischen Prüfung standhält bezweifle ich. Hier die Aufgabe: Die Funktion f sind rekursiv auf alle Zweierpotenzen definiert, also für alle n, die sich als $\begin{eqnarray} 2^{k} \end{eqnarray}$ schreiben lassen, für ein k $\begin{eqnarray} \geq \end{eqnarray}$ 0. Gegeben ist dabei: f(1) = 0 f(n) = 2f( $\begin{eqnarray} \frac{n}{2} \end{eqnarray}$ )+n Zeigen sie durch Induktion über k: f(n) = nlogn => Hier ist der 2er Logarithmus gemeint. Meine Ideen:* Okay, folgendes habe ich mir dabei gedacht. Induktionsanfang für n = 1: f(1) = 0 \|\| f(1) = 1log1 = 0 stimmt also schonmal überein. Induktionsschritt: nun müsste ich ja zeigen, dass f(k+1) = (k+1)log(k+1) ist. jetzt habe ich mir gedacht n= $\begin{eqnarray} 2^{k} \end{eqnarray}$ , wenn man hier nun k+1 einsetzt gilt: 2n = $\begin{eqnarray} 2^{k+1} \end{eqnarray}$ . aber jetzt komm ich nicht mehr weiter, wie genau führe ich den Beweis jetzt weiter? Wäre über Denkanstöße sehr dankbar, mit einem kleinen Schubser komm ich vlt noch auf den richtigen Weg. Vielen Dank euch!
15.01.2020, 22:10	jester.	Auf diesen Beitrag antworten »
Der Induktionsanfang ist natürlich in Ordnung. Verwende als Induktionsvoraussetzung "Für jede Zweierpotenz $\begin{eqnarray} 1\leq x < n \end{eqnarray}$ gelte die zu zeigende Aussage $\begin{eqnarray} f(x) = x \log (x) \end{eqnarray}$ ". Um nun im Induktionsschritt die Gleichung für $\begin{eqnarray} f(n) \end{eqnarray}$ nachzurechnen, verwende die Definition $\begin{eqnarray} f(n)=2f\left(\frac{n}{2}\right)+n \end{eqnarray}$ . Dies ist gemäß Induktionsvoraussetzung gleich $\begin{eqnarray} 2\left(\frac{n}{2}\right)\log\left(\frac{n}{2}\right)+n \end{eqnarray}$ . Nun einfach weiterrechnen bis das Gewünschte da steht. Alternativ kann man einen Umweg gehen, der einen "klassischeren" Induktionsschluss $\begin{eqnarray} k\to k+1 \end{eqnarray}$ ermöglicht, indem man explizit mit Zweierpotenzen $\begin{eqnarray} 2^k \end{eqnarray}$ arbeitet. In der obigen Variante ist $\begin{eqnarray} n \end{eqnarray}$ eben die ganze Zeit implizit eine Zweierpotenz.
26.01.2020, 09:45	PandaAI	Auf diesen Beitrag antworten »
ich muss zugeben, das läuft irgendwie noch nicht so, wie es laufen sollte. Habe mal die nächste Aufgabe auf dem Aufgabenblatt versucht. Hier gilt selbiges wie schon bei der oben geposteten Aufgabe, n= $\begin{eqnarray} 2^{k} \end{eqnarray}$ Hier gilt: g(1) = 2 g(n) = 2g( $\begin{eqnarray} \frac{n}{2} \end{eqnarray}$ )+ $\begin{eqnarray} n^{2} \end{eqnarray}$ zu zeigen ist, dass g(n) = 2 $\begin{eqnarray} n^{2} \end{eqnarray}$ Induktionsanfang passt soweit, problematisch ist der Induktionsschritt folgendes habe ich gemacht: Da es für k gezeigt ist, muss es nun noch für k->k+1 gezeigt werden: g( $\begin{eqnarray} 2^{k+1} \end{eqnarray}$ ) = 2g( $\begin{eqnarray} 2^{k} \end{eqnarray}$ )+ $\begin{eqnarray} (2^{k+1})^{2} \end{eqnarray}$ = 22 $\begin{eqnarray} (2^{k})^{2} \end{eqnarray}$ + $\begin{eqnarray} (2^{k+1})^{2} \end{eqnarray}$ = $\begin{eqnarray} 2^{2k+3} \end{eqnarray}$ das galt es ja zu zeigen, da g(n)= $\begin{eqnarray} 2n^{2} \end{eqnarray}$ = $\begin{eqnarray} 2(2^{k})^{2} \end{eqnarray}$ und g(n+1) = g( $\begin{eqnarray} 2^{k+1} \end{eqnarray}$ ) = $\begin{eqnarray} 2(2^{k+1})^{2} \end{eqnarray}$ = $\begin{eqnarray} 2^{2k+3} \end{eqnarray}$ so habe ich mir das gedacht, macht das so überhaupt annähernd Sinn? lg EDIT: Latex korrigiert (klarsoweit)

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »