Vollständige Induktion < Induktion < Analysis < Oberstufe < Schule < Mathe < Vorhilfe
|
Status: |
(Frage) beantwortet | Datum: | 21:43 Sa 04.04.2015 | Autor: | Ashrag |
Aufgabe 1 | Behauptung: Für alle n [mm] \in \IN_0 [/mm] ist [mm] a_n [/mm] = [mm] 6^{n+2} [/mm] + [mm] 7^{2n+1} [/mm] durch 43 teilbar |
Aufgabe 2 | Beweis: Wir beweisen die Behauptung mit Induktion nach n.
Im Induktionsanfang sei [mm] n_0 [/mm] = 0. Dann ist [mm] a_0 [/mm] = 6² + 7 = 43, also ist [mm] a_0 [/mm] durch 43 teilbar, und es gilt der Induktionsanfang.
Für den Induktionsschritt sei n [mm] \ge [/mm] 0. Wir nehmen an, dass [mm] a_n [/mm] durch 43 teilbar ist, und müssen zeigen, dass [mm] a_{n+1} [/mm] durch 43 teilbar ist. |
Aufgabe 3 | [mm] a_{a+1} [/mm] = [mm] 6^{(n+1)+2} [/mm] + [mm] 7^{2(n+1)+1"}
[/mm]
= [mm] 6^{n+3} [/mm] + [mm] 7^{2n+3}
[/mm]
= [mm] 6(6^{n+2}) [/mm] + [mm] 7²(7^{2n+1})
[/mm]
= [mm] 6(6^{n+2}) [/mm] + [mm] (43+6)7^{2n+1}
[/mm]
= [mm] 6(6^{n+2} [/mm] + [mm] 7^{2n+1}) [/mm] + 43 * [mm] 7^{2n+1} [/mm] |
Aufgabe 4 | 43 teilt [mm] 6(6^{n+2} [/mm] + [mm] 7^{2n+1}), [/mm] denn 43 teilt [mm] 6^{n+2} [/mm] + [mm] 7^{2n+1} [/mm] nach Annahme, und 43 teilt 43 * [mm] 7^{2n+1}. [/mm] Somit ist [mm] a_{n+1} [/mm] durch 43 teilbar, und mit dem Prinzip der vollständigen Induktion folgt die Behauptung |
Mein Problem ist diese Aufgabenstellung. Ich habe mir nun ein paar Youtube Videos angeschaut und ein paar Sachen durchgelesen. Ich denke ich habe es verstanden, aber egal was ich mache, ich kann es nicht hier drauf anwenden und solange ich hier mein Knoten nicht gelöst habe, habe ich ein Problem das Prinzip überhaupt anzuwenden.
Es ist für mich aber äußerst wichtig, dass ich es verstehe und anwenden kann.
Daher hoffe ich, dass vielleicht hier einer in der Lage ist es mir verständlich zu erklären, ich befürchte ich habe mich hier total verrannt und sehe die einfachsten Zusammenhänge nicht mehr.
Der Text ist 1zu1 abgeschrieben aus dem Buch.
Ich möchte mich jetzt schon mal bedanken für eure Hilfe.
Viele Grüße
Ashrag
|
|
|
|
Status: |
(Antwort) fertig | Datum: | 23:13 Sa 04.04.2015 | Autor: | Marcel |
Hallo,
> Behauptung: Für alle n [mm]\in \IN_0[/mm] ist [mm]a_n[/mm] = [mm]6^{n+2}[/mm] +
> [mm]7^{2n+1}[/mm] durch 43 teilbar
> Beweis: Wir beweisen die Behauptung mit Induktion nach n.
>
> Im Induktionsanfang sei [mm]n_0[/mm] = 0. Dann ist [mm]a_0[/mm] = 6² + 7 =
> 43, also ist [mm]a_0[/mm] durch 43 teilbar, und es gilt der
> Induktionsanfang.
>
> Für den Induktionsschritt sei n [mm]\ge[/mm] 0. Wir nehmen an, dass
> [mm]a_n[/mm] durch 43 teilbar ist, und müssen zeigen, dass [mm]a_{n+1}[/mm]
> durch 43 teilbar ist.
> [mm]a_{a+1}[/mm] = [mm]6^{(n+1)+2}[/mm] + [mm]7^{2(n+1)+1"}[/mm]
>
> = [mm]6^{n+3}[/mm] + [mm]7^{2n+3}[/mm]
>
> = [mm]6(6^{n+2})[/mm] + [mm]7²(7^{2n+1})[/mm]
schreibe bitte [mm] [nomm]$7^2$[/nomm]; [/mm] denn 7² sieht man innerhalb von Formeln
nicht!
>
> = [mm]6(6^{n+2})[/mm] + [mm](43+6)7^{2n+1}[/mm]
>
> = [mm]6(6^{n+2}[/mm] + [mm]7^{2n+1})[/mm] + 43 * [mm]7^{2n+1}[/mm]
> 43 teilt [mm]6(6^{n+2}[/mm] + [mm]7^{2n+1}),[/mm] denn 43 teilt [mm]6^{n+2}[/mm] +
> [mm]7^{2n+1}[/mm] nach Annahme, und 43 teilt 43 * [mm]7^{2n+1}.[/mm] Somit
> ist [mm]a_{n+1}[/mm] durch 43 teilbar, und mit dem Prinzip der
> vollständigen Induktion folgt die Behauptung
> Mein Problem ist diese Aufgabenstellung. Ich habe mir nun
> ein paar Youtube Videos angeschaut und ein paar Sachen
> durchgelesen. Ich denke ich habe es verstanden, aber egal
> was ich mache, ich kann es nicht hier drauf anwenden und
> solange ich hier mein Knoten nicht gelöst habe, habe ich
> ein Problem das Prinzip überhaupt anzuwenden.
> Es ist für mich aber äußerst wichtig, dass ich es
> verstehe und anwenden kann.
> Daher hoffe ich, dass vielleicht hier einer in der Lage
> ist es mir verständlich zu erklären, ich befürchte ich
> habe mich hier total verrannt und sehe die einfachsten
> Zusammenhänge nicht mehr.
>
> Der Text ist 1zu1 abgeschrieben aus dem Buch.
>
> Ich möchte mich jetzt schon mal bedanken für eure Hilfe.
Ja, aber was ist denn nun Dein Problem? Ich erkläre es mal so: Ein
Induktionsbeweis funktioniert wie das "Fallenlassen" (abzählbar)
unendlicher vieler Dominosteine.
Der Induktionsschritt zeigt im Prinzip: Wenn der vorangegangene Stein fällt,
dann folgt auch, dass der nächste fällt (weil er *nahe genug dran steht*).
Um alle Steine fallen zu lassen, muss man dann auch *mit einem anfangen*
(das ist quasi der Induktionsstart).
Lies Dir aber auch
Seite 10 von hier (Zählung intern!)
mal durch.
Zu Deiner Aufgabe: [mm] $a_n=6^{n+2}+7^{2n+1}$ [/mm] ist für alle $n [mm] \in \IN_0$ [/mm] durch 43 teilbar.
Du fängst, gemäß der Aufgabenstellung, meist in sinnvoller Weise mit *dem
minimalen [mm] $n\,$* [/mm] an. Hier ist [mm] $\min(\IN_0)=0\,.$
[/mm]
[Manchmal ist das ungünstig, das merkt man dann etwa, wenn man den
Induktionsschritt macht, und dabei sieht, dass der nur für *größere* [mm] $n\,$
[/mm]
leicht erklärbar ist. Die Idee ist dann meist:
Eine Aussage [mm] $A(z)\,$ [/mm] soll für alle ganzen $z [mm] \ge z_0$ [/mm] gelten. Im Induktionsschritt
sieht man aber, dass der nur für alle ganzen $z [mm] \ge z_1$ [/mm] mit [mm] $z_1 [/mm] > [mm] z_0$ [/mm] *klappt*.
Dann zeigt man einfach, dass $A(z)$ für [mm] $z=z_0,...,z_1$ [/mm] gilt; und im Induktionsbeweis
ist dann der *interessante* Induktionsstart [mm] $z=z_1$. [/mm] Brauchst Du dafür ein
Beispiel? Aber zurück zur Aufgabe: ...]
Für [mm] $n=0\,$ [/mm] ist [mm] $a_n=a_0=6^{n+2}+7^{2n+1}=6^2+7=43$ [/mm] offenbar durch 43 teilbar.
Wundere Dich jetzt nicht, ich nehme lieber mal eine andere Indexbezeichnung:
Nun sei $k [mm] \in \IN_0$ [/mm] so, dass [mm] $a_k=6^{k+2}+7^{2k+1}$ [/mm] von 43 geteilt werde.
(Mindestens ein solches k kennen wir schon; welches wohl?)
Unter der Voraussetzung, dass 43 ein Teiler von [mm] $a_k$ [/mm] ist, wollen wir zeigen, dass
dann auch 43 ein Teiler von [mm] $a_{k+1}$ [/mm] ist.
[Rein von der Logik her: Wir wissen, dass 43 ein Teiler von [mm] $a_0$ [/mm] ist. Wenn wir
nun wissen, dass die letzte Folgerung stimmt, dann schließen wir insgesamt:
Die Folgerung:
(*) "43 teilt [mm] $a_k$ $\Longrightarrow$ [/mm] 43 teilt [mm] $a_{k+1}$"
[/mm]
zeigt, dass gilt:
Weil 43 [mm] $a_0$ [/mm] teilt, teilt 43 auch [mm] $a_1$.
[/mm]
Die gleiche Folgerung (*) zeigt dann aber auch:
Weil 43 [mm] $a_1$ [/mm] teilt, teilt 43 auch [mm] $a_2$.
[/mm]
etc. pp.
Jetzt zur Aufgabe:
VORAUSSETZUNG (I.V.): $k [mm] \in \IN_0$ [/mm] ist so, dass
43 teilt [mm] $a_k=6^{k+2}+7^{2k+1}$
[/mm]
INDUKTIONSSCHRITT: Unter der Voraussetzung (I.V.) ist zu begründen, dass
auch [mm] $43\,$ [/mm] ein Teiler von [mm] $a_{k+1}$ [/mm] sein muss.
1.) Wie sieht [mm] $a_{k+1}$ [/mm] aus? Naja, ersetze in der Definition von [mm] $a_k$ [/mm] überall
[mm] $k\,$ [/mm] durch $k+1$ (gerne mit zusätzlichen Klammern).
Es ist also
[mm] $a_{\red{k+1}}=6^{\red{(k+1)}+2}+7^{2\red{(k+1)}+1}=6^{k+3}+7^{2k+3}$
[/mm]
Jetzt weißt Du aber nur was über [mm] $a_k=6^{k+2}+7^{2k+1}\,.$ [/mm] Es wäre also schön,
dieses irgendwie in [mm] $a_{k+1}$ [/mm] *sichtbar zu machen* (eine Idee wäre es, einfach
mal [mm] $a_k$ [/mm] abzuziehen und wieder draufzuaddieren; man sieht aber, dass das
Ganze damit nicht wirklich einfacher wird; wie man das sieht? Naja: Mach es
halt mal! ):
[mm] $a_{k+1}=6^{k+3}+7^{2k+3}=6*6^{k+2}+7^2*7^{2k+1}$
[/mm]
Das *Problem* ist nun, das wir so noch nirgends [mm] $a_k=6^{k+2}+7^{2k+1}$ [/mm] direkt sehen; wir wollen etwa
[mm] $a_{k+1}=irgendwas*a_k+\text{Korrektur}$
[/mm]
sehen. Das wäre dann toll, wenn wir danach erkennen, dass auch [mm] $\text{Korrektur}$
[/mm]
durch 43 teilbar ist.
Naheliegend sind dann folgende Ansätze:
1.) [mm] $a_{k+1}=6*a_k+\text{Korrektur}$
[/mm]
oder
2.) [mm] $a_{k+1}=7^2*a_k+\text{Korrektur '}$ [/mm] (hier haben wir ja eine andere Korrektur,
daher am Ende der ' dran!).
Ist Dir klar, warum?
Verfolgt man den ersten Weg, so erkennt man wegen
[mm] $6*a_k=6*(6^{k+2}+7^{2k+1})$,
[/mm]
dass dort
[mm] $\text{Korrektur}=(7^2-6)*7^{2k+1}=43*7^{2k+1}$
[/mm]
vorzunehmen ist. (Das ist toll, oder?)
Verfolgt man den Weg 2.):
Wegen
[mm] $a_{k+1}-7^2*(\overbrace{6^{k+2}+7^{2k+1}}^{=a_k})=6^{k+3}-7^{2k+3}-7^2*6^{k+2}-7^{2k+3}=(6-7^2)*6^{k+2}$
[/mm]
ist [mm] $\text{Korrektur '}=(6-7^2)*6^{k+2}$ [/mm] zu setzen; also
[mm] $\text{Korrektur '}=(-43)*6^{k+2}$
[/mm]
Auch das wäre toll; oder?
Man kann sowas übrigens auch mal sporadisch kontrollieren; ich mache es
mal für den Fall der Vorgehensweise von 2.).
Für $k=4$ ist
[mm] $a_k=a_4=6^{k+2}+7^{2k+1}=6^6+7^9=40400263\,.$
[/mm]
Also
(*) [mm] $a_{k+1}=a_5=6^7+7^{11}=1977606679\,.$
[/mm]
Nun ist [mm] $7^2*a_4=49*a_4=\red{1979612887}\,.$ [/mm] Addieren wir zur letzten Zahl noch die [mm] $\text{Korrektur '}$ [/mm]
(für [mm] $k=4\,$) [/mm] von
[mm] $-43*6^{k+2}=-43*6^6=-2006208\,,$
[/mm]
so sollten wir bei [mm] $a_5$ [/mm] ankommen:
[mm] $\red{1979612887}-2006208=1977606679\,.$
[/mm]
Vergleiche das mit (*) und Du siehst: passt!
Gruß,
Marcel
|
|
|
|