vollständige induktion (nicht teilbar)

Es bedeuten: {nl} \(a \mid b\)  a teilt b

\(a \nmid b\)  a teilt b nicht

(b) 

\(\begin{array}{rcl} \boxed{~ \begin{array}{rcl} 3^{2^{n+1}}-1 &=& \underbrace{\left( 3^{2^{n}} - 1 \right)^2}_{\text{1. Summand}} + \underbrace{2\cdot \left( 3^{2^{n}} - 1 \right)}_{2. Summand}\\ \end{array} ~}\\ \text{ Der erste Summand teilt } 2^{n+4} \ ?\\ \left( 3^{2^{n}} - 1 \right) & \mid & 2^{n+2} \qquad \text{laut } (a)\\ \left( 3^{2^{n}} - 1 \right)^2 & \mid & \left( 2^{n+2} \right)^2\\ \left( 3^{2^{n}} - 1 \right)^2 & \mid & 2^{(n+2)\cdot 2} \\ \left( 3^{2^{n}} - 1 \right)^2 & \mid & 2^{2n+4} \\ \left( 3^{2^{n}} - 1 \right)^2 & \mid & 2^{n+4+n} \\ \left( 3^{2^{n}} - 1 \right)^2 & \mid & 2^{(n+4)+n} \\ \left( 3^{2^{n}} - 1 \right)^2 & \mid & 2^{n+4}\cdot 2^n \\ \hline \text{ Der erste Summand teilt } 2^{n+4} \\ \left( 3^{2^{n}} - 1 \right)^2 & \mid & 2^{n+4}\cdot 2^n \ | \ 2^{n+4}\\ \hline \\ \text{ Der zweite Summand teilt nicht } 2^{n+4} \ ?\\ 2\cdot \left( 3^{2^{n}} - 1 \right) & \nmid & 2^{n+4}\\ \boxed{~3^{2^{n}} - 1 \nmid 2^{n+3}\quad \text{Induktionsvoraussetzung in }(b)~}\\ \left( 3^{2^{n}} - 1 \right) &\nmid & 2^{n+3}\\ 2\cdot \left( 3^{2^{n}} - 1 \right) &\nmid & 2\cdot 2^{n+3}\\ 2\cdot \left( 3^{2^{n}} - 1 \right) &\nmid & 2^{n+3+1}\\ 2\cdot \left( 3^{2^{n}} - 1 \right) &\nmid & 2^{n+4}\\ \end{array}\)

Das gedrehte Bild!!!

(a) Zeigen Sie mit vollständiger Induktion, dass \(3^{2^n} - 1 \text{ durch } 2^{n+2}\) teilbar ist.

Es bedeuten: 

\(a \mid b \)  a teilt b

\(a \nmid b\)  a teilt b nicht

Induktionsanfang:

Für n = 1 gilt:

\(\begin{array}{rcl} 3^{2^1} - 1 & \mid & \ 2^{1+2}\\ 8 & \mid & 8 \end{array} \)

Also 8 teilt 8 ist richtig!

Induktionsvoraussetzung:

\(\text{Es gelte }\quad 3^{2^n} - 1 \mid \ 2^{n+2}\\\)

Induktionsbehauptung:

\(3^{2^{(n+1)}} - 1 \mid \ 2^{(n+1)+2} \)

Beweis des Induktionsschritts \(n\rightarrow n+1:\)

\(\begin{array}{rcl} 3^{2^{n+1}} - 1 & \overset{?}{\mid} & \ 2^{(n+1)+2} \\ \boxed{~ \begin{array}{rcl} 3^{2^{n+1}}-1 &=& \left( 3^{2^{n}} - 1 \right)^2 + 2\cdot \left( 3^{2^{n}} - 1 \right)\\ 3^{2^{n+1}}-1 &=& 3^{2^{n}\cdot 2} -2\cdot 3^{2^{n}} + 1 + 2\cdot 3^{2^{n}} - 2\\ 3^{2^{n+1}}-1 &=& 3^{2^{n+1}} -1 \qquad \text{okay!}\\ \end{array} ~}\\ \left( 3^{2^{n}} - 1 \right)^2 + 2\cdot \left( 3^{2^{n}} - 1 \right) &\overset{?}{\mid} & \ 2^{(n+1)+2} \\ \left( 3^{2^{n}} - 1 \right) \left( 3^{2^{n}} - 1 + 2 \right) &\overset{?}{\mid} & \ 2^{(n+2)+1} \\ \underbrace{ \left( 3^{2^{n}} - 1 \right) }_{3^{2^n} - 1 \ \mid \ 2^{n+2}\ (\text{Induktionsannahme}) } \cdot \underbrace{ \left( 3^{2^{n}} +1 \right) }_{\text{immer durch 2 teilbar, weil gerade}} &\overset{?}{\mid} & \ 2^{n+2}\cdot 2 \\ \boxed{~ \begin{array}{rcl} 3^{2^{n}} +1 \qquad \text{immer durch 2 teilbar, }\\ \text{weil 3 ungerade ist }\\ \text{und } 3 \cdot 3 = 9 \text{ ungerade ist }\\ \text{und } 3\cdot 3 \cdot 3 = 27 \text{ ungerade ist.}\\ \text{Also } 3^x \text{ immer ungerade ist.}\\ \text{Eine ungerade Zahl mal einer ungeraden Zahl}\\ \text{bleibt eine ungerade Zahl!}\\ \text{Eine ungerade Zahl + 1 ist eine gerade Zahl!} \end{array} ~}\\ \end{array} \)

Damit ist die Behauptung für n = 1 und n = n+1, also für n \(\ge\) 1 bewiesen!

lieber heureka!

kannst du mir erklären, wie du beim beweis des induktionsschritt nach dem eingekastelten von zeile 2 auf zeile 3 kommst?

(3^{2hoch n} -1)² + 2 (3^{2 hoch n} _{-1) /...}

(3^{2hoch n} -1) (3^{2 hoch n} -1+2)

wo ist das quadrat hin verschwunden und muss ich nicht beide klammerteile mit der 2 multiplizieren?

Besten Dank!!!