(3^2^n) - 1 durch 2^{n+2} teilbar

Question

habe hier eine Aufgabe, beid der ich nicht klar komme:

2)    3^{2^n} - 1 ist durch 2ⁿ⁺² teilbar

3)   Die Anzahl A_n aller Teilmengen einer n-elementigen Menge ist gegeben durch A_n=2ⁿ

Beides muss mit Vollständiger Induktion bewiesen werden. Habe schon einen Ansatz zu 3), bin mir aber nicht sicher ob das so geht. Bei 2) hab ich gar keine Idee.

 

3)  I.A :   n=0 : Teilmenge einer 0-elementigen Menge : {0}

                      ⇒ A₀ = 2⁰ = 1   ✓

              n=1 : Teilmenge einer 1-elementigen Menge: {0},{1}

                     ⇒ A₁ = 2¹ = 2  ✓

             n=2: Teilmenge einer 2-elementigen Menge: {0},{1},{2},{1,2}

                   ⇒ A₂ = 2² = 4  ✓

  I.V:  A_n = 2ⁿ ist Anzahl aller Teilmengen einer n-elementigen Menge

 I.S:   n→ n+1 :  durch das zusätzliche Element der n+1 -elementigen Menge in Kombination mit jeder Teilmenge     einer n-elementigen Menge entsteht eine neue Teilmenge, was dazu führt, dass die Anzahl einer n+1 -elementigen Menge doppelt so hoch ist wie die einer n-elementigen Menge.#

     ⇒  A_n+1 = 2ⁿ⁺¹ = 2ⁿ * 2  ✓

 

Kann ich das so machen? Und kann mir bitte jemand bei der 2) helfen?

Comments

ja, kann man machen .)

Answer 1

3) Sieht doch soweit von der Idee sehr gut aus.

2)

Induktionsanfang n = 1

3^{2^1} - 1 ist durch 2^{1+2} teilbar
8 ist durch 8 teilbar

Induktionsschritt n --> (n + 1)

3^{(2^{n + 1})} - 1 ist durch 2^^{(n + 1) + 2} teilbar
3^{2·2^n} - 1 ist durch 2^{n + 3} teilbar
(3^{2^n})^2 - 1 ist durch 2·2^{n + 2} teilbar
(3^{2^n} + 1)(3^{2^n} - 1) ist durch 2·2^{n + 2} teilbar
(3^{2^n} + 1)(a·2^{n + 2}) ist durch 2·2^{n + 2} teilbar
(3^{2^n} + 1)(a) ist durch 2 teilbar

Da 3^{2^n} nur den Faktor 3 enthält ist 3^{2^n} ungerade. 3^{2^n} + 1 muss daher gerade sein.

(b·2)(a) ist durch 2 teilbar

Damit ist die Aussage meiner Meinung nach gezeigt.

Comments

Die klingt logisch. Ich verstehe aber nicht ganz, wie du im Induktionschritt von Zeile 4 auf 5 kommst. Wo kommt das a her?

---

3^{2^n} - 1 ist durch Induktionsannahme durch 2^{n + 2} teilbar. Daher ist ein Faktor 2^{n + 2} und der andere Faktor a weil ich den nicht kenne.

Answer 2

Induktionsanfang für n=1: (3² -1)/2³ = 8/8 ok

Induktionsschritt für n + 1 

3²⁽ⁿ⁺¹⁾ -1 = 3²*3ⁿ⁺¹ - 1 = (8-1)*3ⁿ⁺¹ - 1 = 2³*3ⁿ⁺¹ - 3ⁿ⁺¹- 1 = 2³*3ⁿ⁺¹ - (3ⁿ⁺¹  + 1)

Da der Teiler 2ⁿ⁺³ ein Vielfaches von 2 ist und sowohl der erste Term als auch der zweite Term (gerade Zahl)  ebenso ein Vielfaches von 2 ist, ist die oben genannte Aussage aus meiner Sicht bewiesen.