Vollständige Induktion - Teilbarkeitsrelation

21.11.2016, 11:07

MioMioMathe

Vollständige Induktion - Teilbarkeitsrelation

Hallo!

Ich habe folgende Aufgabenstellung und frage mich wie ich diese zu verstehen habe:

A: Für alle natürlichen Zahlen n gilt $\begin{eqnarray*} n^3-n \end{eqnarray*}$ ist durch 6 teilbar.

(Beweis mittels vollständiger Induktion)

Ist das nun folgendermaßen zu verstehen: $\begin{eqnarray*} n^3-n \end{eqnarray*}$ | 6
also mittels Teilbarkeitsrelation oder als Bruch mit der Aussage dividiert durch 6?

Ersteres erscheint mir sinnvoller da so eine vernünftige Aussage entsteht.

Was meint ihr?

21.11.2016, 11:15

HAL 9000

Auf diesen Beitrag antworten »

Symbolik $\begin{align*} a \mid b \end{align*}$ bedeutet, dass $\begin{align*} a \end{align*}$ ein Teiler von $\begin{align*} b \end{align*}$ ist bzw. anders formuliert, $\begin{align*} b \end{align*}$ durch $\begin{align*} a \end{align*}$ teilbar ist.

In dem Sinne muss es hier $\begin{align*} 6 \mid (n^3-n) \end{align*}$ lauten.

Zitat:

Original von MioMioMathe
oder als Bruch mit der Aussage dividiert durch 6?

Im Fall $\begin{align*} a\neq 0 \end{align*}$ ist Aussage $\begin{align*} a \mid b \end{align*}$ äquivalent zu $\begin{align*} \frac{b}{a}\in\mathbb{Z} \end{align*}$ .

D.h., die Behauptung könnte hier auch so formuliert werden: $\begin{align*} \frac{n^3-n}{6}\in\mathbb{Z} \end{align*}$ für alle $\begin{align*} n\in\mathbb{N} \end{align*}$

Ich nehme an, das ist es, was du da meinst.

21.11.2016, 11:24

klarsoweit

Auf diesen Beitrag antworten »

Nebenbei: der Beweis geht auch ohne vollständige Induktion. Aber das Beweisverfahren soll hier ja wohl geübt werden. smile

21.11.2016, 11:36

MioMioMathe

Auf diesen Beitrag antworten »

Ja genau, das meinte ich!

Oh, klar, so rum habe ich mir das auch aufgeschrieben... Hammer

Zitat:

Original von HAL 9000
In dem Sinne muss es hier $\begin{align*} 6 \mid (n^3-n) \end{align*}$ lauten.

Ich werde dann die Teilbarkeitsrelation verwenden, da bei mir gilt N inkl. 0.

Danke! smile

21.11.2016, 12:14

MioMioMathe

Auf diesen Beitrag antworten »

Wirklich weit komme ich leider nicht, vielleicht könnt ihr mir ja weiterhelfen...

$\begin{eqnarray*} A(n) : \forall n \in N : 6 \mid n^3 - n \end{eqnarray*}$

I.A.: n = 0

$\begin{eqnarray*} 6 \mid 0^3 - 0 \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow \end{eqnarray*}$ 6 ist teiler von 0.

I.V.: A(n) ist wahr für ein festes aber beliebiges $\begin{eqnarray*} n \in N \end{eqnarray*}$ .

I.S.: Zeige A(n+1) ist wahr.

$\begin{eqnarray*} 6 \mid (n+1)^3 - (n+1) \end{eqnarray*}$

$\begin{eqnarray*} 6 \mid (n+1)^3 - n-1 \end{eqnarray*}$

Dann multipliziere ich mit *(-1), damit ich ein n+1 habe:

$\begin{eqnarray*} 6 \mid -(n+1)^3 + n+1 \end{eqnarray*}$

Und da ich nun ein alleinstehendes n+1 habe ist die Aussage somit bewiesen?

Damit würde jedoch immer eine negative Zahl geteilt werden, aber die Teilbarkeitsrelation würde das ja auch erlauben.

21.11.2016, 12:50

HAL 9000

Auf diesen Beitrag antworten »

Wie kommst du darauf, dass du damit irgendwas bewiesen hast? Außer Aufstellen der Induktionsbehauptung und einer Multiplikation mit (-1), deren Sinn mir verborgen ist, hast du doch nichts im Induktionsschritt getan? Erstaunt1

21.11.2016, 12:53

klarsoweit

Auf diesen Beitrag antworten »

Zitat:

Original von MioMioMathe
Dann multipliziere ich mit *(-1), damit ich ein n+1 habe:

$\begin{eqnarray*} 6 \mid -(n+1)^3 + n+1 \end{eqnarray*}$

Wozu das? Du hattest doch vorher auch schon ein (n+1) .

Zitat:

Original von MioMioMathe
Und da ich nun ein alleinstehendes n+1 habe ist die Aussage somit bewiesen?

