0 Daumen
4,5k Aufrufe

Wir sollen beweisen dass 22n-1 teilbar durch 3 ist, mit Hilfe der vollständigen Induktion.

Induktionsanfang hab ich n=1 gewählt da erhält man 3, was natürlich teilbar ist.

Für den Induktionsanfang n=n+1 leider weiß ich da jetzt nicht weiter wie genau ich das beweisen soll.

Avatar von

2 Antworten

+2 Daumen
 
Beste Antwort
Induktionsschritt n -> n + 1

2^{2[n + 1]} - 1

2^{2n + 2} - 1

4 * 2^{2n} - 1

4 * 2^{2n} - 4 + 3

4 * (2^{2n} - 1) + 3
2^{2n} - 1 ist durch 3 Teilbar.

Ein Produkt ist durch 3 Teilbar, wenn einer der Faktoren durch 3 teilbar ist.

Eine Summe ist durch 3 Teilbar, wenn beide Summanden durch 3 teilbar sind.

Damit ist auch 4 * (2^{2n} - 1) + 3 durch 3 teilbar.
Avatar von 477 k 🚀
+1 Daumen

Voraussetzung:

Gelte für ein festes m ≥ n : 3 teilt 2 2 m - 1

Dann gilt für m + 1: 3 teilt 2 2 ( m + 1 ) - 1

Beweis:

2 2 ( m + 1 ) - 1

= 2 2 m + 2 - 1

= 2 2 m * 2 2 - 1

= ( 2 2 m - 1 + 1 ) * 4 - 1

= ( 2 2 m - 1 ) * 4 + 1 * 4  - 1

= 4 * ( 2 2 m - 1 ) + 3

3 teilt gemäß Voraussetzung ( 2 2 m - 1 ),

dann teilt 3 aber auch  4 * ( 2 2 m - 1 )

und auch  

4 * ( 2 2 m - 1 ) + 3 = 2 2 ( m + 1 ) - 1

q.e.d.

Avatar von 32 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community