0 Daumen
474 Aufrufe

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

2)    32^n - 1 ist durch 2n+2 teilbar

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

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}

                      ⇒ A0 = 20 = 1   ✓

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

                     ⇒ A1 = 21 = 2  ✓

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

                   ⇒ A2 = 22 = 4  ✓

  I.V:  An = 2n 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.#

     ⇒  An+1 = 2n+1 = 2n * 2  ✓

 

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

von
ja, kann man machen .)

2 Antworten

0 Daumen

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.

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

32^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.

0 Daumen

Induktionsanfang für n=1: (32 -1)/23 = 8/8 ok

Induktionsschritt für n + 1 

32(n+1) -1 = 32*3n+1 - 1 = (8-1)*3n+1 - 1 = 23*3n+1 - 3n+1- 1 = 23*3n+1 - (3n+1  + 1)

Da der Teiler 2n+3 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.

von 5,4 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...