Nee, was hat der Beweis der Teilbarkeit durch 6 mit einem "alleinstehenden n+1" zu tun? verwirrt

Du mußt zeigen, daß 6 ein Teiler von (n+1)³ - (n+1) ist. Dazu darfst du die Induktionsvoraussetzung (6 ist Teiler von n³ - n) verwenden. Ich würde mal (n+1)³ ausrechnen und etwas zusammenfassen. smile

21.11.2016, 13:15

MioMioMathe

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Wie kommst du darauf, dass du damit irgendwas bewiesen hast? Außer Aufstellen der Induktionsbehauptung und einer Multiplikation mit (-1), deren Sinn mir verborgen ist, hast du doch nichts im Induktionsschritt getan? Erstaunt1

Hmh, dann habe ich nicht verstanden worauf ich hinaus soll verwirrt

21.11.2016, 13:17

MioMioMathe

Auf diesen Beitrag antworten »

Zitat:

Original von klarsoweit
Du mußt zeigen, daß 6 ein Teiler von (n+1)³ - (n+1) ist. Dazu darfst du die Induktionsvoraussetzung (6 ist Teiler von n³ - n) verwenden. Ich würde mal (n+1)³ ausrechnen und etwas zusammenfassen. smile

Dann habe ich folgendes heraus:

n * ((n + 2) * (n + 1))

nur was kann ich damit jetzt anfangen? verwirrt

21.11.2016, 13:29

klarsoweit

Auf diesen Beitrag antworten »

Nun ja, ich hatte eher an so etwas gedacht: $\begin{eqnarray*} (n+1)^3 - (n+1) = n^3 + 3n^2 + 3n + 1 - n - 1 = (n^3 - n) + (3n \cdot (n+1)) \end{eqnarray*}$

Wie sieht es nun mit der Teilbarkeit durch 6 bei den eingeklammerten Summanden aus?

21.11.2016, 13:40

MioMioMathe

Auf diesen Beitrag antworten »

Zitat:

Original von klarsoweit
Nun ja, ich hatte eher an so etwas gedacht: $\begin{eqnarray*} (n+1)^3 - (n+1) = n^3 + 3n^2 + 3n + 1 - n - 1 = (n^3 - n) + (3n \cdot (n+1)) \end{eqnarray*}$

Wie sieht es nun mit der Teilbarkeit durch 6 bei den eingeklammerten Summanden aus?

Achsoooooo... ich muss auf jeden fall wieder die Induktionsvoraussetzung im Term stehen haben, richtig?

Nach I.V. gilt, das der erste Summand durch 6 teilbar ist. Und der zweite Summand ist ebenfalls immer durch 6 teilbar. Nur wie erkläre ich das für den zweiten Summanden?

21.11.2016, 13:50

HAL 9000

Auf diesen Beitrag antworten »

Irgenwie ein mühsames Geschäft: Der Induktionsschritt benötigt dann die Aussage

Zitat:

B: Für alle natürlichen Zahlen $\begin{eqnarray*} n \end{eqnarray*}$ ist $\begin{eqnarray*} n(n+1) \end{eqnarray*}$ durch 2 teilbar.

also dieselbe Art Aussage wie die eigentliche Behauptung, nur eine Nummer kleiner.

-----------------------------------------------------------------

Mein Vorschlag wäre komplett anders: Man weist

Zitat:

C: Jeder Binomialkoeffizient $\begin{align*} \binom{m}{k} \end{align*}$ mit $\begin{align*} m\in\mathbb{Z},k\in\mathbb{N}_0 \end{align*}$ ist eine ganze Zahl.

nach, zunächst für $\begin{align*} m\geq k \end{align*}$ per Induktion über $\begin{align*} m \end{align*}$ , später dann auch für $\begin{align*} m<k \end{align*}$ durch Zusatzbetrachtungen. Die Behauptung hier im Thread ist dann der Spezialfall $\begin{align*} m=n+1,k=3 \end{align*}$ .

21.11.2016, 13:51

klarsoweit

Auf diesen Beitrag antworten »

Zitat:

Original von MioMioMathe
Achsoooooo... ich muss auf jeden fall wieder die Induktionsvoraussetzung im Term stehen haben, richtig?

Das wäre vorteilhaft, wenn man die Induktionsvoraussetzung nutzen möchte. smile

Zitat:

Original von MioMioMathe
Und der zweite Summand ist ebenfalls immer durch 6 teilbar. Nur wie erkläre ich das für den zweiten Summanden?

Nun ja, von den Faktoren n und (n+1) ist genauer einer gerade. Davor steht noch der Faktor 3. Insgesamt muß also 3n * (n+1) durch 6 teilbar sein. War das jetzt so schwer?

Nehmen wir nochmal n³ - n. Es ist $\begin{eqnarray*} n^3 - n = (n-1) \cdot n \cdot (n+1) \end{eqnarray*}$ .
Offensichtlich ist einer der Faktoren durch 3 teilbar und einer durch 2 teilbar. Insgesamt ist das also durch 6 teilbar. Augenzwinkern