vollständige Induktion < Analysis < Hochschule < Mathe < Vorhilfe
|
Hallo Zusammen,
Ich habe bei folgender Aufgabe Schwierigkeiten bei einer Abschätzung:
| Aufgabe | | Sei [m]\textstyle T(n): = bn + \frac{2}{n}\sum_{k = 1}^{n - 1}{T(k)},\ T(1): = 0[/m], wobei [mm] $b\!$ [/mm] geeignet zu wählen ist. Zeige: [m]\exists c > 0\forall n \geqslant 1:T\left( n \right) \leqslant cn\log _2 n[/m]. |
Idee:
[m]n = 1: 0 \leqslant c\log _2 1 = 0.[/m] Angenommen die Aussage wäre wahr, dann $n [mm] \leadsto [/mm] n+1$:
[mm] $T(n+1)=b(n+1)+\frac{2}{n+1}\sum_{k=1}^n{T(k)}\stackrel{\*_1}{\leqslant}b+bn+\frac{2}{n}\sum_{k=1}^n{T(k)}=b+bn+\frac{2}{n}\left(\left(\sum_{k=1}^{n-1}{T(k)}\right)+T(n)\right)$
[/mm]
[mm] $=b+bn+\frac{2}{n}\left(\sum_{k=1}^{n-1}{T(k)}\right)+\frac{2T(n)}{n}\stackrel{\*_2}\leqslant b+cn\log n+\frac{2cn\log n}{n}=b+\left(1+\frac{2}{n}\right)cn\log [/mm] n.$
[mm] $(\*_1):$ [/mm] Ein Bruch wird größer, wenn sein Nenner kleiner wird.
[mm] $(\*_2):$ [/mm] Hier benutze ich zweimal die Induktionsannahme.
Aber wie komme ich nun von dieser Form auf [m]c\left(n+1\right)\log\left(n+1\right)[/m]? War meine bisherige Vorgehensweise richtig?
Vielen Dank!
Viele Grüße
Karl
|
|
| |
|
Hallo! Ich kann keinen Fehler entdecken und wäre genauso vorgegangen.
> wobei b geeignet zu wählen ist.
Ich denke du solltest, wie es ja auch vorgegeben ist das b passend bestimmen:
Du hast
[mm]b+cnlog_2n+ \bruch{2}{n}cnlog_2n=c(n+1)log_2(n+1)[/mm]
Daraus würde ich folgendes machen:
[mm]b+cnlog_2n+ \bruch{2}{n}cnlog_2n-c(n+1)log_2(n+1)=0 [/mm]
[mm]\gdw b+cnlog_2n+ \bruch{2}{n}cnlog_2n-cnlog_2(n+1)-clog_2(n+1)=0[/mm]
[mm]\gdw b+cn(log_2(n^{( \bruch{2}{n}+1)})-log_2(n+1))-clog_2(n+1)=0[/mm]
[mm]\gdw b+cn(log_2(\bruch{n^{(\bruch{2}{n}+1)}}{n+1})-clog_2(n+1)=0[/mm]
[mm]\gdw b+c(log_2(\bruch{n^{(2+n)}}{(n+1)^n})-log_2(n+1))=0 [/mm]
[mm]\gdw b= -clog_2(\bruch{n^{(2+n)}}{(n+1)^{(n+1)}}) [/mm]
Dann stimmt die Abschätzung
Vielleicht hilft dir das.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:38 Do 19.05.2005 | | Autor: | Karl_Pech |
Danke für deine Hilfe Deuteronomium!
Viele Grüße
Karl
![[user]](/images/smileys/user.gif "[user]")
|
|
|
|
