Induktionsbeweis < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
Status: |
(Frage) beantwortet | Datum: | 00:48 Di 21.07.2009 | Autor: | mausieux |
Aufgabe | Beweisen Sie mithilfe der vollständigen Induktion, dass [mm] 3^{2^n}-1 [/mm] durch [mm] 2^{n+2} [/mm] teilbar ist. |
Ich habe so begonnen:
[mm] \bruch{3^{2^n}-1}{2^{n+2}}= [/mm] a [mm] /*2^{n+2}
[/mm]
[mm] 3^{2^n}-1 [/mm] = [mm] a{2^{n+2}}
[/mm]
(i) Die Behauptung gilt für n = 1 offensichtlich.
[mm] 3^{2^1}-1 [/mm] = [mm] a{2^{1+2}}
[/mm]
8 = 8a /:8
a = 1
(v) Die Behauptung gilt bis n!
(II) Schluß von [mm] {n\rightarrow\n+1}
[/mm]
[mm] 3^{2^n+1}-1 [/mm] = [mm] b{2^{{n+1}+2}}
[/mm]
[mm] {(3^{2^n+1}-1)}{(3^{2^n+1}+1)} [/mm] = [mm] b{2^{{n+1}+2}}
[/mm]
[mm] {(a{2^{n+2}})}{(3^{2^n+1}+1)} [/mm] = [mm] b{2^{{n+1}+2}}
[/mm]
Weiter komme ich nicht, oder ich weiß schon wie es weiter geht - verstehe es aber noch nicht
Würde mir jemand helfen und Erklärungen geben????
|
|
|
|
Status: |
(Antwort) fertig | Datum: | 01:55 Di 21.07.2009 | Autor: | pelzig |
Induktionsschritt: [mm] $3^{2^{n+1}}-1=\left(3^{2^n}\right)^2-1=(3^{2^n}+1)\cdot(3^{2^n}-1)\stackrel{\text{I.V.}}{=}\underbrace{(3^{2^n}+1)}_{\text{gerade}}(b\cdot 2^{n+2})=\tilde{b}\cdot 2^{n+3}$.
[/mm]
Gruß, Robert
|
|
|
|
|
Status: |
(Frage) beantwortet | Datum: | 13:04 Di 21.07.2009 | Autor: | mausieux |
Würdest du mir denn Schritt mal bitte erklären? Kommt der nach meinem letzten bzw. knüpft er an meinen Schluss an?
|
|
|
|
|
Status: |
(Antwort) fertig | Datum: | 13:36 Di 21.07.2009 | Autor: | Marcel |
Hallo,
> Würdest du mir denn Schritt mal bitte erklären? Kommt der
> nach meinem letzten bzw. knüpft er an meinen Schluss an?
die Rechnung
[mm] $$3^{2^{n+1}}-1=\left(3^{2^n}\right)^2-1=(3^{2^n}+1)\cdot(3^{2^n}-1)\stackrel{\text{I.V.}}{=}\underbrace{(3^{2^n}+1)}_{\text{gerade}}(b\cdot 2^{n+2})=\tilde{b}\cdot 2^{n+3}$$
[/mm]
ergibt sich im Induktionsschritt $n [mm] \mapsto [/mm] n+1$ (beachte dabei: [mm] $3^{2^{n+1}}=3^{2*2^{n}}=\big(3^{2^n}\big)^2$):
[/mm]
Hier wird vorausgesetzt, dass [mm] $3^{2^{n}}-1$ [/mm] durch [mm] $2^{n+2}$ [/mm] teilbar sei. (Wenn Du das übrigens mit [mm] $\frac{3^{2^{n}}-1}{2^{n+2}}=a$ [/mm] formulieren willst, dann solltest Du zusätzlich schreiben: Mit einem $a [mm] \in \IZ$!)
[/mm]
Nun ist zu zeigen, dass - unter der obigen Voraussetzung - dann auch [mm] $3^{2^{n+1}}-1$ [/mm] ein ganzzahliges Vielfaches von [mm] $2^{(n+1)+2}=2^{n+3}$ [/mm] ist. In Deiner Formulierung:
Dass mit [mm] $b:=\frac{3^{2^{n+1}}-1}{2^{n+3}}$ [/mm] dann auch $b [mm] \in \IZ$ [/mm] gilt.
Robert hat nun (s.o.) gerechnet (anstelle von Roberts [mm] $b\,$ [/mm] sollte eher ein [mm] $a\,$ [/mm] stehen, wegen der Formulierung der I.V.; und Roberts [mm] $\tilde{b}$ [/mm] heißt bei mir dann wieder nur [mm] $b\,$):
[/mm]
[mm] $$3^{2^{n+1}}-1=(3^{2^n}+1)\cdot(3^{2^n}-1)\stackrel{\text{I.V.}}{=}\underbrace{(3^{2^n}+1)}_{\text{gerade}}(a\cdot 2^{n+2})\,.$$
[/mm]
Hierbei kann man nun begründen, dass die von Robert aufgestellte Behauptung, dass [mm] $3^{2^n}+1$ [/mm] gerade ist, auch wirklich stimmt:
[mm] $3^{2^n}$ [/mm] ist als Produkt endlich vieler ungerader Zahlen (die [mm] $3\,$ [/mm] ist ja eine ungerade Zahl, und diese wird [mm] $2^n$ [/mm] Mal mit sich selbst multipliziert!) ungerade, woraus auch schon Robert's Behauptung folgt.
[mm] $(\star)$ [/mm] Daraus ergibt sich, dass [mm] $3^{2^n}+1=2*m$ [/mm] mit einem $m=m(n) [mm] \in \IZ$ [/mm] gilt.
Also:
[mm] $$3^{2^{n+1}}-1=2*m*(a*2^{n+2})$$
[/mm]
[mm] $$\gdw 3^{2^{n+1}}-1=m*(a*2^{n+3})$$
[/mm]
[mm] $$\gdw 3^{2^{n+1}}-1=(m*a)*2^{n+3}\,.$$
[/mm]
Nach I.V. war $a [mm] \in \IZ$ [/mm] und wegen [mm] $(\star)$ [/mm] ist auch $m [mm] \in \IZ$ [/mm] und somit $(m*a) [mm] \in \IZ\,.$ [/mm] Folglich ergibt sich wegen $b=m*a$ dann auch $b [mm] \in \IZ\,.$
[/mm]
Bemerkung:
Evtl. kannst Du hier auch überall [mm] $\IZ$ [/mm] durch [mm] $\IN$ [/mm] bzw. [mm] $\IN_0$ [/mm] ersetzen.
P.S.:
Um die Bezeichnungen [mm] $a\,$, $b\,$ [/mm] und [mm] $\tilde{b}$ [/mm] zu vermeiden und nicht unterschiedlich zu benutzen (Roberts [mm] $a\,$ [/mm] war wohl nur für den Fall [mm] $n=1\,$ [/mm] reserviert, sein [mm] $b\,$ [/mm] spielt die Rolle meines [mm] $a\,$'s [/mm] und sein [mm] $\tilde{b}$ [/mm] spielt die Rolle meines [mm] $b\,$'s), [/mm] kann man auch einfach sagen:
Wir betrachten die Folge [mm] $\big(a_n\big)_{n \in \IN}$ [/mm] (bei mir ist $0 [mm] \notin \IN$), [/mm] definiert durch
[mm] $$a_n:=\frac{3^{2^n}-1}{2^{n+2}}\;\;(n \in \IN)\,.$$ [/mm]
Wenn man die Aufgabe umformuliert, so hat man zu zeigen:
Dann ist [mm] $\big(a_n\big)_{n \in \IN}$ [/mm] eine Folge in [mm] $\IZ$ [/mm] (oder [mm] $\IN$ [/mm] oder [mm] $\IN_0$...), [/mm] also:
Zu zeigen wäre dann, dass für jedes $n [mm] \in \IN$ [/mm] gilt
[mm] $$a_n \in \IZ\;\;\text{(oder }\IN\text{ oder }\IN_0\ldots\text{)}.$$
[/mm]
Für [mm] $n=1\,$ [/mm] würde dann hier nicht [mm] $a\,,$ [/mm] sondern [mm] $a_1$ [/mm] stehen. Im Induktionsschritt würde man benutzen, dass nach I.V. [mm] $a_n=\frac{3^{2^n}-1}{2^{n+2}} \in \IZ$ [/mm] gelten würde, und hätte zu zeigen, dass dann auch
[mm] $$a_{n+1}=\frac{3^{2^{n+1}}-1}{2^{n+3}} \in \IZ$$ [/mm]
gelten muss.
Gruß,
Marcel
|
|
|
|
|
Status: |
(Mitteilung) Reaktion unnötig | Datum: | 10:51 Mi 22.07.2009 | Autor: | mausieux |
Hallo Marcel,
vielen Dank für die sehr ausführliche Beantwortung. Ich werde mir das jetzt noch mal alles genau anschauen, da ich früher mal einen anderen Lösungsweg genommen habe. Ich denke aber, dass dieser (deiner/euer) besser ist. Mein früherer Weg war mit modula usw. Nicht sehr schön.
Danke
|
|
|
|