Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Induktion mit Potenzen
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Mathe-Forum -> Induktion mit Potenzen
 
Autor Nachricht
meiner einer
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 02.11.2005
Beiträge: 111

BeitragVerfasst am: 22 Nov 2006 - 19:05:41    Titel: Induktion mit Potenzen

Hallo,

mein Problem erläutere ich anhand von Beispielen.
Zitat:
IV: für n: 1+2+...+n = (n(n+1))/2
IB: für n+1: 1+2+...+n+(n+1) = ((n+1)(n+2))/2
Beweis: nach IV gilt:
1+2+...+n+(n+1) = (n(n+1))/2 + (n+1)
= ... = ((n+1)(n+2))/2

Also in der vorletzten Zeile zähl ich zu der Gleichung für n einfach (n+1) dazu. Klar, da es sich hierbei um eine Summe handelt.

Aber wie mache ich das bei Potenzen, also wenn n der Exponent ist?
Beispiel (mit h als eine Funktion): so würde ich es rechnen:
Zitat:
IV: für n: h(n) = 2^(n) - 1
IB: für n+1: h(n+1) = 2^(n+1) - 1
Beweis: nach IV gilt:
h(n+1) = 2 * 2^(n) - 1
= 2^(n+1) - 1

Es geht mir also um die vorletzte Zeile, in der ich sagen muß:
h(n+1) = h(n) mit (n+1)
ist das richtig, dass es dann ganz einfach 2 * 2^(n) - 1 ist?

Ich hab jetzt nämlich 3 Aufgaben von meinem aktuellen Übungsblatt genau auf diese Weise gelöst - das sind 50% des Blattes. Drum wäre es gut zu wissen, ob ich das richtig habe Laughing
Tetra
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 07.11.2006
Beiträge: 950

BeitragVerfasst am: 22 Nov 2006 - 22:09:35    Titel:

irgendwas kommt mir da spanisch vor....

IV: für n: h(n) = 2^(n) - 1

ok

IB: für n+1: h(n+1) = 2^(n+1) - 1

ok. damit ist dann: h(n+1)=[2*h(n)]+1

Beweis: nach IV gilt:
h(n+1) = 2 * 2^(n) - 1
= 2^(n+1) - 1

?? was soll das zeigen???




Normalerweise macht man:

IV: h(n) = 2^(n) - 1. was auch immer h(n) bei dir ist
IA: n=0:

h(0)=(2^0)-1

IS: n-->n+1

da muss dann gelten: h(n+1)=[2*h(n)]+1



Oder hab ich da was falsch verstanden? und wass ist h(n)?
Winni
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 04.08.2005
Beiträge: 3612

BeitragVerfasst am: 22 Nov 2006 - 22:19:57    Titel:

Hallo !

Annahme: 2^0 + 2^1 +... + 2^(n-1) = 2^n - 1

n=1: 2^0 = 2^1 - 1 o.k.

n->n+1 :
2^(n+1) - 1 = 2^0 + 2^1 +... + 2^(n-1) + 2^n = 2^n - 1 + 2^n = 2*2^n - 1 = 2^(n+1) - 1
... was zu zeigen war ...
meiner einer
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 02.11.2005
Beiträge: 111

BeitragVerfasst am: 22 Nov 2006 - 23:06:46    Titel:

Ok, entschuldigung, hab mich zu unverständlich ausgedrückt.
Was ich geschrieben hatte, war nur ein Teil der Induktion. Ich mach das normal so:

Induktionsanfang: n_0 =...
Induktionsschritt: n >= n_0
-Induktionsvorraussetzung: für n
-Induktionsbehauptung: für n+1

Also ich hab immer nur den Induktionsschritt hingeschrieben. Übrigens: das n war aus den natürlichen Zahlen ohne 0. h war eine Abbildung, die bestimmte Bedingungen erfüllen sollte, die ich hier aber nicht angegeben habe.
Also das war natürlich mein Fehler, dass ihr das so nicht nachvollziehen konntet. Mir gings aber eigentlich auch nur darum:
Tetra hat folgendes geschrieben:
IB: für n+1: h(n+1) = 2^(n+1) - 1

ok. damit ist dann: h(n+1)=[2*h(n)]+1

...obwohl, vielleicht auch doch nicht. Ich bin nochmal auf einen "anderen weg" gekommen, bleib aber hängen.
Vergesst am besten, was ich bisher geschrieben hab. Nochmal alles von vorne, und diesmal die komplette Aufgabenstellung:

Aufgabe:
Die Abbildung h: IN -> Z(ganze Zahlen) sei rekursiv definiert durch
h(1) = 3,
h(2) = 5,
h(n) = 3h(n-1) - 2h(n-2) (für n >= 3).
Beweise mittles vollständiger Induktion, dass für alle n€IN gilt:
h(n) = 2^(n) +1.

mein Beweis:
IA:
n_0 = 1:
2^(1)+1 = 3 = h(1)

n_1 = 2:
2^(2)+1 = 5 = h(2)

