Induktion < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:08 Mi 02.02.2005 | | Autor: | chil14r |
Hallo! Hab ne Frage zu nem ziemlichen simplen Induktionsbeweis ! Leider ist er nicht zu simpel :
zu zeigen ist 4 \ ( [mm] 5^n [/mm] - 1 )
Also 4 ist Teiler von [mm] 5^n [/mm] - 1
IA. [mm] 5^1 [/mm] -1 = 4 ; 4 ist Teiler von sich selbst
IV. [mm] 5^n [/mm] - 1 = k*4
IB 5^( n+1 ) -1 = k*4
Das einzige was mir einfällt ist vielleicht den log auf
[mm] 5^n*5 [/mm] -1 = k*4 anzuwenden. Aber damitkommt manletzendlichauch nichtweiter! Kann mir jemand helfen ? Danke
|
|
| |
|
Hallo, Tom,
da Marcel sich viel Zeit auserbeten hat presche ich mal vor
wenn's den Induktiv sein muß hilft Dir vielleicht
[mm] $5^{n+1}-1 [/mm] = [mm] 5*5^n-1 [/mm] = [mm] (4+1)*5^n [/mm] - 1 = [mm] (5^n [/mm] - 1) + [mm] 4*5^n$
[/mm]
aber ich hoffe dir ist auch klar, daß [mm] $a^n [/mm] -1$ immer durch a-1 teilbar ist ( mach mal die Polynomdivision wenn Du's nicht glaubst )
Gruß F.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:59 Mi 02.02.2005 | | Autor: | chil14r |
das is echt schlichtweg genial. für mich als biostudent ein kleines wunder :)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:14 Mi 02.02.2005 | | Autor: | Marcel |
Hallo Friedrich!
> Hallo, Tom,
>
> da Marcel sich viel Zeit auserbeten hat presche ich mal
> vor...
War in Ordnung, aber normalerweise überlege ich mir schon, wielange ich Zeit haben will und habe auch meine Gründe, warum ich mir solange Zeit nehmen will. Bitte respektiere das, sonst ist dieses Feature, eine Frage zu reservieren, ziemlich sinnlos. 
Viele Grüße,
Marcel
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:00 Mi 02.02.2005 | | Autor: | Marcel |
Hallo Tom!
> Hallo! Hab ne Frage zu nem ziemlichen simplen
> Induktionsbeweis ! Leider ist er nicht zu simpel :
> zu zeigen ist 4 \ ( [mm]5^n[/mm] - 1 )
> Also 4 ist Teiler von [mm]5^n[/mm] - 1
> IA. [mm]5^1[/mm] -1 = 4 ; 4 ist Teiler von sich selbst
> IV. [mm]5^n[/mm] - 1 = k*4
![[ok]](/images/smileys/ok.gif "[ok]") (Du solltest aber eher schreiben: Mit einem $k [mm] \in \IN_{\,0}$! [/mm] (D.h., es gibt ein $k [mm] \in \IN_{\,0}$, [/mm] so dass [mm] $5^n-1=k*4$ [/mm] gilt).)
> IB 5^( n+1 ) -1 = k*4
![[notok]](/images/smileys/notok.gif "[notok]") Nein, dass $k$ in der Induktionsbehauptung muss (und wird auch) nicht das gleiche sein wie in der Induktionsvoraussetzung. Die Induktionsbehauptung ist, dass es ein $r [mm] \in \IN_{\,0}$ [/mm] gibt, so dass:
[mm] $5^{n+1}-1=r*4$.
[/mm]
Der Beweis geht eigentlich ziemlich einfach:
[m]5^{n+1}-1=5*5^n-1=5*(5^n-1)+4=(\star)[/m]
Im nächsten Schritt wendest du die Induktionsvoraussetzung an, nämlich dass (nach I.V.) [mm] $5^n-1=k*4$ [/mm] mit einem $k [mm] \in \IN_{\,0}$ [/mm] gilt:
[mm] $(\star)=5*(k*4)+4=(5k+1)*4$
[/mm]
Definierst du nun $r:=5k+1$, so gilt [mm] $r\in \IN_{\,0}$ [/mm] (wegen $k [mm] \in \IN_{\,0}$) [/mm] und die Behauptung ist bewiesen.
Ich wollte dir aber auch noch einen induktionsfreien Beweis anbieten:
Es gilt [mm] $\forall [/mm] n [mm] \in \IN$:
[/mm]
[m]5^n-1=(4+1)^n-1=\left[\sum_{k=0}^n\left( {n \choose k}4^k*\underbrace{1^{n-k}}_{=1}\right)\right]-1=\underbrace{{n \choose 0}*4^0}_{=1}+\left[\sum_{k=1}^n\left({n \choose k}4^k\right)\right]-1=\sum_{k=1}^n\left({n \choose k}4^k\right)=4*\sum_{k=1}^n\left({n \choose k}4^{k-1}\right)[/m]
Daraus kann man dann auch ablesen, dass für jedes $n [mm] \in \IN$ [/mm] gilt, dass $4$ ein Teiler von [mm] $5^n-1$ [/mm] ist, da für alle $n [mm] \in \IN$ [/mm] gilt: [m]\sum_{k=1}^n\left({n \choose k}4^{k-1}\right)\in \IN[/m].
Viele Grüße,
Marcel
|
|
|
|
