www.vorhilfe.de
- Förderverein -
Der Förderverein.

Gemeinnütziger Verein zur Finanzierung des Projekts Vorhilfe.de.
Hallo Gast! [ einloggen | registrieren ]
Startseite · Mitglieder · Impressum
Forenbaum
^ Forenbaum
Status VH e.V.
  Status Vereinsforum

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Suchen
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Induktionsbeweise" - Induktion
Induktion < Induktion < Analysis < Oberstufe < Schule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Induktionsbeweise"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Induktion: Idee
Status: (Frage) beantwortet Status 
Datum: 00:39 Do 12.05.2016
Autor: brover

Aufgabe
ich habe als Aufgabe folgende Rekurrenz zu lösen:
T(1) = 1;
T(n) = T(\frac{n}{2}) + n f.a. n \in \mathds{N} derart, dass es ein k \in \mathds{N}\{0\} gibt mit n = 2^k
T(n) = T(2^k) mit k = \left \lfloor log_{2}(n) \right \rfloor in den übrigen Fällen.

Moin zusammen,

Für die Rekurrenz habe ich nun folgende Gleichung:
T(n) = 2^{k+1}-1

Welche ich per Induktion Beweise:

Induktionsanfang:
T(1) = 1 = 2^1-1 = 2^{0+1}-1
T(2) = 3 = 4 - 1 = 2^2-1 = 2^{1+1}-1
T(3) = 3 = 4 - 1 = 2^2-1 = 2^{1+1}-1

Induktionsvorraussetzung:
T(n) = 2^{k+1}-1

Induktionsschluss:
T(n+1) = T(\frac{n+1}{2}) + n + 1
= T(\frac{2^k+1}{2}) + 2^k + 1
= T(2^{k-1}+\frac{1}{2}) + 2^k + 1
oder
= T(\frac{2^{log_{2}(n)}+1}{2}) + 2^k + 1

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 :)


        
Bezug
Induktion: Antwort
Status: (Antwort) fertig Status 
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
Bezug
        
Bezug
Induktion: Antwort
Status: (Antwort) fertig Status 
Datum: 11:57 Do 12.05.2016
Autor: HJKweseleit

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.
Bezug
                
Bezug
Induktion: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 22:49 Do 12.05.2016
Autor: brover

Danke!


Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Induktionsbeweise"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
ev.vorhilfe.de
[ Startseite | Mitglieder | Impressum ]