vollständige induktion < Induktion < Analysis < Oberstufe < Schule < Mathe < Vorhilfe
|
| Aufgabe | | Mittels vollständiger induktion beweise man, dass für alle ungeraden natürlichen zahlen n element aus N, der ausdruck [mm] 2^n [/mm] +1 durch 3 teilbar ist. |
1.) Induktionsanfang:
erstmal ist mein n definiert durch n= 2m-1, als darstellung aller ungeraden zahlen mit m element der natürlichen zahlen ab 1. schreibe das hier dazu weil ich meine dass man sich nicht ganz einig ist ob 0 dazu gehört oder nicht.
daraus folgt dann: [mm] 2^2^*^1^{-1} [/mm] +1 [mm] =2^2^{-1} [/mm] +1= [mm] 2^1 [/mm] +1= 2+1=3 äquivalent zu 0 modulo 3.
2.) induktionsannahme:
die identität [mm] 2^2^m^{-1} [/mm] +1 gelte für alle natürlichen zahlen k kleiner gleich m.
(bei der ausdrucksweise dieses schrittes bin ich mir immer recht unsicher)
3.) induktionsschritt:
zeigen dass die identität auch für die nächste stufe gilt, somit für m, (m+1) einsetzen.
daraus folgt:
[mm] 2^2^{(m+1)^-1} [/mm] +1
[mm] 2^{2m+2-1 } [/mm] +1= [mm] 2^{2m} *2^2 *2^{-1} [/mm] +1= [mm] 2^2*2^{2m}*2^{-1} [/mm] +1
[mm] 4*2^{2m-1} [/mm] +1
nun ziehe ich mir von den [mm] 4*2^{2m-1}, [/mm] eins herraus sodass ich stehen habe
3* [mm] 2^{2m-1} [/mm] + [mm] 2^{2m-1} [/mm] +1
[mm] 2^{2m-1} [/mm] +1 ist laut schritt eins durch 3 teilbar.
und der rest, also [mm] 3*2^{2m-1} [/mm] ist ebenfalls durch drei teilbar da es ein vielfaches von drei ist. somit ist bewiesen dass es für alle natürlichen ungeraden zahlen durch 3 teilbar ist.
oder??
gruß und danke schonmal
|
|
| |
|
Hallo freak-club,
> Mittels vollständiger induktion beweise man, dass für
> alle ungeraden natürlichen zahlen n element aus N, der
> ausdruck [mm]2^n[/mm] +1 durch 3 teilbar ist.
> 1.) Induktionsanfang:
>
> erstmal ist mein n definiert durch n= 2m-1, als darstellung
> aller ungeraden zahlen mit m element der natürlichen
> zahlen ab 1. schreibe das hier dazu weil ich meine dass man
> sich nicht ganz einig ist ob 0 dazu gehört oder nicht.
>
> daraus folgt dann: [mm]2^2^*^1^{-1}[/mm] +1 [mm]=2^2^{-1}[/mm] +1= [mm]2^1[/mm] +1=
> 2+1=3 äquivalent zu 0 modulo 3. ![[ok]](/images/smileys/ok.gif "[ok]")
>
> 2.) induktionsannahme:
>
> die identität [mm]2^2^m^{-1}[/mm] +1 gelte für alle natürlichen
> zahlen k kleiner gleich m.
> (bei der ausdrucksweise dieses schrittes bin ich mir immer
> recht unsicher)
Jo, das kannst du so machen, ist die erweiterte IV. Es genügt auch: "Für [mm]m\in\IN[/mm] beliebig, aber fest gelte [mm]3\mid \left(2^{2m-1}+1\right)[/mm]
>
> 3.) induktionsschritt:
>
> zeigen dass die identität auch für die nächste stufe
> gilt, somit für m, (m+1) einsetzen.
>
> daraus folgt:
es folgt ein Term?
>
> [mm]2^2^{(m+1)^-1}[/mm] +1
Genauer: zu zeigen: 3 teilt den obigen Ausdruck und dann Begr. liefern
>
> [mm]2^{2m+2-1 }[/mm] +1= [mm]2^{2m} *2^2 *2^{-1}[/mm] +1= [mm]2^2*2^{2m}*2^{-1}[/mm] +1
>
> = [mm]4*2^{2m-1}[/mm] +1
>
> nun ziehe ich mir von den [mm]4*2^{2m-1},[/mm] eins herraus sodass
> ich stehen habe
>
> 3* [mm]2^{2m-1}[/mm] + [mm]2^{2m-1}[/mm] +1
>
> [mm]2^{2m-1}[/mm] +1 ist laut schritt eins durch 3 teilbar.
Laut IV !
>
> und der rest, also [mm]3*2^{2m-1}[/mm] ist ebenfalls durch drei
> teilbar da es ein vielfaches von drei ist. somit ist
> bewiesen dass es für alle natürlichen ungeraden zahlen
> durch 3 teilbar ist.
>
>
>
> oder??
Ja, sag noch kurz, dass wenn a und b durch 3 teilbar sind, auch a+b durch 3 teilbar ist. Das benutzt du ja im letzten Schritt der Begründung implizit
Ich mache das immer so:
IV: [mm]3\mid 2^{2m-1}+1[/mm]
[mm]\Rightarrow 3\mid 4\cdot{}\left(2^{2m-1}+1\right)=2^{2(m+1)-1}+4[/mm] wegen [mm]a\mid b\Rightarrow a\mid k\cdot{}b[/mm]
Weiter gilt [mm]3\mid (-3)[/mm], also teilt 3 auch die Summe [mm]\left(2^{2(m+1)-1}+4\right)-3=2^{2(m+1)-1}+1[/mm]
Kommt also auf dasselbe heraus 
>
> gruß und danke schonmal
Gruß
schachuzipus
|
|
|
| |
|
> Hallo freak-club,
>
>
> > Mittels vollständiger induktion beweise man, dass für
> > alle ungeraden natürlichen zahlen n element aus N, der
> > ausdruck [mm]2^n[/mm] +1 durch 3 teilbar ist.
> > 1.) Induktionsanfang:
> >
> > erstmal ist mein n definiert durch n= 2m-1, als darstellung
> > aller ungeraden zahlen mit m element der natürlichen
> > zahlen ab 1. schreibe das hier dazu weil ich meine dass man
> > sich nicht ganz einig ist ob 0 dazu gehört oder nicht.
> >
> > daraus folgt dann: [mm]2^2^*^1^{-1}[/mm] +1 [mm]=2^2^{-1}[/mm] +1= [mm]2^1[/mm] +1=
> > 2+1=3 äquivalent zu 0 modulo 3.
> >
> > 2.) induktionsannahme:
> >
> > die identität [mm]2^2^m^{-1}[/mm] +1 gelte für alle natürlichen
> > zahlen k kleiner gleich m.
> > (bei der ausdrucksweise dieses schrittes bin ich mir
> immer
> > recht unsicher)
>
> Jo, das kannst du so machen, ist die erweiterte IV. Es
> genügt auch: "Für [mm]m\in\IN[/mm] beliebig, aber fest gelte [mm]3\mid \left(2^{2m-1}+1\right)[/mm]
>
>
> >
> > 3.) induktionsschritt:
> >
> > zeigen dass die identität auch für die nächste stufe
> > gilt, somit für m, (m+1) einsetzen.
> >
> > daraus folgt:
>
> es folgt ein Term?
>
> >
> > [mm]2^2^{(m+1)^-1}[/mm] +1
>
> Genauer: zu zeigen: 3 teilt den obigen Ausdruck und dann
> Begr. liefern
>
> >
> > [mm]2^{2m+2-1 }[/mm] +1= [mm]2^{2m} *2^2 *2^{-1}[/mm] +1= [mm]2^2*2^{2m}*2^{-1}[/mm]
> +1
> >
> > = [mm]4*2^{2m-1}[/mm] +1
muss ich die nächsten schritte noch machen? ein kollege meinte dass ab hier eigentlich schon ende sein könnte.
ich werds immer wieder so machen wie hier gezeigt. aber würde es bis hierher schon reichen?
> >
> > nun ziehe ich mir von den [mm]4*2^{2m-1},[/mm] eins herraus sodass
> > ich stehen habe
> >
> > 3* [mm]2^{2m-1}[/mm] + [mm]2^{2m-1}[/mm] +1
> >
> > [mm]2^{2m-1}[/mm] +1 ist laut schritt eins durch 3 teilbar.
>
> Laut IV !
>
> >
> > und der rest, also [mm]3*2^{2m-1}[/mm] ist ebenfalls durch drei
> > teilbar da es ein vielfaches von drei ist. somit ist
> > bewiesen dass es für alle natürlichen ungeraden zahlen
> > durch 3 teilbar ist.
>
>
>
> >
> >
> >
> > oder??
>
> Ja, sag noch kurz, dass wenn a und b durch 3 teilbar sind,
> auch a+b durch 3 teilbar ist. Das benutzt du ja im letzten
> Schritt der Begründung implizit
>
> Ich mache das immer so:
>
> IV: [mm]3\mid 2^{2m-1}+1[/mm]
>
> [mm]\Rightarrow 3\mid 4\cdot{}\left(2^{2m-1}+1\right)=2^{2(m+1)-1}+4[/mm]
> wegen [mm]a\mid b\Rightarrow a\mid k\cdot{}b[/mm]
>
> Weiter gilt [mm]3\mid (-3)[/mm], also teilt 3 auch die Summe
> [mm]\left(2^{2(m+1)-1}+4\right)-3=2^{2(m+1)-1}+1[/mm]
>
> Kommt also auf dasselbe heraus
>
> >
> > gruß und danke schonmal
>
> Gruß
>
> schachuzipus
>
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:21 Sa 05.03.2011 | | Autor: | Loddar |
Hallo freak-club!
> > = [mm]4*2^{2m-1}[/mm] +1
>
> muss ich die nächsten schritte noch machen? ein kollege
> meinte dass ab hier eigentlich schon ende sein könnte.
>
> ich werds immer wieder so machen wie hier gezeigt. aber
> würde es bis hierher schon reichen?
Da bis dato die Induktionsvoraussetzung noch gar nicht angewandt wurde, muss es hier noch weiter gehen.
Gruß
Loddar
|
|
|
|
