Vollständige Induktion < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:49 So 10.10.2004 | | Autor: | ossywest |
Hallo zusammen,
könnt ihr mir vielleicht auch bei dieser Aufgabe helfen?
Die Folge [mm] (a_{2})_{n\in \IN^{0}} [/mm] sei rekursiv definiert durch
[mm] a_{0} [/mm] := 0, [mm] a_{1} [/mm] := 1 , [mm] a_{n+1} [/mm] := [mm] 2a_{n} [/mm] + [mm] 3a_{n-1} [/mm] für alle [mm] n\in \IN
[/mm]
Zeige das für alle n [mm] \in \IN^{0} [/mm] gilt [mm] a_{0} [/mm] = [mm] \bruch{1}{4} [/mm] ( [mm] 3^{n} [/mm] - [mm] (-1)^{n})
[/mm]
Benutzten kann man woll die Induktion mit erweiterter Induktionsannahme.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt
|
|
| |
|
Hallo ossywest,
Da sind wohl ein paar Schreibfehler in deinem Beitrag. An einigen Stellen, wo ein n hingehört, stehen Zahlen.
Hast du die Aufgabe schonmal allein versucht zu lösen? Wenn ja, dann poste doch deinen Lösungsvorschlag hier rein. Wenn nein, sag uns doch bitte, an welcher Stelle du genau Schwierigkeiten hast? Weisst du, wie du bei Induktionsbeweisen vorzugehen hast?
Liebe Grüsse,
Alex
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:33 Mi 13.10.2004 | | Autor: | ossywest |
Hallo,
ich habe bis jetzt nur einige Aufgaben gelöst, die hatten aber auch nur eine kleine Bedingung die bewiesen werden mußte. Aber bei diesre Frage weiß ich leider echt nicht wie ich das machen soll. Vielleicht könnt ihr mir da erklähren wie ihr zu einem Ergebnis kommt, so das ich das in aller Ruhe nachvollziehen kann.
MfG
ossywe!
|
|
|
| |
|
Hallo Sven,
Ich erkläre dir erstmal, was "erweiterte Induktionsannahme" hier bedeutet. Bei einem normalen Induktionsbeweis lautet die Induktionsannahme
"Die Behauptung gilt für i = n."
Die erweiterte Induktionsannahme lautet dagegen:
"Die Behauptung gilt für alle i kleiner gleich n."
In deinem Fall sieht das so aus:
Induktionsanfang n=0: [mm] $\frac{1}{4}(3^0 [/mm] - [mm] (-1)^0) [/mm] = [mm] \frac{1}{4}\cdot [/mm] 0 = 0 = [mm] a_0$
[/mm]
Induktionsannahme: Für alle i [mm] $\leq$n [/mm] gilt [mm] $a_i [/mm] = [mm] \frac{1}{4}(3^i [/mm] - [mm] (-1)^i)$.
[/mm]
Induktionsschritt n > 0: [mm] $a_{n+1} [/mm] = [mm] 2a_n [/mm] + [mm] 3a_{n-1} [/mm] = [mm] \ldots$
[/mm]
Jetzt solltest du an 2 Stellen die Induktionsannahme einsetzen. Versuch mal weiterzumachen. :)
Ich glaube, du kannst das nur nachvollziehen, wenn du es einmal selbst probiert hast. Ich habe dich jetzt bis zum schwierigen Teil geführt, den meistern wir jetzt gemeinsam, indem du einen Lösungsvorschlag präsentierst und ich ihn dann korrigiere.
Hinweis: Induktionsannahme einsetzen, ausmultiplizieren, an einer Stelle [mm] $-(-1)^n [/mm] = [mm] +(-1)^{n+1}$ [/mm] verwenden und zusammenfassen und 1/4 ausklammern.
Liebe Grüsse,
Alex
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:02 Mi 13.10.2004 | | Autor: | ossywest |
also wäre es das für den 2 Teil [mm] a_{1}=1 [/mm]
[mm] \bruch{1}{4}(3^{1}-(-1)^{1}) [/mm] = [mm] \bruch{1}{4}(3-(-1))=\bruch{1}{4}*4=1
[/mm]
Wäre das so weit Richtig?
Aber wie mache ich das mit dem Teil [mm] a_{n+1} [/mm] muß ich das auch an der Stelle i einsetzen?
MfG
ossywest!
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 22:15 Mi 13.10.2004 | | Autor: | ossywest |
Könnt ihr mir helfen? siehe oben
|
|
|
| |
|
Hallo Sven,
Da ich mir jetzt wirklich nicht sicher bin, ob das erweiterte Prinzip der vollständigen Induktion dein Problem ist oder diese spezielle Aufgabe, werde ich dir jetzt ein ähnliches Beispiel vorrechnen.
BEISPIELAUFGABE:
Wir definieren die Folge
[mm] $b_0 [/mm] := 1, [mm] b_1 [/mm] := 2, [mm] b_n [/mm] := [mm] b_{n-1}+2\cdot b_{n-2}$ [/mm] für [mm] $n\geq [/mm] 2$
Behauptung: [mm] $b_n [/mm] = [mm] 2^n$ [/mm] für [mm] $n\geq [/mm] 0$
Beweis:
Induktionsanfang: [mm] b_0 [/mm] = 1 = [mm] 2^0, b_1 [/mm] = 2 = [mm] 2^1
[/mm]
Induktionsschritt für n [mm] $\geq$ [/mm] 1:
Induktionsvoraussetzung: Für alle i = 0,...,n gilt [mm] $b_n [/mm] = [mm] 2^n$.
[/mm]
Induktionsbehauptung: [mm] $b_{n+1} [/mm] = [mm] 2^{n+1}$
[/mm]
Induktionsbeweis:
[mm] $b_{n+1} [/mm] = [mm] \blue{b_n} [/mm] + [mm] 2\cdot \blue{b_{n-1}}$
[/mm]
Nach Induktionsvoraussetzung ist [mm] $b_n [/mm] = [mm] 2^n$ [/mm] und [mm] $b_{n-1} [/mm] = [mm] 2^{n-1}$. [/mm] Wir haben also die Induktionsvoraussetzugn für i=n und für i=n-1 benutzt.
Damit erhalten wir
[mm] $b_{n+1} [/mm] = [mm] 2^n [/mm] + [mm] 2\cdot 2^{n-1} [/mm] = [mm] 2^n [/mm] + [mm] 2^n [/mm] = [mm] 2\cdot 2^n [/mm] = [mm] 2^{n+1}$. [/mm] (*)
q.e.d.
Bei deiner Aufgabe gehst du analog vor. Das haben wir oben ja schon gemacht. Du musst jetzt nur noch die letzte Berechnung ausführen, die hier in Zeile (*) steht.
Bitte schreib uns, ob du diese Beispielaufgabe verstanden hast und probiere die Lösung deiner Aufgabe.
Liebe Grüsse,
Irrlicht
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:38 Do 14.10.2004 | | Autor: | ossywest |
Hallo.
ich habe gerade versucht das nachzufollziehen. Aber in meinem Beispiel kann ich das leider nicht.
Kann du das auch in dieser Aufgabe, mir erklähren?
MfG
Sven!
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:19 Do 14.10.2004 | | Autor: | Stefan |
Hallo ossywest!
Also, Irrlich hat dir wirklich sehr gute Tipps gegeben. Ich finde es nicht gut, dass du es nicht wenigstens mal mit einem eigenen Lösungsansatz versuchst. Es reißt dir doch hier keiner den Kopf ab, wenn du was Falsches postest. Oder wirken wir so furchterregend, dass man sich bei uns nicht traut Fehler zu machen? Mir ist es lieber, du versuchst etwas und es ist falsch, anstatt hier nur auf unsere Musterlösungen zu warten.
Vorschlag: Ich rechne es jetzt mal zum Großteil und du versuchst dann die Lücken zu füllen. Einverstanden?
Wie von Irrlicht geschrieben, gilt mit der erweiterten Induktionsvoraussetzung (IV):
[mm] $a_{n+1}$
[/mm]
$= 2 [mm] a_n [/mm] + [mm] 3a_{n-1}$
[/mm]
[mm] $\stackrel{(IV)}{=} [/mm] 2 [mm] \cdot \frac{1}{4} \cdot (3^n [/mm] - [mm] (-1)^n) [/mm] + 3 [mm] \cdot \frac{1}{4} \cdot (3^{n-1} [/mm] - [mm] (-1)^{n-1})$
[/mm]
$= [mm] \frac{1}{4} \cdot [/mm] (2 [mm] \cdot 3^n [/mm] - 2 [mm] \cdot (-1)^n [/mm] + 3 [mm] \cdot 3^{n-1} [/mm] - 3 [mm] \cdot (-1)^{n-1})$ [/mm]
$= [mm] \ldots$
[/mm]
$= [mm] \frac{1}{4} \cdot (3^{3+1} [/mm] - [mm] (-1)^{n+1})$.
[/mm]
Und jetzt versuche bitte die Lücke zu füllen. Das sind ca. zwei Zeilen. Und auch wenn es falsch ist: Macht nichts, versuche es bitte und poste deine Lösung. Nur wenn wir sehen, wo du Probleme hast, können wir dir effektiv helfen. Sonst hast du rein gar nichts davon, und genau das wollen wir nicht. Wir wollen in erster Linie deine Schwächen beheben, dmait du demnächst so etwas vollkommen selber hinbekommst. 
Liebe Grüße
Stefan
|
|
|
| |
|
Hallo, ossywest,
nach
dem was Dir schon gesagt ist, ist es doch nur mehr eine einfache Rechenübung,
bei der die Potenzgesetze bekannt sein müssen, und insbesondere daß $ [mm] 9=3^2 [/mm] $ und $ [mm] (-1)^{n-2}=(-1)^n [/mm] gilt.
Behauptet wird
(1) [mm] $a_n [/mm] = [mm] \frac{1}{4}(3^n [/mm] - [mm] (-1)^n)$ [/mm] sei äquivalent zur, etwas umgeschriebenen,
recurisiven
Deffinition (2) [mm] $a_n [/mm] = [mm] 2*a_{n-1} +3*a_{n-2}$, [/mm] was leicht überprüfbar ist wenn
man (1) in (2) einsetzte
[mm] $a_n [/mm] = [mm] 2*\frac{1}{4}(3^{n-1} [/mm] - [mm] (-1)^{n-1})+3*\frac{1}{4}(3^{n-2} [/mm] - [mm] (-1)^{n-2})$
[/mm]
Machst Du da nun mal selbst weiter? Fasse die 3er- und (-1)er-Potenzen
zusammen indem Du (n-2)te Potenzen ausklammerest und dann siehe
Potenzgesetze.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 03:02 Fr 15.10.2004 | | Autor: | SirJective |
Hallo Friedrich,
> Behauptet wird
> (1) [mm]a_n = \frac{1}{4}(3^n - (-1)^n)[/mm] sei äquivalent zur,
> etwas umgeschriebenen,
> recurisiven
> Deffinition (2) [mm]a_n = 2*a_{n-1} +3*a_{n-2}[/mm], [...]
Das ist, soweit ich es verstanden habe, nicht die Aufgabe.
Du behauptest hier, dass die Folge [mm]a_n = \frac{1}{4}(3^n - (-1)^n)[/mm] die Rekursionsgleichung [mm]a_n = 2*a_{n-1} +3*a_{n-2}[/mm] erfüllt. Das kann man tatsächlich ohne vollständige Induktion zeigen.
Zu zeigen ist aber, dass die durch bestimmte Startwerte und die Rekursionsgleichung (2) definierte Folge die angegebenen Werte (1) hat. Das ist etwas leicht anderes und geht schon wegen der Definition der Folge durch (2) nicht ohne vollständige Induktion.
Gruss,
SirJective
|
|
|
|
