Aufgabe 26

Man zeige durch vollständige Induktion:

(a) "für allen" "gibt es m" (n=2m ODER n=2m+1)

Beweis: Induktion über n

Basis: setze m=0
(zu zeigen: "es gibt m"(0=2m ODER 0=2m+1, da Basis 0!)

Schritt: n→ Sn

Induktionshypothese: "es gibt m" (n=2m ODER n=2m+1)

Prinzip der Induktion:

  A(0) → "für alle n"(A(n)→A(Sn)) → A(n)    
  Basis                  Schritt  

Zu zeigen:

"es gibt m`"(Sn=2m`ODER Sn=2m`+1)

1.Fall: n=2m, Setze m`:=m

             Dann Sn=2m+1
                                 m`

2. Fall: n=2m+1, Setze m`:=Sm

             Dann Sn=S(2m+1)
                                 2*Sm     (nach Def *)
                                       m`
 

(b) Man zeige durch vollständige Induktion die Irrationalität von √2, d.h. "für alle n" "für alle m"(n+1)² ≠ 2(m+1)²

Hinweis: Man verwende eine Wertverlaufsinduktion nach n!

                                      Wertverlaufsinduktion A(m)
                                                           ↓
                                        IH: A(m) gilt für die m<n
                  alle A(m)(m<n)   →    A(n)    Zu zeigen:A(n)
   |-------------------------------------------|------|-----------------→
                                                        n-1    n                      N


    (Gewöhnliche) Induktion:

   |------------------------------------------|-----------|------------------→
                                                     A(n)  →  A(Sn)

Wertverlaufsinduktion (n):

Zu zeigen: "für alle m" (n+1)² ≠ 2*(m+1)²     (=A(n))

(Anmerkung: Wir können verwenden, dass A(k) schon bewiesen worden ist für alle k<n (IH))

Verwende Fallunterscheidung (FU) gemäß (a):

1. Fall: n+1 gerade, etwa =2k
            (2k)²   =   2(m+1)²            (geteilt durch 2)
             2k²    =    (m+1)²

           Verwende für die Induktionshypothese für m  (<n)
           Damit folgt: F (siehe auch Beweis durch Negation!)

2. Fall: n+1 ungerade: Widerspruch!, da (n+1) ungerade, aber 2(m+1)² gerade!


Aufgabe 28: