Beweis zur Teilbarkeit durch 3 per vollständiger Induktion

27.09.2010, 11:12

calculon102

Beweis zur Teilbarkeit durch 3 per vollständiger Induktion

Hallo zusammen,

ich habe vorgestern eine Klausur geschrieben und an einer Aufgabe festgehangen, die mir bis heute keine Ruhe lässt:

Zitat:

Beweisen Sie 3 teilt $\begin{eqnarray*} 5^n + (-1)^n * 2 \end{eqnarray*}$ für alle $\begin{eqnarray*} n \in ~\mathbb N_0 \end{eqnarray*}$ .

Der Beweis sollte über vollständige Induktion erfolgen. Induktionsanfang ist auch kein Problem.

Mir sind dir Formalien zum Beweis von Teilbarkeit auch soweit klar, aber bei der notwendigen Umformung der Induktion habe ich irgendwie ein Brett vorm Kopf.

Meine Ansätze wären zum Beispiel Umformungen oder andere Darstellungen wie
$\begin{eqnarray*} (2+3)5^{n-1} + (-2)(-1)^{n-1} \end{eqnarray*}$

oder
$\begin{eqnarray*} (6 -1)5^{n-1} + (-2)(-1)^{n-1} \end{eqnarray*}$

Des weiteren könnte man differenzieren, ob n gerade oder ungerade ist und damit schon den rechten Summanden auflösen. Denn wenn n gerade, dann:
$\begin{eqnarray*} (6 -1)5^{n-1} + 2 \end{eqnarray*}$

Bzw., wenn n ungerade dann:
$\begin{eqnarray*} (6 -1)5^{n-1} - 2 \end{eqnarray*}$

Aber ich sehe einfach nicht den Ansatz für weitere Umformungen. Hilfe!

27.09.2010, 11:51

riwe

Auf diesen Beitrag antworten »

RE: Beweis zur Teilbarkeit durch 3 per vollständiger Induktion
eine idee:
a) sei n gerade
nach voraussetzung $\begin{eqnarray*} 5^n+2 \end{eqnarray*}$ durch 3 teilbar

$\begin{eqnarray*} n+1\to 5^{n+1}-2 =5\cdot(5^n+2)-12..... \end{eqnarray*}$

usw. Augenzwinkern

27.09.2010, 12:19

calculon102

Auf diesen Beitrag antworten »

RE: Beweis zur Teilbarkeit durch 3 per vollständiger Induktion
Danke! Das würde ich als nicht-Professor schon als Beweis akzeptieren. smile

Aber wie bist Du konkret auf die korrekten -12 nach der Herausnahme der 5er Potenz gekommen? Pure Erfahrung? Augenzwinkern

Zitat:

Original von riwe
$\begin{eqnarray*} n+1\to 5^{n+1}-2 =5\cdot(5^n+2)-12..... \end{eqnarray*}$

27.09.2010, 12:41

riwe

Auf diesen Beitrag antworten »

RE: Beweis zur Teilbarkeit durch 3 per vollständiger Induktion

Zitat:

Original von calculon102
Danke! Das würde ich als nicht-Professor schon als Beweis akzeptieren. smile

Aber wie bist Du konkret auf die korrekten -12 nach der Herausnahme der 5er Potenz gekommen? Pure Erfahrung? Augenzwinkern

Zitat:

Original von riwe
$\begin{eqnarray*} n+1\to 5^{n+1}-2 =5\cdot(5^n+2)-12..... \end{eqnarray*}$

intuition

27.09.2010, 14:16

calculon102

Auf diesen Beitrag antworten »

RE: Beweis zur Teilbarkeit durch 3 per vollständiger Induktion

Zitat:

Original von riwe
intuition Augenzwinkern

Oje. Deswegen mag ich Beweisführungen in Klausuren nicht. Geht manchmal eher Richtung Rätselspiel, abhängig von Tagesform.

Aber müßte man nicht in so einem Beweis auch belegen, wie man auf die -12 kommt?
Ich meine, dann könnte ich ja auch keck schreiben, bei geraden n ist
$\begin{eqnarray*} 5^n + 2 \end{eqnarray*}$ immer durch 3 teilbar
und bei ungeraden n
$\begin{eqnarray*} 5^n - 2 \end{eqnarray*}$ ebenso immer durch 3 teilbar.
Ist doch offensichtlich! Augenzwinkern

27.09.2010, 14:41

riwe

Auf diesen Beitrag antworten »

RE: Beweis zur Teilbarkeit durch 3 per vollständiger Induktion

Zitat:

Original von calculon102

Zitat:

Original von riwe
intuition Augenzwinkern

ich sehe, du hast es nicht genau verstanden, wo es doch ziemlich offensichtlich ist - klar muß man das belegen

$\begin{eqnarray*} 5^{n+1}=5\cdot(5^n+2)-5\cdot 2\to 5^{n+1}-2=5\cdot(5^n+2)-12 \end{eqnarray*}$
und der 1. summand ist lt. IV durch 3 teilbar, 12 wohl auch Augenzwinkern

