Induktionsproblem < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:10 So 09.05.2010 | | Autor: | XeZZ |
| Aufgabe | T(1) = 1
T(n) = 2*T(n/2)+2n-1
T'(n) = 2n*ld(n) + 1 |
Zu Beweisen ist mit Induktion über k, dass die Für alle Eeingabewerte der Form [mm] 2^k [/mm] T(n) = T(n) ist.
So nun hab ich angefangen und hab aber am Ende irgendwoe nen Fehler.
Ind. Anfang:
[mm] T(2^0) [/mm] = 1
[mm] T'(2^0) [/mm] = [mm] 2*ld(2^0)+1 [/mm] = 1
Ind Schritt:
Behauptung: [mm] 2\cdot \T(2^{k+1}/2)+2*2^{k+1}-1 [/mm] = [mm] 2*2^{k+1}*ld(2^k+1)+1
[/mm]
Beweis:
[mm] 2\cdot \T(2^{k+1}/2)+2^{k+2}-1=2^{k+2}*ld(2^{k+1})+1
[/mm]
[mm] 2\cdot \T(2^k)+2^{k+2}-1=2^{k+2}*ld(2^{k+1})+1 [/mm] |T' eingesetzt in T
[mm] 2(2*2^k*ld(2^k)-1=2^{k+2}*ld(2^{k+1})+1
[/mm]
[mm] 2^{k+2}*ld(2^k)+2-1=2^{k+2}*ld(2^{k+1})+1
[/mm]
[mm] 2^{k+2}*ld(2^k)+1=2^{k+2}*ld(2^{k+1})+1
[/mm]
So nun fehlt mir nen k im ld auf der linken Seite und ich finde den Fehler einfach nicht und bitte deshalb hier um Hilfe :)
mfg
|
|
| |
|
Hallo,
> T(1) = 1
> T(n) = 2*T(n/2)+2n-1
>
> T'(n) = 2n*ld(n) + 1
> Zu Beweisen ist mit Induktion über k, dass die Für alle
> Eeingabewerte der Form [mm]2^k[/mm] T(n) = T(n) ist.
>
> So nun hab ich angefangen und hab aber am Ende irgendwoe
> nen Fehler.
>
> Ind. Anfang:
> [mm]T(2^0)[/mm] = 1
> [mm]T'(2^0)[/mm] = [mm]2*ld(2^0)+1[/mm] = 1
>
> Ind Schritt:
> Behauptung: [mm]2\cdot \T(2^{k+1}/2)+2*2^{k+1}-1[/mm] =
> [mm]2*2^{k+1}*ld(2^k+1)+1[/mm]
> Beweis:
> [mm]2\cdot \T(2^{k+1}/2)+2^{k+2}-1=2^{k+2}*ld(2^{k+1})+1[/mm]
>
> [mm]2\cdot \T(2^k)+\red{2^{k+2}}-1=2^{k+2}*ld(2^{k+1})+1[/mm] |T'
> eingesetzt in T
Du vergisst ab diesem Schritt in deiner Rechnung das rot-markierte.
> [mm]2(2*2^k*ld(2^k)-1=2^{k+2}*ld(2^{k+1})+1[/mm]
> [mm]2^{k+2}*ld(2^k)+2-1=2^{k+2}*ld(2^{k+1})+1[/mm]
> [mm]2^{k+2}*ld(2^k)+1=2^{k+2}*ld(2^{k+1})+1[/mm]
Beginne bitte deinen Induktionsbeweis, wenn du es aufschreibst, in Zukunft immer so:
[mm] $2*T(2^{k+1}/2)+2*2^{k+1}-1 [/mm] = ...$,
dass du am Ende nach vielen Gleichheitszeichen auf das gewünschte [mm] $2*2^{k+1}*ld(2^k+1)+1$ [/mm] kommst. Das ist erstens mathematisch schöner, und zweitens wird dadurch für dich deutlicher, wann du die Induktionsvoraussetzung anwenden kannst, und dir passieren solche Fehler nicht.
Grüße,
Stefan
|
|
|
|
