TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2025W/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 ist als solved markiert. Ist dies falsch oder ungenau? Aktualisiere den Lösungsstatus (Details: Vorlage:Beispiel)

Lösungsvorschlag

Induktionsvoraussetzung:

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

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

Induktionsanfang:

$\begin{array}{c}P(0)=6|7^0-1\iff 6|0\\ P(1)=6|7^1-1\iff 6|6\end{array}$

(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{array}{cc}P(n+1)=& 6|7^{n+1}-1\\ \\ 7^{n+1}-1=& 7\ast 7^n\stackrel{\text{einfach hinzufügen}}{\overbrace{-7^n+7^n}}-1\stackrel{I.V.}{\iff }7\ast 7^n-7^n+6\ast m\\ =& 6\ast 7^n+6\ast m\\ \\ \end{array}$

$7\ast 7^n-1=6\ast 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{array}{ccc}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.}\\ & ⟹6|7(7^n-1),6|6\\ \end{array}$