Rekursionsformel mit vollständiger Induktion beweisen

11.07.2011, 17:13

churks

Rekursionsformel mit vollständiger Induktion beweisen

Die Aufgabenstellung lautet wie folgt:

Gegeben sei die Rekursionsformel:
$\begin{eqnarray*} T(1)=k, T(n)=3T\left (\frac{n}{2}\right)+kn \end{eqnarray*}$ , für n > 1

Beweisen Sie per vollständiger Induktion, dass gilt:
$\begin{eqnarray*} T(n)=3kn^{log_{2}(3)}-2kn \end{eqnarray*}$

Hinweis: Gehen Sie o.B.d.A. davon aus, dass n eine Potenz von 2 ist!

Als Induktionsanfang habe ich n=2 gewählt und es kommt bei beiden 5k raus.
Damit also erledigt.

Jetzt weiß ich aber nicht wie ich weiter vorgehen soll. Irgendwie komme ich nicht mit der Funktion klar, sowie mit der Bedingung das n eine Potenz von 2 sein soll. Kann ich dann trozdem immer noch (n+1) schreiben? Desweiteren weiß ich nicht ob ich die Rekursionsformel in eine Summenformel umformen muss.

11.07.2011, 18:19

Alive-and-well

Auf diesen Beitrag antworten »

RE: Rekursionsformel mit vollständiger Induktion beweisen
Du musst dir überlegen was in diesem Fall das "n+1" ist. Da ja die nächste Zahl für die diese Formel gilt, nicht die nächste natürliche Zahl ist sondern die nächste zweierpotenz.

12.07.2011, 10:20

churks

Auf diesen Beitrag antworten »

Müsste ich also anstatt (n+1) einfach (2^(n+1)) einsetzen?

Der IS würde dann bei mir so aussehen:
$\begin{eqnarray*} T(n)=3T\left(1\right)+2k+3T\left(\frac{ 2^{(n+1)} }{2}\right)+k(2^{(n+1)})=3k\left(2^{(n+1)}\right)^{log_{2}(3)}-2k(2^{(n+1)}) \end{eqnarray*}$

12.07.2011, 10:59

René Gruber

Auf diesen Beitrag antworten »

Mal $\begin{eqnarray*} n \end{eqnarray*}$ , mal $\begin{eqnarray*} 2^n \end{eqnarray*}$ , da musst du ja durcheinander kommen - wie eben in der Formel...

Trenn das doch mal sauber, auch von den verwendeten Symbolen her! Wenn du die Behauptung für alle Zweierpotenzen $\begin{eqnarray*} n=2^m \end{eqnarray*}$ beweisen willst, dann schreib sie doch erstmal für diese Zweierpotenzen auf, und vereinfache wenn möglich:

$\begin{eqnarray*} T\left( 2^m \right) = 3k \left( 2^m \right)^{\log_2(3)} - 2k\cdot 2^m = 3k \left( 2^{\log_2(3)} \right)^m - k\cdot 2^{m+1} = k\left( 3^{m+1} - 2^{m+1} \right) \end{eqnarray*}$

So sieht das ganze doch schon viel freundlicher aus. Und jetzt diese Formel beweisen, durch Vollständige Induktion über $\begin{eqnarray*} m \end{eqnarray*}$ mit Start $\begin{eqnarray*} m=0 \end{eqnarray*}$ .

12.07.2011, 13:53

Flo123456789

Auf diesen Beitrag antworten »

Kann hier mal irgendein fähiger Mensch die Rechenschritte posten?

12.07.2011, 14:17

churks

Auf diesen Beitrag antworten »

Also gut, jetzt nochmal ganz von Vorne:
Induktionsanfang:
$\begin{eqnarray*} T(2)=3T\left (1\right)+k2=3k+2k=5k \end{eqnarray*}$
und:
$\begin{eqnarray*} T(2)=3k2^{log_{2}(3)}-2k2=5k \end{eqnarray*}$

Behauptung Stimmt also für den Fall n=2:
Nun nehme ich die Umformung der 2. Formel von René Gruber:
(glaub da wurde einmal im mittleren Bereich ein +1 hinter dem dem ^m vergessen)
$\begin{eqnarray*} T\left( 2^m \right) = 3k \left( 2^m \right)^{\log_2(3)} - 2k\cdot 2^m = 3k \left( 2^{\log_2(3)} \right)^{m+1} - k\cdot 2^{m+1} = k\left( 3^{m+1} - 2^{m+1} \right) \end{eqnarray*}$

