Mit vollständiger Induktion zeigen: Jede Zahl grösser gleich 24 lässt sich schreiben als…

Question

Aufgabe:

1) Beweisen Sie die folgende Aussage mit vollständiger Induktion:

Jede Zahl n ∈ ℕ mit n ≥ 24 lässt sich in der Form n = 5*k + 7*l mit k, l ∈ ℕ∪{0} schreiben.

Problem/Ansatz:

Wie soll ich anfangen und beweisen?

Answer 1

Da muss man wohl etliche Fälle unterscheiden.

n= 24 ist ja klar   2*5 + 2*7

Sei nun für n eine Zerlegung vorhanden 5*k+7*l  mit k, l ∈ ℕ∪{0}

1. Fall:   k=0 ==>   l>3 und  n = 7*l . Es gibt also m∈ ℕ∪{0}  mit l=m+2

also ist n+1 = (m+2)*7 + 1 = 7m + 14 + 1 = 7m + 5*3 also n+1 auch

 passend zerlegbar.

2. Fall:  k=1 also n = 5 + 7*l   und wegen n≥24 also l>2, also

gibt es wieder  m∈ ℕ∪{0}  mit l=m+2  und es gilt

          n+1 =  6 + 7*(m+2) = 20+7*m = 4*5 + 7*m klappt also auch dann.

Dann muss man noch die Fälle mit kleinem l betrachten.

3. Fall l=0  ==>   n=5*k  .  Dann ist aber k>4, also

gibt es   m∈ ℕ∪{0}  mit k=m+4  und es gilt

                           n+1 = 5*(m+4) + 1 = 5*m + 21 = 5*m + 3*7 also:

                                    Zerlegung klappt.

4. Fall  l=1  also  n = 5*k + 7 .

                         Wegen n≥24 also k≥4  und so

gibt es   m∈ ℕ∪{0}  mit k=m+4  und es gilt

                         n+1 = 5*(m+4) + 8 = 5*m + 28 = 5*m + 4*7 also:

                                       Zerlegung klappt.

5. Fall: beide k und l sind mindestens 2.

                    und n = 5*k+7*l

Dann gibt es   x,y∈ ℕ∪{0}  mit k=x+1  und  l=y+2

also  n +1  = 1 +  5*(x+1) + 7*(y+2) = 5*x +7*y + 20

                                                        = 5*(x+4) + 7*y

 Also auch dann klappt die Zerlegung.   q.e.d.