TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 3

Man zeige durch vollständige Induktion, dass $7^{n}-1$ für alle $n\in \mathbb {N}$ durch 6 teilbar ist.

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

Lösungsvorschlag

Induktionsvoraussetzung:

$P(n):=6|7^{n}-1\Leftrightarrow 7^{n}-1=6*k,k\in \mathbb {N}$

($6|$ bedeutet '6 ist ein Teiler von')

Induktionsanfang:

${\begin{aligned}P(0)=6|7^{0}-1\Leftrightarrow 6|0\\P(1)=6|7^{1}-1\Leftrightarrow 6|6\end{aligned}}$

(nicht notwendig, nur zur Veranschaulichung, P(0) ist ausreichend)

Induktionsschritt:

$P(n)\Rightarrow P(n+1)$

Induktionsbehauptung von scatmike:

Anmerkung: Der Trick ist $7^{n}-7^{n}$ in den Term hineinzunehmen, dann kann man mit der Induktionsvorraussetzung substituieren

${\begin{aligned}P(n+1)=&\ 6|7^{n+1}-1\\\\7^{n+1}-1=&\ 7*7^{n}\overbrace {-7^{n}+7^{n}} ^{\text{einfach hinzufügen}}-1\ {\overset {I.V.}{\Leftrightarrow }}\ 7*7^{n}-7^{n}+6*m\\=&\ 6*7^{n}+6*m\\\\\end{aligned}}$

$7*7^{n}-1=6*7^{n}+7^{n}-1$

Induktionsbehauptung mit Ergänzen auf vollständiges Quadrat

Hier ist der Trick die Ergänzung auf ein vollständiges Quadrat zu verwenden um auf unsere Induktionsvoraussetzung (I.V.) zu kommen. Dann können wir sagen, dass dieser Term durch 6 teilbar ist.

${\begin{aligned}P(n+1)&=7^{n+1}-1&\\&=7\cdot 7^{n}-1&{\text{Auf vollständiges Quadrat bringen}}\\&=7\cdot (7^{n}-1)+6&(7^{n}-1){\text{ war unsere I.V.}}\\&\implies 6|7(7^{n}-1),\;6|6\\\end{aligned}}$