Induktion < Induktion < Analysis < Oberstufe < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 00:39 Do 12.05.2016 | | Autor: | brover |
| Aufgabe | ich habe als Aufgabe folgende Rekurrenz zu lösen:
f.a. derart, dass es ein gibt mit
mit in den übrigen Fällen. |
Moin zusammen,
Für die Rekurrenz habe ich nun folgende Gleichung:
Welche ich per Induktion Beweise:
Induktionsanfang:
Induktionsvorraussetzung:
Induktionsschluss:
oder
Hier komme ich einfach nicht weiter. Wie komme ich dort auf T(n) damit ich die IV anwenden kann?
Danke schonmal für alle hilfreichen Tipps/Ansätze :)
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:37 Do 12.05.2016 | | Autor: | leduart |
Hallo
du musst in deiner Induktion zwischen [mm] n=2^k [/mm] k [mm] \in \IN [/mm] und [mm] 2^k
du hast in deiner Induktion die 2 verschiedenen Def. für T ja nicht benutzt.
Gruß leduart
|
|
|
| |
|
Mache zunächst eine VI nur für diejenigen Zahlen, die eine Zweierpotenz sind, also nicht über n, sondern über k.
Ergebnis: [mm] T(2^k)=2*2^k-1.
[/mm]
Jetzt betrachtest du diejenigen Zahlen, die zwischen [mm] 2^k [/mm] und [mm] 2^{k+1} [/mm] liegen, aber ohne VI. Dafür gilt ebenfalls: [mm] T(n)=2*2^k-1.
[/mm]
Somit: [mm] T(2^{k+x})=2^{k+1}-1 [/mm] für [mm] k\in \IN [/mm] und [mm] 0\le [/mm] x < 1.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:49 Do 12.05.2016 | | Autor: | brover |
Danke!
|
|
|
|
