| |
| Autor |
  rekursive Laufzeitgleichung |
|
nakrama
Ehemals Aktiv 
Dabei seit: 12.05.2019
Mitteilungen: 47
 |  Themenstart: 2022-05-12
|
Hallo,
ich soll für die folgende rekursive Laufzeitgleichung einen Induktionsbeweis führen.
$T(n) = \begin{cases}
1 & n = 1 \\
8*T(n/2) + n^2*\sqrt(n) & n > 1
\end{cases}$
Zeigen soll ich, dass $T(n) = (2 + \sqrt(2))*n^3 - (1+\sqrt(2))*n^2*\sqrt(n)$ gilt.
Für n gilt, $n = 2^k, k \in \mathbb{N} $
Mir ist nicht ganz klar, inwiefern das funktionieren soll.
Die Induktion nach n:
IA: n = 1
$ T(1) = 1 = (2 + \sqrt(2))*1^3-(1+\sqrt(2))*1^2*\sqrt(1)$
IS: n -> n+1
Hier fällt der T(n) = 1 Fall ja raus.
Weiter als das komme ich jedoch nicht, da mir nicht klar ist, wie ich hier weiter machen soll um auf T(n) zu kommen, damit ich die Voraussetzung verwenden kann.
Danke im Voraus.
Mit freundlichen Grüßen
nakrama
|
 Profil
|
haegar90
Wenig Aktiv 
Dabei seit: 18.03.2019
Mitteilungen: 935
 | Beitrag No.1, eingetragen 2022-05-12