jetzt klar.
analog geht man bei ungeradem n vor

27.09.2010, 15:46

Pierre Vogel

Auf diesen Beitrag antworten »

RE: Beweis zur Teilbarkeit durch 3 per vollständiger Induktion
Alternativ:

Definiere zunächst $\begin{eqnarray*} a_{n+1}:=5a_n+12(-1)^{n+1},~a_1:=3. \end{eqnarray*}$

Offensichtlich sind alle $\begin{eqnarray*} a_n \end{eqnarray*}$ durch $\begin{eqnarray*} 3 \end{eqnarray*}$ teilbar.

Induktiv folgt

$\begin{eqnarray*} a_n=5^n+2(-1)^n \text{ für alle } n\geq1. \end{eqnarray*}$

27.09.2010, 16:19

calculon102

Auf diesen Beitrag antworten »

Zitat:

Original von riwe
$\begin{eqnarray*} 5^{n+1}=5\cdot(5^n+2)-5\cdot 2\to 5^{n+1}-2=5\cdot(5^n+2)-12 \end{eqnarray*}$
und der 1. summand ist lt. IV durch 3 teilbar, 12 wohl auch Augenzwinkern

Ich denke: ich begreife langsam. In der Schreibweise für mich persönlich so klarer:
$\begin{eqnarray*} 5^{n+1}=5 ( (5^n+2) - 2 ) \to 5^{n+1}-2=5 ( (5^n+2) - 2 ) - 2 \end{eqnarray*}$

Mir fällt der Gedankengang noch schwer die 2 doppelt abzuziehen, also das in $\begin{eqnarray*} 5^{n+1} \end{eqnarray*}$ zwar schon -2 drinsteckt, aber daraus dann nochmal für $\begin{eqnarray*} 5^{n+1} -2 \end{eqnarray*}$ eine Folgerung gezogen wird.

Je länger ich darüber nachdenke allerdings auch logisch. Aber müssen wir nicht noch zusätzlich beweisen, dass
$\begin{eqnarray*} 5^{n} + 2 \end{eqnarray*}$ wenn n gerade
bzw.
$\begin{eqnarray*} 5^{n} - 2 \end{eqnarray*}$ wenn n ungerade
durch 3 teilbar ist, also die eigentliche Induktionsvoraussetzung belegen?

Danke nochmal!

Zitat:

Original von Pierre Vogel
Alternativ:

Definiere zunächst $\begin{eqnarray*} a_{n+1}:=5a_n+12(-1)^{n+1},~a_1:=3. \end{eqnarray*}$
Offensichtlich sind alle $\begin{eqnarray*} a_n \end{eqnarray*}$ durch $\begin{eqnarray*} 3 \end{eqnarray*}$ teilbar.

Induktiv folgt $\begin{eqnarray*} a_n=5^n+2(-1)^n \text{ für alle } n\geq1. \end{eqnarray*}$

Respekt für die kreative Lösung. Da wäre ich im Leben nicht drauf gekommen. Ich hoffe nicht, dass so die Musterlösung ausschaut. Augenzwinkern

27.09.2010, 16:52

tmo

Auf diesen Beitrag antworten »

Folgende Lösung sehen auch kreativ aus, man muss aber nur die richtigen Methoden kennen, ist alles kein Hexenwerk Augenzwinkern

$\begin{eqnarray*} 5^n+2(-1)^n=3\left((-1)^n+2\sum_{k=0}^{n-1} 5^k(-1)^{n-k} \right) \end{eqnarray*}$

Oder so:

$\begin{eqnarray*} a_0=3, a_1=3, a_{n+2}=4a_{n+1}+5a_n \end{eqnarray*}$

Jedes Folgenglied ist durch 3 teilbar und induktiv folgt auch hier $\begin{eqnarray*} a_n = 5^n +2(-1)^n \end{eqnarray*}$

28.09.2010, 08:56

calculon102

Auf diesen Beitrag antworten »

Zitat:

Original von tmo
Folgende Lösung sehen auch kreativ aus, man muss aber nur die richtigen Methoden kennen, ist alles kein Hexenwerk Augenzwinkern

Das glaub ich Dir. smile

Aber ginge es nicht auch "einfacher" so in der Richtung zum Beispiel:
$\begin{eqnarray*} 5^{n+1} + (-1)^{n+1} \cdot 2 = (3+2)5^n + (-1)^{n+1} \cdot 2 = 3 \cdot 5^n + 2(5^n + (-1)^{n+1}) \end{eqnarray*}$
Wie auch immer es danach weitergeht? Oder bin ich damit in einer Sackgasse?

28.09.2010, 16:33

tmo

Auf diesen Beitrag antworten »

Du meinst jetzt als Induktionsbeweis? Dann wärst du auf dem richtigen Weg

Neue Frage »

Antworten »

Beweis zur Teilbarkeit durch 3 per vollständiger Induktion

Verwandte Themen