n_2 = 3:
2^(3)+1 = 9
---ist gleich:---
3h(n-1) - 2h(n-2) = 3h(2) - 2h(1) = 9

IS: für n >= 3
-IV: für n: h(n) = 2^(n)+1
-IB: für n+1: h(n+1) = 2^(n+1) +1
Beweis:
g(n+1) = 3h(n+1-1) - 2h(n+1-2) = 3h(n) - 2h(n-1)
nach IV => 3(2^(n)+1) - 2(2^(n-1)+1) = 3*2^(n) - 2^(n)+1 = 2^(n+1)+1

----------------
so mein Problem ist jetzt, dass ich beim Beweis kurzerhand h(n-1) = 2^(n-1)+1 eingesetzt habe, was natürlich nicht so einfach geht. Wie mach ichs besser?
Winni
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 04.08.2005
Beiträge: 3612

BeitragVerfasst am: 23 Nov 2006 - 14:20:16    Titel:

... kannst Deinem Lehrer ausrichten, dass hier ein Induktionsbeweis überflüssig - also kein gutes Beispiel für diese Beweisart - ist ...

Bedingung: h(n) = 3h(n-1) - 2h(n-2)

Behauptung: h(n) = 2^n + 1 für alle n>=3 .

Beweis:
Behauptung in die Bedingung für h(n-2) und h(n-1) einsetzen,
als Ergebnis ergibt sich h(n).
meiner einer
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 02.11.2005
Beiträge: 111

BeitragVerfasst am: 23 Nov 2006 - 15:11:36    Titel:

wow Laughing
nun gut, wir sollen es dennoch mit vollständiger Induktion nachweisen.

Aber es ist doch richtig, dass man bei vollst.Induktion von n auf n+1 schließt!? Und die Aussage beweist man indem man in die Behauptung die Bedingung einsetzt!? Oder gilt das nicht allgemein?

So gesehen ist dein beweis kein Induktionsbeweis - ok, sagtest du ja auch.

Wie sieht es denn damit aus, wenn ich bei meinem Beweis zwei Behauptungen aufstellen würde? Also einmal was schon da steht:
für n+1: h(n+1) = 2^(n+1) +1
und zusätzlich:
für n-1: h(n-1) = 2^(n-1) +1

Dann ist es keine Induktion mehr, oder? Ich weiß nicht, was ich sonst machen sollte...
Winni
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 04.08.2005
Beiträge: 3612

BeitragVerfasst am: 23 Nov 2006 - 16:29:36    Titel:

Die Induktion musst Du mit n=3 beginnen:

Induktionsanfang:
h(3) = 3h(2) - 2h(1) ist erfüllt,
weil h(1)=2^1 + 1 = 3 und h(2) = 2^2 + 1 = 5
als Ergebnis h(3) = 2^3 +1 liefert.

Induktion n->n+1 :
Voraussetzung: h(n) = 3h(n-1) - 2h(n-2) mit h(n) = 2^n + 1
Schlussfolgerung: h(n+1) = 3h(n) - 2h(n-1) mit h(n+1) = 2^(n+1) + 1

h(n+1) = 3h(n) - 2h(n-1) = 3*(2^n + 1) - 2*(2^(n-1) + 1)
= 3*2^n + 3 - 2*2^(n-1) - 2 = 2^(n+1) + 1

Damit bist Du schon fertig.
meiner einer
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 02.11.2005
Beiträge: 111

BeitragVerfasst am: 24 Nov 2006 - 15:48:35    Titel:

ich hab jetzt mit meiner Mathe-Tutorin gesprochen, und die sagte mir:
"Den Induktionsanfang musst du fuer 1 und 2 durchfuehren, da in der
rekursiven Formel fuer h(n) immer auf zwei Vorhergehende (also h(n-1)
und h(n-2)) zurueckgegriffen wird."
Also so:

Induktionsanfang:
für n_0 = 1:
2^(n) + 1 = 2^(1) + 1 = 3 = h(1)
für n_1 = 2:
2^(n) + 1 = 2^(2) + 1 = 5 = h(2)

Induktionsschritt: für n >= 3:
Voraussetzung:
h(n-1) = 2^(n-1) + 1
h(n-2) = 2^(n-2) + 1
Schlussfolgerung:
h(n) = 2^(n) + 1 (mit h(n) = 3h(n-1) - 2h(n-2))

h(n) = 3h(n-1) - 2h(n-2) = 3*(2^(n-1) + 1) - 2*(2^(n-2) + 1)
= (3/2)*2^(n) + 3 - (2/4)*2^(n) - 2 = 2^(n) + 1
Winni
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 04.08.2005
Beiträge: 3612

BeitragVerfasst am: 24 Nov 2006 - 15:54:05    Titel:

Ja, stimmt, h(1) und h(2) am Anfang noch überprüfen.
Das mit n=3 war bereits auf die Rekurionsformel bezogen.
Wie auch immer, jetzt hast Du es korrekt.
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Mathe-Forum -> Induktion mit Potenzen
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum