Induktion

21.02.2019, 22:44

Einstein1879

Induktion

Guten Abend,

ich soll zeigen, dass die Zahl $\begin{eqnarray*} n^4-4n^2 \end{eqnarray*}$ für jede natürliche Zahl $\begin{eqnarray*} n \geq 3 \end{eqnarray*}$ durch $\begin{eqnarray*} 3 \end{eqnarray*}$ teilbar ist.

Dazu verwende ich die Vollständige Induktion.

Für den Induktionsanfang, gilt :

$\begin{eqnarray*} n=3 \end{eqnarray*}$

$\begin{eqnarray*} 3^4-4 \cdot 3^2=81-36=45 \end{eqnarray*}$

$\begin{eqnarray*} 3 | 45 \end{eqnarray*}$ Somit gilt es schonmal für $\begin{eqnarray*} n=3 \end{eqnarray*}$ .

Der Induktionsschritt, lautet

$\begin{eqnarray*} (n+1)^4-4 \cdot (n+1)^2=n^4+4n^3-2n^2-4n-3=(n^4-4n^2)+4n^3+2n^2-4n-3 \end{eqnarray*}$

Aber jetzt komme ich nicht weiter.

22.02.2019, 00:02

Dopap

Auf diesen Beitrag antworten »

und wo ist die Induktionsannahme?
und das 3 ist Teiler von könnte man noch formal hinschreiben.

22.02.2019, 00:12

mYthos

Auf diesen Beitrag antworten »

Ich sehe zunächst einen Rechenfehler:

Zitat:

Original von Einstein1879
...
Der Induktionsschritt, lautet

$\begin{eqnarray*} (n+1)^4-4 \cdot (n+1)^2=n^4+4n^3\color{red}-\color{black}2n^2-4n-3=(n^4-4n^2)+4n^3+\color{red}2\color{black}n^2-4n-3 \end{eqnarray*}$
...

Richtig ist: $\begin{eqnarray*} (n+1)^4-4 \cdot (n+1)^2=n^4+4n^3\color{red}+\color{black}2n^2-4n-3=(n^4-4n^2)+4n^3+\color{red}6\color{black}n^2-4n-3 \end{eqnarray*}$

Jetzt wirst du vermutlich weiterkommen; denn $\begin{eqnarray*} 6n^2 - 3 \end{eqnarray*}$ kannst du als weiteren durch 3 teilbaren Term herausnehmen.
(Der Rest ist geschickt zerlegbar; die Faktoren können modulo 3 schnell untersucht werden ..)

mY+

22.02.2019, 09:48

Matt Eagle

Auf diesen Beitrag antworten »

Geht auch ohne Induktion!
Wie so oft, kann man auch hier mittels folgender Zerlegung

$\begin{eqnarray*} n^4-4n^2=(n-1)\cdot n^2\cdot (n+1)-3n^2 \end{eqnarray*}$

die Teilbarkeit durch 3 direkt ablesen.

22.02.2019, 10:09

HAL 9000

Auf diesen Beitrag antworten »

Das Beispiel zeigt deutlich, dass Induktion nicht immer eine gute Idee ist:

Für $\begin{eqnarray*} f(n)=n^4-4n^2 \end{eqnarray*}$ ist der im Induktionsschritt betrachteten Differenz $\begin{eqnarray*} f(n+1)-f(n)=4n^3+6n^2-4n-3 \end{eqnarray*}$ kaum besser (manche würden sogar sagen: schlechter) die Teilbarkeit durch 3 anzusehen als $\begin{eqnarray*} f(n) \end{eqnarray*}$ selbst. Insofern ist die Induktion hier nur unnötiger Ballast.

22.02.2019, 10:47

klarsoweit

Auf diesen Beitrag antworten »

Zum Üben der Vollständigen Induktion ist das Beispiel durchaus praktikabel. Es kommt mal wieder auf die Aufgabenstellung an. smile

22.02.2019, 11:17

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von klarsoweit
Zum Üben der Vollständigen Induktion ist das Beispiel durchaus praktikabel.

Da hab ich eine Idee, wie man hier noch viel mehr Induktion üben kann: Indem man eine nette Kette von Induktionsbeweisen aufbaut!

Für $\begin{eqnarray*} f(n)=n^4-4n^2 \end{eqnarray*}$ soll die Teilbarkeit durch 3 nachgewiesen werden.

Im Induktionsschritt benöten wir dazu die Teilbarkeit durch 3 für $\begin{eqnarray*} f_1(n):=f(n+1)-f(n) = 4n^3+6n^2-4n-3 \end{eqnarray*}$ . Dafür starten wir eine eigene "Induktion 2":

In deren Induktionsschritt benöten wir die Teilbarkeit durch 3 für $\begin{eqnarray*} f_2(n):=f_1(n+1)-f_1(n) = 12n^2+24n+6 \end{eqnarray*}$ . Hier können wir stoppen, denn dieser Term ist erkennbar durch 3 teilbar.

Jetzt müssen noch die beiden Induktionsanfänge ergänzt werden, und wir sind fertig. Big Laugh

Aber warum nur gefällt mir der Weg von Matt Eagle besser? smile

22.02.2019, 11:54

Einstein1879

Auf diesen Beitrag antworten »

Ich danke euch sehr. Das mit dem Rechenfehler, war mir leider nicht aufgefallen.

22.02.2019, 13:45

Huggy

Auf diesen Beitrag antworten »

Der Weg von Matt Eagle ist natürlich sehr schön. Aber dazu muss man seine Umformung erst mal sehen. Simple Kongruenzrechnung führt ohne Nachdenken zum Ziel:

$\begin{eqnarray*} a)\quad n \equiv 0 \mod 3 \rightarrow n^4-4n^2 \equiv 0 \mod 3 \end{eqnarray*}$

$\begin{eqnarray*} b)\quad n \equiv \pm 1 \mod 3 \end{eqnarray*}$

$\begin{eqnarray*} \rightarrow n^2 \equiv 1 \mod 3, \quad n^4 \equiv 1 \mod 3 \end{eqnarray*}$

$\begin{eqnarray*} n^2 \equiv 1 \mod 3 \rightarrow 4n^2 \equiv 4 \equiv 1 \mod 3 \end{eqnarray*}$

$\begin{eqnarray*} \rightarrow n^4-4n^2 \equiv 1-1 =0 \mod 3 \end{eqnarray*}$

22.02.2019, 14:53

HAL 9000

Auf diesen Beitrag antworten »

Generelle Überlegung für solche Polynome $\begin{eqnarray*} p(n) = \sum_{k=0}^m a_k n^k \end{eqnarray*}$ mit rationalen Koeffizienten $\begin{eqnarray*} a_0,\ldots,a_m \end{eqnarray*}$ :

Es gilt genau dann $\begin{eqnarray*} p(n)\in\mathbb{Z} \end{eqnarray*}$ für alle $\begin{eqnarray*} n\in\mathbb{N} \end{eqnarray*}$ (bzw. sogar $\begin{eqnarray*} n\in\mathbb{Z} \end{eqnarray*}$ ) wenn in der alternativen Darstellung $\begin{eqnarray*} p(n) = \sum_{k=0}^m b_k \binom{n}{k} \end{eqnarray*}$ alle Koeffizienten $\begin{eqnarray*} b_0,\ldots,b_m \end{eqnarray*}$ ganzzahlig sind.

Es gilt übrigens der direkte Zusammenhang $\begin{eqnarray*} b_k = p^{\langle k\rangle}(0) \end{eqnarray*}$ , wobei $\begin{eqnarray*} p^{\langle k\rangle} \end{eqnarray*}$ für die iterierten Differenzen der Funktion $\begin{eqnarray*} p \end{eqnarray*}$ steht, d.h., mit $\begin{eqnarray*} p^{\langle 0\rangle} = p \end{eqnarray*}$ sowie $\begin{eqnarray*} p^{\langle k+1\rangle}(n):=p^{\langle k\rangle}(n+1)-p^{\langle k\rangle}(n) \end{eqnarray*}$ .

Im vorliegenden Fall klappt das mit $\begin{eqnarray*} p(n) = \frac{1}{3}\left(n^4-4n^2\right) \stackrel{!}{=} 8\binom{n}{4} + 12\binom{n}{3} + 2\binom{n}{2} - \binom{n}{1} \end{eqnarray*}$ .

22.02.2019, 19:26

klauss

Auf diesen Beitrag antworten »

Und da habe ich gestern Abend geraume Zeit rumprobiert, um eine "schöne" Lösung zu finden wie sonst bei Induktion meistens üblich. Erst nachdem mYthos auch keine liefern konnte, habe ich mich dazu durchgerungen, das Restproblem umständlich zu erledigen. Man kann ja noch für $\begin{eqnarray*} n^{3}-n \end{eqnarray*}$ eine zweite Neben-Induktion durchführen, die geht dann schön auf. In diesem Sinne hat klarsoweit wiederum Recht.

22.02.2019, 20:18

Mathema

Auf diesen Beitrag antworten »

Zitat:

Original von Huggy
Der Weg von Matt Eagle ist natürlich sehr schön. Aber dazu muss man seine Umformung erst mal sehen.

Offensichtlich ist aber $\begin{eqnarray*} n^4-4n^2=n^2(n^2-4)=n^2(n+2)(n-2) \end{eqnarray*}$ . Und damit lässt sich ja auch gut arbeiten.

Wink

22.02.2019, 21:24

mYthos

Auf diesen Beitrag antworten »

Zitat:

Original von klauss
... eine "schöne" Lösung zu finden wie sonst bei Induktion meistens üblich. Erst nachdem mYthos auch keine liefern konnte, ...

Na ja, über "schön" kann man verschiedener Ansicht sein. Und die Aufgabenstellung bestand ja darin, Induktion zu verwenden!

Zitat:

Original von mYthos
...
Richtig ist: $\begin{eqnarray*} (n+1)^4-4 \cdot (n+1)^2=n^4+4n^3\color{red}+\color{black}2n^2-4n-3=(n^4-4n^2)+4n^3+\color{red}6\color{black}n^2-4n-3 \end{eqnarray*}$
...
... denn $\begin{eqnarray*} 6n^2 - 3 \end{eqnarray*}$ kannst du als weiteren durch 3 teilbaren Term herausnehmen.
(Der Rest ist geschickt zerlegbar; die Faktoren können modulo 3 schnell untersucht werden ..)
...

Und eine weitere Induktion an eine bestehende anzuhängen, fand ich jetzt auch nicht so prickelnd Big Laugh

Deshalb der Hinweis mit modulo 3.
Da es hier ja keine Komplettlösungen geben sollte, hätte ich zuerst gerne eine nachfolgende Rechnung von Einstein1879 gesehen, bevor dann in weitere Details gegangen wird.

mY+

22.02.2019, 21:32

Mathema

Auf diesen Beitrag antworten »

Zitat:

Original von mYthos
Und die Aufgabenstellung bestand ja darin, Induktion zu verwenden!

Wo steht das? Ich lese das hier

Zitat:

Original von Einstein1879
ich soll zeigen, dass die Zahl $\begin{eqnarray*} n^4-4n^2 \end{eqnarray*}$ für jede natürliche Zahl $\begin{eqnarray*} n \geq 3 \end{eqnarray*}$ durch $\begin{eqnarray*} 3 \end{eqnarray*}$ teilbar ist.

Dazu verwende ich die Vollständige Induktion.

jedenfalls nicht raus.

22.02.2019, 21:41

mYthos

Auf diesen Beitrag antworten »

Stimmt! Jedenfalls ist es nicht eindeutig, dass dezitiert Induktion gefordert ist.
Aber das wird wohl nur Einstein1879 selbst wissen ...

mY+

Neue Frage »

Antworten »

Induktion

Verwandte Themen