Vollständige Induktion: Teilbarkeit beweisen

Question

Ich brauche Hilfe bei der folgenden Aufgabe zur Vollständigen Induktion:

a > 1: (a-1) teilt (aⁿ-1)

Ich verstehe überhaupt nicht, wie ich hierbei vorgehen muss und wäre für ein paar Tipps sehr dankbar.

Answer 1

I.Anfang: n=1 → a-1=a-1 ✓

I.Voraussetzung: k₁*(a-1)=aⁿ-1 gilt

I.Schritt: k₂*(a-1)=aⁿ⁺¹-1 ist zu zeigen.

a^{n+1}-1=a*a^n -1=a*(k1*(a-1)+1)-1

=k1*a*(a-1)+a-1

=(k1*a+1)*(a-1) ✓

k2=k1*a+1

:-)

Comments

Vielen Dank !

---

Gerne. Hast du es denn verstanden?

---

Ich habe es gerade nochmal versucht nachzuvollziehen. Aber ehrlich gesagt ist mir nicht ganz ersichtlich, wo das k1 und k2 herkommt, da ich bisher auf die Art und Weise noch keine Aufgabe gelöst habe ..

---

Ein Beispiel:

"5 ist ein Teiler von 35" kann ich auch so schreiben: "Es gibt eine natürliche Zahl k, sodass gilt k*5=35".

---

Okay das ist nachvollziehbar, danke für das Beispiel. Aber was genau passiert bei folgenden Schritt: a*an -1 = a*(k1*(a-1)+1)-1 (Erste Zeile deiner Lösung)

---

Da habe ich die IV eingesetzt.

a^n=...+1

:-)

Answer 2

Aloha :)

1) Verankerung bei \(n=1\)$$\frac{a^n-1}{a-1}=\frac{a^1-1}{a-1}=1\in\mathbb N\quad\checkmark$$

2) Induktionsschritt:

Nach Voraussetzung existiert ein \(m=\frac{a^n-1}{a-1}\) mit \(m\in\mathbb N\). Damit gilt:

$$\frac{a^{n+1}-1}{a-1}=\frac{a^{n+1}}{a-1}-\frac{1}{a-1}=a\,\frac{a^{n}}{a-1}-\frac{1}{a-1}=a\,\frac{a^{n}-1+1}{a-1}-\frac{1}{a-1}$$$$=a\left(\frac{a^n-1}{a-1}+\frac{1}{a-1}\right)-\frac{1}{a-1}=a\left(m+\frac{1}{a-1}\right)-\frac{1}{a-1}$$$$=am+\frac{a}{a-1}-\frac{1}{a-1}=am+\frac{a-1}{a-1}=am+1\in\mathbb N\quad\checkmark$$

Answer 3

Ist folgender Satz bekannt (sodass er als Beweismittel verwendet werden kann)?

Aus m|b und m|c folgt m|(b+c) .

Im Induktionsbeweis lässt sich

\(a^{n+1}\) schreiben als \(a^{n+1}-a^n+a^n\).

Somit gilt \(a^{n+1}-1=a^{n+1}-a^n+a^n-1=(a^{n+1}-a^n)+(a^n-1)\).

Da sich \((a^{n+1}-a^n)\) durch Ausklammern als Produkt   \(a^{n}(a-1)\) schreiben lässt, gilt also

\((a^{n+1}-a^n)+(a^n-1)= a^{n}(a-1)+(a^n-1) \).

Der erste Summand ist wegen des Vorhandenseins des Faktors (a-1) (und der Ganzzahligkeit von a^n) durch (a-1) teilbar, und der zweite Summand ist durch (a-1) teilbar laut Induktionsvoraussetzung.

Comments

Danke für die ausführliche Beschreibung. Könntest du ein paar Wörter zu dem Satz:

Aus m|b und m|c folgt m|(b+c) , sagen ? Der war mir bisher nicht bekannt und wurde an der Hochschule auch nicht behandelt.