Diese Formel muss ich dann doch jetzt mit der 1. Formel mit n+1=> m=2 gleichsetzen.
Die erste Formel lautet ja dann in dem Fall für den IS:
$\begin{eqnarray*} T(2^{m+1})=3T\left (\frac{2^{m+1}}{2}\right)+k\cdot 1^{m+1} \end{eqnarray*}$

Der Part : $\begin{eqnarray*} T\left (\frac{2^{m+1}}{2}\right) \end{eqnarray*}$
bedeutet doch nix anderes als die Summe der vorigen n, da dürfte ich dann doch
also das Ergebnis aus m=1 einsetzen oder nicht?
Das würde dann so ausssehen:
$\begin{eqnarray*} T(2^{m+1})=3\cdot\left (5k\right)+k\cdot 1^{m+1} \end{eqnarray*}$

Und jetzt muss ich dann nur noch diese 1. Formel mit der 2. umgeformten Formel gleichsetzen, richtig?

12.07.2011, 14:19

René Gruber

Auf diesen Beitrag antworten »

Zitat:

Original von churks
(glaub da wurde einmal im mittleren Bereich ein +1 hinter dem dem ^m vergessen)

Dein Glaube in allen Ehren, aber da wurde nichts vergessen.

Zitat:

Original von churks
Die erste Formel lautet ja dann in dem Fall für den IS:
$\begin{eqnarray*} T(2^{m+1})=3T\left (\frac{2^{m+1}}{2}\right)+k\cdot 1^{m+1} \end{eqnarray*}$

Nochmals nein. Sie lautet

$\begin{eqnarray*} T(2^{m+1})=3T\left (\frac{2^{m+1}}{2}\right)+k\cdot 2^{m+1} \end{eqnarray*}$

Zitat:

Original von churks
Der Part : $\begin{eqnarray*} T\left (\frac{2^{m+1}}{2}\right) \end{eqnarray*}$
bedeutet doch nix anderes als die Summe der vorigen n,

Richtig.

Zitat:

Original von churks
da dürfte ich dann doch also das Ergebnis aus m=1 einsetzen oder nicht?

"Oder nicht" ist zutreffend: Wie kommst du darauf, das "vorige" mit m=1 gleichzusetzen. Das lässt auf tiefschürende Defizite im Verständnis der Vollständigen Induktion schließen:

Der Induktionsschritt lautet doch $\begin{eqnarray*} m\to m+1 \end{eqnarray*}$ , und nicht etwa $\begin{eqnarray*} 1\to m+1 \end{eqnarray*}$ (wie man deine letzte Anmerkung übersetzen müsste)

P.S.: Abgesehen davon würde ich als Induktionsanfang $\begin{eqnarray*} m=0 \end{eqnarray*}$ statt $\begin{eqnarray*} m=1 \end{eqnarray*}$ wählen. $\begin{eqnarray*} m=1 \end{eqnarray*}$ zu nehmen ist kein Fehler, aber umständlicher und zudem unnötig beschränkend: Denn dann hat man die Aussage "nur" für $\begin{eqnarray*} m\geq 1 \end{eqnarray*}$ beweisen statt für alle $\begin{eqnarray*} m\geq 0 \end{eqnarray*}$ , was zugegeben nicht den Riesenunterschied ausmacht. Augenzwinkern

12.07.2011, 14:44

churks

Auf diesen Beitrag antworten »

Oh Sorry, jetzt hab ich deine Umformung verstanden.
Und das mit dem 1^(m+1) anstelle von 2^(m+1) in der 1. Formel muss nen Tippfehler meinerseits gewesen sein.

Also weiter im Text:
Mit dem: $\begin{eqnarray*} T\left (\frac{2^{m+1}}{2}\right) \end{eqnarray*}$ meinte ich nur, das ich das Ergebnis von m=1 da einsetzen kann aber die ganze Formel beibehalte, das ist dann doch m+1. Also:

$\begin{eqnarray*} T(2^{m+1})=3\cdot 5k+k\cdot 2^{m+1} \end{eqnarray*}$

12.07.2011, 14:48

René Gruber

Auf diesen Beitrag antworten »

Nochmals nein, du hast meinen Einwurf nicht beachtet: Du setzt das Ergebnis für $\begin{eqnarray*} m \end{eqnarray*}$ ein (d.h. die Induktionsvoraussetzung), nicht nur für $\begin{eqnarray*} m=1 \end{eqnarray*}$ . unglücklich

Also:

$\begin{eqnarray*} T\left(2^{m+1}\right) = 3T\left(2^{m}\right) + k2^{m+1} \stackrel{IV}{=} 3k\left(3^{m+1}-2^{m+1}\right) + k2^{m+1} = \ldots \end{eqnarray*}$

Neue Frage »

Antworten »

Rekursionsformel mit vollständiger Induktion beweisen

Verwandte Themen