|
Vielleicht hilft es umzuschreiben ?
$T(2^k) = \begin{cases}
1 & k = 0 \\
8 \cdot T(2^{k-1}) + 2^{2k}\cdot 2^{k/2} & k > 0
\end{cases}$
|
Profil
|
Kuestenkind
Senior 
Dabei seit: 12.04.2016
Mitteilungen: 2568
| Beitrag No.2, eingetragen 2022-05-12
|
Huhu,
das ist ja einfache Algebra und ein wenig Potenzgesetze.
\(\displaystyle T\left(2^{k+1}\right)=8T\left(\frac{2^{k+1}}{2}\right)+\left(2^{k+1}\right)^2\sqrt{2^{k+1}}=8T\left(2^k\right)+\left(2^{k+1}\right)^2\sqrt{2^{k+1}}\stackrel{IV}{=}8\left(\left(2+\sqrt{2}\right)(2^k)^3-(1+\sqrt{2})(2^k)^2\sqrt{2^k}\right)+\left(2^{k+1}\right)^2\sqrt{2^{k+1}}=\ldots=(2+\sqrt{2})\left(2^{k+1}\right)^3
-(1+\sqrt{2})\left(2^{k+1}\right)^2\sqrt{2^{k+1}}\)
Gruß,
Küstenkind
edit: Tippfehler verbessert. PS: Schreibe \cdot und \sqrt{...} in \(\LaTeX\) für \(\cdot\) bzw. \(\sqrt{...}\)
|
Profil
|
nakrama
Ehemals Aktiv
Dabei seit: 12.05.2019
Mitteilungen: 47
| Beitrag No.3, vom Themenstarter, eingetragen 2022-05-12
|
\quoteon(2022-05-12 15:28 - haegar90 in Beitrag No. 1)
Vielleicht hilft es umzuschreiben ?
$T(2^k) = \begin{cases}
1 & k = 0 \\
8 \cdot T(2^{k-1}) + 2^{2k}\cdot 2^{k/2} & k > 0
\end{cases}$
\quoteoff
Hat definitiv geholfen!
Hab mich ein bisschen mit der Anmerkung von k schwer getan, auf k = 0 bin ich auch noch gekommen und war mir nicht sicher ob die 0 per se erlaubt ist, bzw hab ich bei den Wurzeln und dem T(n/2) nicht dran gedacht es einfach umzuformen..
Vielen Dank euch beiden!
|
Profil
|
nakrama
Ehemals Aktiv
Dabei seit: 12.05.2019
Mitteilungen: 47
| Beitrag No.4, vom Themenstarter, eingetragen 2022-05-12
|
\quoteon(2022-05-12 15:44 - Kuestenkind in Beitrag No. 2)
Huhu,
das ist ja einfache Algebra und ein wenig Potenzgesetze.
\(\displaystyle T\left(2^{k+1}\right)=8T\left(\frac{2^{k+1}}{2}\right)+\left(2^{k+1}\right)^2\sqrt{2^{k+1}}=8T\left(2^k\right)+\left(2^{k+1}\right)^2\sqrt{2^{k+1}}\stackrel{IV}{=}8\left(\left(2+\sqrt{2}\right)(2^k)^3-(1+\sqrt{2})(2^k)^2\sqrt{2^k}\right)+\left(2^{k+1}\right)^2\sqrt{2^{k+1}}=\ldots=(2+\sqrt{2})\left(2^{k+1}\right)^3
-(1+\sqrt{2})\left(2^{k+1}\right)^2\sqrt{2^{k+1}}\)
\quoteoff
Ich muss doch nochmal fragen..
Dachte eigentlich es hätt sich erledigt, aber tatsächlich sehe ich nicht ganz was in deinen fehlenden Schritten stattfindet:
\(8\left(\left(2+\sqrt{2}\right)(2^k)^3-(1+\sqrt{2})(2^k)^2\sqrt{2^k}\right)+\left(2^{k+1}\right)^2\sqrt{2^{k+1}}\)
Wenn ich 8 = 2^3 ausdrücke und multipliziere komme ich zwar auf den vorderen Teil der gesuchten Form, aber scheitere danach an der Umformung:
\(8\left(\left(2+\sqrt{2}\right)(2^k)^3-(1+\sqrt{2})(2^k)^2\sqrt{2^k}\right)+\left(2^{k+1}\right)^2\sqrt{2^{k+1}}\)
$$=(2^{k+1})^3*(2+\sqrt{2})-(1+\sqrt{2})*\sqrt{2^k}*2^{2k}*2^3+(2^{k+1})^2*\sqrt{2^{k+1}} $$
wie bekomme ich die "Seite" nach dem Minus umgeformt?
Hab schon ein bisschen was rumprobiert, aber führt nichts in die gewünschte Richtung..
|
Profil
|
Kuestenkind
Senior 
Dabei seit: 12.04.2016
Mitteilungen: 2568
| Beitrag No.5, eingetragen 2022-05-12
|
Huhu nakrama,
\(2^3=2^2\cdot\sqrt{2}\cdot\sqrt{2}\). Dann einfach ausklammern.
Gruß,
Küstenkind
[Verschoben aus Forum 'Berechenbarkeitstheorie' in Forum 'Induktion' von Kuestenkind]
|
Profil
|
nakrama
Ehemals Aktiv
Dabei seit: 12.05.2019
Mitteilungen: 47
| Beitrag No.6, vom Themenstarter, eingetragen 2022-05-12
|
\quoteon(2022-05-12 19:49 - Kuestenkind in Beitrag No. 5)
Huhu nakrama,
\(2^3=2^2\cdot\sqrt{2}\cdot\sqrt{2}\). Dann einfach ausklammern.
Gruß,
Küstenkind
[Verschoben aus Forum 'Berechenbarkeitstheorie' in Forum 'Induktion' von Kuestenkind]
\quoteoff
Eigentlich dachte ich, dass es das Problem gelöst hätte, aber scheinbar nicht.
Habs erst mit:
$$(2^{k+1})^3*(2+\sqrt{2})-(1+\sqrt{2})*\sqrt{2^k}*2^{2k}*2^3+(2^{k+1})^2*\sqrt{2^{k+1}} $$
$$ = (2^{k+1})^3*(2+\sqrt{2})-(2+\sqrt{2})*\sqrt{2^k}*2^{2k}*2^2*\sqrt{2}+(2^{k+1})^2*\sqrt{2^{k+1}} $$
$$ = ... $$
versucht, bin damit nicht weiter gekommen, obwohl die Umformungen richtig sein sollten.
Dachtest du an:
$$(2^{k+1})^3*(2+\sqrt{2})-(1+\sqrt{2})*\sqrt{2^k}*2^{2k}*2^2*\sqrt{2}*\sqrt{2}+(2^{k+1})^2*\sqrt{2^{k+1}} $$
$$ = (2^{k+1})^3*(2+\sqrt{2})-(1+\sqrt{2})*\sqrt{2^{k+1}}*2^{2k+2}*\sqrt{2}+(2^{k+1})^2*\sqrt{2^{k+1}} $$
$$ = (2^{k+1})^3*(2+\sqrt{2})-(1+\sqrt{2})*(2^{2k+5/2})*\sqrt{2^{k}} \leftarrow $$
$$ = (2^{k+1})^3*(2+\sqrt{2})-(1+\sqrt{2})*(2^{k+1})^2*\sqrt{2^{k+1}} $$
An der Stelle mit dem Pfeil hab ich ehrlich gesagt nicht ganz verstanden wie der Schritt dort hin funktioniert hat. (Mit WolframAlpha umformen lassen)
Habe es selbst anders ausgeklammert in diesem Schritt, von daher wäre eine kurze Erklärung noch ganz hilfreich!
Hat mich tatsächlich gut zum verzweifeln gebracht😴
|
Profil
|
Kuestenkind
Senior
Dabei seit: 12.04.2016
Mitteilungen: 2568
| Beitrag No.7, eingetragen 2022-05-13
|
Guten Morgen nakrama,
es ist - wie gesagt - nur ausklammern:
\(\displaystyle -(1+\sqrt{2})\cdot \sqrt{2^k}\cdot 2^{2k}\cdot 2^3+(2^{k+1})^2\cdot \sqrt{2^{k+1}}=-(1+\sqrt{2})\cdot \sqrt{2^{k+1}}\cdot 2^{2k+2}\cdot \sqrt{2}+(2^{k+1})^2\cdot \sqrt{2^{k+1}}=-(2^{k+1})^2\cdot \sqrt{2^{k+1}}\left((1+\sqrt{2})\sqrt{2}-1\right)\)
Und die letzte klammer schaffst du sicherlich alleine.
Gruß,
Küstenkind
|
Profil
|
nakrama
Ehemals Aktiv
Dabei seit: 12.05.2019
Mitteilungen: 47
| Beitrag No.8, vom Themenstarter, eingetragen 2022-05-13
|
\quoteon(2022-05-13 06:51 - Kuestenkind in Beitrag No. 7)
Guten Morgen nakrama,
es ist - wie gesagt - nur ausklammern:
\(\displaystyle -(1+\sqrt{2})\cdot \sqrt{2^k}\cdot 2^{2k}\cdot 2^3+(2^{k+1})^2\cdot \sqrt{2^{k+1}}=-(1+\sqrt{2})\cdot \sqrt{2^{k+1}}\cdot 2^{2k+2}\cdot \sqrt{2}+(2^{k+1})^2\cdot \sqrt{2^{k+1}}=-(2^{k+1})^2\cdot \sqrt{2^{k+1}}\left((1+\sqrt{2})\sqrt{2}-1\right)\)
Und die letzte klammer schaffst du sicherlich alleine.
Gruß,
Küstenkind
\quoteoff
Hallo,
ich sehe jetzt erst woran es gelegen hat, so weit war ich auch schon, aber hab vor lauter Versuchen/Ansätzen komplett übersehen, dass man es ja letztlich nur noch zusammenfassen muss...
Manchmal steht man sich auch selbst im Weg.
Nochmals danke, damit hat es sich dann wirklich erledigt!
|
Profil
|
nakrama hat die Antworten auf ihre/seine Frage gesehen.
nakrama hat selbst das Ok-Häkchen gesetzt. | | nakrama wird per Mail über neue Antworten informiert. |
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die
Nutzungsbedingungen,
die Distanzierung,
die Datenschutzerklärung und das Impressum.
[Seitenanfang]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
