4. Ist diese Induktion gültig ?

Ist diese Induktion gültig ?

  • ?

    Hallo,

    ich habe irgendwie Zweifel, dass ich folgende Induktion richtig durchgeführt habe. Könnte da mal jemand einen Blick drauf werfen ?

    Aussage : Für a Element N  mit a>=1 ist ((2a-1)^n) -1 gerade für alle n>=0

Induktionsanfang :

((2a-1)^0) -1 = 1-1 = 0 ; gerade

Induktionsannahme :

((2a-1)^k) -1 ist gerade für alle k >= 0 

Induktionsschluss :

((2a-1)^k+1) -1 = ((2a-1)^k)*(2a-1)  -1

1. Der Term (2a-1)^k ist ungerade, da nach Induktionsannahme (2a-1^k) -1 gerade ist.

2. Der Term (2a-1) lässt sich ebenfalls in der Form (2a-1) ^k schreiben, mit k =1, somit ist er ebenfalls ungerade.

3. Da (2a-1)^k sowie (2a-1) ungerade sind, ist ihr Produkt ebenfalls ungerade. 

4. Nach dem Abziehen von 1 ist der Gesamtausdruck Gerade. q.e.d

    Denkt ihr das geht so in Ordnung ? Bei Satz 3. habe ich Bedenken. Kann man das so stehenlassen ohne zu beweisen ?

    0
  • D

    Naja, es ist schon etwas händewedeln dabei, aber mit einem Verweis auf die Primzahlzerlegung ist das ziemlich offensichtlich. Kommt immer darauf an, wen Du mit deinem Beweis erschrecken willst.

    BTW, deine Induktionsannahme ist etwas streng: die ist nämlich idR nicht, daß deine Aussage für alle k>=0 gilt, sondern daß es für ein spezielles k gilt (und dieses spezielle k hast Du ja im Induktionsanfang schon gefunden). Und wenn es für dieses k gilt, dann kann ich jetzt mit dieser Annahme etwas über k+1 sagen.

    0
  • S

    harg schrieb:

    ((2a-1)^k) -1 ist gerade für alle k >= 0

    Wenn Du's schon für alle annimmst, musst Du nichts mehr zeigen. Richtig wäre "für ein k"

    2. Der Term (2a-1) lässt sich ebenfalls in der Form (2a-1) ^k schreiben, mit k =1, somit ist er ebenfalls ungerade.

    Wenn das ein Rückgriff auf die Induktionsannahme sein soll, ist es falsch. s.o.
    Entweder Du formulierst das im Induktionsanfang mit (also für k=0 und k=1), oder Du sagst einfach hier, dass 2a-1 ungerade ist.

    3. Da (2a-1)^k sowie (2a-1) ungerade sind, ist ihr Produkt ebenfalls ungerade.

    Denkt ihr das geht so in Ordnung ? Bei Satz 3. habe ich Bedenken. Kann man das so stehenlassen ohne zu beweisen ?

    Also ich würd's durchgehen lassen. Hängt aber auch etwas davon ab, wie genau ihr "gerade" und "ungerade" definiert habt. Bei "intuitiver" Definition würde das so reichen. Wenn ihr gerade/ungerade Zahlen als die Mengen 2Z bzw. 2Z+1 definiert, dann könntest Du z.B. folgendes schreiben:

    (2a-1)^k ist ungerade, es gibt also ein m \in Z mit (2a-1)^k = 2m+1. Damit ist
    (2a-1)^k(2a-1) = (2m+1)(2a-1) = 4ma+2a-2m-1 = 2(2ma+a-m-1)+1, also ungerade.

    0
  • S

    Daniel E. schrieb:

    BTW, deine Induktionsannahme ist etwas streng: die ist nämlich idR nicht, daß deine Aussage für alle k>=0 gilt, sondern daß es für ein spezielles k gilt

    Soweit richtig.

    (und dieses spezielle k hast Du ja im Induktionsanfang schon gefunden).

    NEIN! Dann könnte mans ja einfach einsetzen... und hätte dann 'nen Beweis für k=1 da stehen. Aber genau das will man ja nicht.

    *edit*

    Daniel E. schrieb:

    Naja, es ist schon etwas händewedeln dabei, aber mit einem Verweis auf die Primzahlzerlegung ist das ziemlich offensichtlich. Kommt immer darauf an, wen Du mit deinem Beweis erschrecken willst.

    Ich tippe einfach mal auf Erstsemester-Übungsleiter - und der wird ihm die Primfaktorzerlegung um die Ohren hauen.

    0
  • D

    SG1 schrieb:

    Daniel E. schrieb:

    BTW, deine Induktionsannahme ist etwas streng: die ist nämlich idR nicht, daß deine Aussage für alle k>=0 gilt, sondern daß es für ein spezielles k gilt

    Soweit richtig.

    (und dieses spezielle k hast Du ja im Induktionsanfang schon gefunden).

    NEIN! Dann könnte mans ja einfach einsetzen... und hätte dann 'nen Beweis für k=1 da stehen. Aber genau das will man ja nicht.

    Naja, dann eben *ein solches k*.

    Mich verwirrt das gängige Format von Induktionsbeweisen immer, vermutlich, weil ich irgendwie immer von der falschen Richtung her denke.

    Sagen wir, ich will Aussage A(k) mit k>=k0 zeigen, dann zeigt man halt, daß A(k)=>A(k+1) gilt und man zeigt, daß A(k0) wahr ist. Vor welchen Teil man seine Gebetssätze ala "Nehmen wir an, es existiert ein k ..." davorschreibt und wie man jetzt welchen Teil der Aufgabe benennt, das werd ich mir wahrscheinlich nicht mehr merken können.

    0
  • B

    Zwei Fehler:

    Erstens:

    ((2a-1)^k) -1 ist gerade für alle k >= 0

    Das ist die Beh. Wenn du die voraussetzt dann stimmt die Beh trivialerweise.

    Du meinst:
    Es gibt ein k aus N: so dass für alle p aus N mit 0<=p<=k: ((2a-1)^p)-1 ist gerade

    Zweitens:

    2. Der Term (2a-1) lässt sich ebenfalls in der Form (2a-1) ^k schreiben, mit k =1, somit ist er ebenfalls ungerade.

    Das geht im Schritt von k=0 auf k=1 schief. Ich schreib einfach mal deinen Gedankengang für den Fall k=0 auf:

    Induktionsannahme :
    Für alle p aus N mit 0<=p<=0: ((2a-1)^p)-1 ist gerade <=> ((2a-1)^0)-1 ist gerade

    Induktionsschluss :

    ((2a-1)^0+1) -1 = ((2a-1)^0)*(2a-1) -1

    1. Der Term (2a-1)^0 ist ungerade, da nach Induktionsannahme ((2a-1)^0)-1 gerade ist. [Soweit ok]

    2. Der Term (2a-1) lässt sich ebenfalls in der Form (2a-1)^p schreiben, mit p =1, somit ist er ebenfalls ungerade. [Bumm, die Induktionsannahme gilt aber nicht für p = 1 da sie nur für p <= 0 gilt. Hier verwendest du was du zeigen wolltest, das kann nicht klappen.]

    Lösung: rechne den Fall k=1 einzeln nach und verwende den dann als Induktionsanfang

    Man kann das auch ohne Induktion und Primzahlzerlegung lösen:
    ((2a-1)^n) -1 gerade <=> (2a-1)^n ungerade <=> 2a-1 ungerade (da ein Produkt endlich vieler natürlicher Zahlen nur dann ungerade ist wenn alle Faktoren ungerade sind) <=> klar für alle n aus N ohne die 0, mit 0 ist es Definitionssache.

    0
Anmelden zum Antworten