vollständige Induktion mit Ungleichungen

Thomas Musche, 0171-2814263 Naturwissenschaftlich-Mathematischer Unterricht

Vollstndige InduktionFr Lehramtskandidaten Mathematik GHR / Sek 2 und Ingenieure Autor Thomas Musche, www.Lern-aktiv.de, 0171-2814263 Inhalt: Induktionsbeweise mit Summenformeln Induktion mit Ungleichungen Teilbarkeitsinduktionen

www.Lern-aktiv.de Nachhilfeskripte und Nachhilfelehrer fr Schler und Studenten Thomas Musche, 0171-2814263 Naturwissenschaftlich-Mathematischer Unterricht

Thomas Musche, 0171-2814263 Naturwissenschaftlich-Mathematischer Unterricht Vollstndige Induktion Die Vollstndige Induktion ist ein Beweisverfahren, welches sehr gerne Lerninhalt bei Lehramtskandidaten und Physikern/ Ingenieuren ist. Sie beginnt stets mit einem Induktionsanfang, wo die vorgegebene Aussage fr die erste Zahl (hufig n=1 oder n=0 ) gezeigt wird. Der Induktionsschritt hingegen ist mehr allgemein: Ausgehend von einem oder mehrerer beliebigen Vorgnger muss die Aussage fr einen Nachfolger gezeigt werden. Resultat ist schlielich dann, dass es fr alle Elemente dann gezeigt ist. Eine der beliebtesten Induktionsbeweise, stets zur Einfhrung der vollstndigen Induktion benutzt, ist:

Induktion mit SummenformelnBeispiel 1: Beweisen Sie die Gaussche Summenformel fr natrliche Zahlen:n k =1

k=

n (n + 1) gilt fr alle n |N 2

Beweis durch vollstndige Induktion: Induktionsanfang (IA): n=1Summe bis 1 n =1 Formel n =1 einsetzen

1(1 + 1) ist zu zeigen 2 k =1 1 = 2/2 1=1 ist sicher richtig Also gilt Behauptung fr n = 1. n n (n + 1) gilt fr n |N Induktionsschritt (IS) nn+1 Induktionsvoraussetzung (IV): k= 2 k =1 k =(Bem: Manche Autoren schreiben die IV vor den IS, manche dahinter. Ich lse es so, dass ich ihn neben den IS schreibe...so kann man sich das aussuchen, wie man es gerne htte! )n +1

zu zeigen (Induktionsbehauptung IB)k =1

k=

(n + 1) (n + 2) gilt ebenfalls ! 2

Beweis: Linke Seite:n +1 k =1

k=

n

kk =1 Induktionsvoraussetzung !!

+ (n + 1) =letzterSummand

n(n + 1) + (n + 1) 2IV !!

n(n + 1) + 2(n + 1) (n + 2)(n + 1) = = rechte Seite 2 2 Also gilt Behauptung auch fr n+1 (Abschluss Induktionsschritt) Daher gilt Behauptung fr alle n |N (Abschluss des Beweises) In zahlreichen Bchern findet man leider fehlerhafte Induktionen, welche z.B. keine Induktionsvorausetzung ausformulierten (so gut wie nie !!) oder sonstige Fehler enthalten. Das knnen sich Studenten leider nicht erlauben, denn sie bewerten ihre Arbeiten nicht selbst. =


Thomas Musche, 0171-2814263 Naturwissenschaftlich-Mathematischer Unterricht Insbesondere solche bungsgruppenleiter, welche selbst keine wirkliche Ahnung haben, neigen dazu, allzu sehr an der Musterlsung des Profs (falls vorhanden ...) zu kleben. Daher Vorsicht! Die hier vorgestellte Version ist aber schon in zahlreichen mndlichen Prfungen als sehr gut bewertet worden - also meiner Auffassung nach mngelfrei.n

Beispiel 2: Beweisen Siek =1 1

k3 =

n (n + 1) 4

n N

1(1 + 1) 1 4 1 = 1 ist sicher wahr ! 1 = 4 4 k =1 Also gilt Behauptung fr n=1 n n (n + 1) IS: nn+1 IV: gilt fr n |N k3 = 4 k =1 n +1 (n + 1)((n + 1) + 1) zu zeigen: k3 = n N 4 k =1 Beweis: n +1 n n (n + 1) 4(n + 1) + linke Seite k = k 3 + (n + 1) = 4 4 k =1 k =1 letzter Summand

IA: n=1 :

k =

IV !!

IV !! Binom!!

(n + 1)(n + 4(n + 1)) (n + 1) (n + 4n + 4) (n + 1)(n + 2) = = 4 4 4 Also gilt Behauptung auch fr n+1 Also gilt Behauptung fr alle n aus N =

rechte Seite

1 q n +1 fr alle n aus |N (geometrische Summenformel) Beispiel 3: q = 1 q k =0n k

IA: n = 0 :

1 q 0+1 1 q q0 = 1 = 1 ist sicher wahr 1 q 1 q k =0 Also gilt Behauptung fr n=0 n 1 q n +1 k fr n aus |N ist gltig IS: nn+1 IV: q = 1 q k =00

qk =

n +1

Zu zeigen:k =0

qk =

1 q ( n +1)+1 fr n+1 gilt ebenfalls. 1 qn +1

Beweis: linke Seite:k =0

qk =

n k =0

q k + q n +1IV


Thomas Musche, 0171-2814263 Naturwissenschaftlich-Mathematischer Unterricht 1 q n +1 (1 q)q n +1 1 q n +1 + q n+1 q q n +1 1 q n + 2 = = + = war Beh. 1 q 1 q 1 q 1 q Also gilt Beh fr n+1 Also gilt Beh fr alle n aus |N

n

Beispiel 4k =1

k2 =

n(n + 1)(2n + 1) zu zeigen fr alle n aus |N 6

IA: n=1

1(1 + 1)(2 1 + 1) ist zu zeigen 6 k =1 1= 6/6 11 ist sicher richtig also gilt Beh fr n=11

k2 =

n(n + 1)(2n + 1) gilt fr n 6 k =1 n +1 (n + 1)((n + 1) + 1)(2(n + 1) + 1) Beh gilt auch fr n+1 Zu zeigen: k2 = 6 k =1

IS: nn+1

n

IV:

k2 =

n +1

Beweis:k =1

k =

n k =1

k + (n + 1) =IV

n(n + 1)(2n + 1) 6(n + 1) n(n + 1)(2n + 1) + 6(n + 1) + = 6 6 6

(n + 1)(n(2n + 1) + 6(n + 1)) (n + 1)(2n + n + 6n + 6) (n + 1)(n + 2)(2n + 3) = = 6 6 6 (ausmultipliziert sieht man es besser....) Also gilt Behauptung fr n+1 Also gilt Behauptung fr alle n aus |N =n

Beispiel 5:K =1 1

2k 1 = n gilt fr alle n aus |N

IA: n=1k =1

2k 1 = 1 ist zu zeigen

2-1=1 1=1 ist sicher richtig, also gilt Behauptung fr n=1n

IS: nn+1 IV:K =1 n +1

2k 1 = n gilt fr n aus |N

Zu zeigen:K =1

2k 1 = (n + 1) : Behauptung gilt auch fr n+1


Thomas Musche, 0171-2814263 Naturwissenschaftlich-Mathematischer Unterrichtn +1

Beweis:K =1

(2k 1) =

n k =1

(2k 1) + (2(n + 1) 1) = n + 2n + 1 = (n + 1) war Beh.iv

Also gilt Beh. fr n+1 Also gilt Behauptung fr alle n aus |Nn

Beispiel 6:K =1

(2k 1) = n(4n 1)3

fr alle n aus |N

1

IA : n=1

3 Also gilt Beh. fr n=1k =1

(2k 1)2 = 1(4 1 1) (2 1 1) 2 = 1 3 1 = 1 ist sicher wahr.3n

3 Zu zeigen: Behauptung gilt fr n+1: (2k 1) = (n + 1)(4(n + 1) 1) 3 K =1 Beweis: (n + 1)(4(n + 1) 1) (n + 1)(4n + 8n + 4 1) n(4n 1 + 8n + 4) + 4n + 8n + 3 = = = 3 3 3K =1 n +1IV IV

IS: nn+1 IV: Behauptung gilt fr n :

(2k 1) = n(4n 1)

n(4n 1) 8n + 4n + 4n + 8n + 3 + = 3 3

12n + 12n + 3 (2k 1) + = 3 k =1n

n k =1

(2k 1) + 4n + 4n + 1

=

n k =1

(2k 1) + (2n + 1) =

n +1 k =1

(2k 1)

Also gilt Behauptung fr n+1 Also gilt Behauptung fr alle n aus |NBeispiel 7 IA: n=11 n gilt fr alle n aus |N = n +1 k =1 k ( k + 1) 1 1 1 1 ist offensichtlich richtig = = 1+1 1 (1 + 1) 2 k =1 k ( k + 1) Also gilt Behauptung fr n=1n 1 n

IS: nn+1 IV:

1 n ist gltig fr n aus |N = n +1 k =1 k ( k + 1) n +1 1 n +1 Zu zeigen: = (n + 1) + 1 k =1 k ( k + 1) Beweis:


Thomas Musche, 0171-2814263 Naturwissenschaftlich-Mathematischer Unterrichtn +1 n + 1 (n + 1)(n + 1) n + 2n + 1 n ( n + 2) 1 = = = = + n + 1 + 1 n + 2 (n + 2)(n + 1) (n + 1)(n + 2) (n + 1)(n + 2) (n + 1)(n + 2)IV IV

n 1 + = n + 1 (n + 1)(n + 2) Also gilt Beh. fr n+1 Also gilt Beh. fr alle n aus |N =

1 1 + = (n + 1)(n + 2) k =1 k ( k + 1)

n

n +1

1 k =1 k ( k + 1)

n

Beispiel 8:k =1

k (k + 1) =

n(n + 1)(n + 2) fr alle n aus |N 3

IA: n=1

1 2 3 1(1 + 1)(1 + 2) 1(1 + 1) = 2 = 2 ist richtig 3 3 k =1 Also gilt Behauptung fr n=11

k (k + 1) =

n

IS: nn+1

IV:k =1 n +1

k (k + 1) =

n(n + 1)(n + 2) gilt fr n aus |N 3

Zu zeigen:k =1

k (k + 1) =

(n + 1)((n + 1) + 1)((n + 1) + 2) Beh gilt fr n+1 3

Beweis:IV

(n + 1)((n + 1) + 1)((n + 1) + 2) (n + 1)(n + 2)(n + 3) (n + 1)(n + 2)n 3(n + 1)(n + 2) = = + 3 3 3 3IV

=

n k =1

k (k + 1) + (n + 1)(n + 2) =

n +1 k =1

k (k + 1)

Also gilt Beh. fr n+1 Also gilt Beh fr alle n aus |N



Induktion mit UngleichungenHier ist es sinnvoll, stets eine geeignete Abschtzung zu finden und dann die IV einzubringen. Der meiner Meinung nach schwierigste Teil ist die, richtig abzuschtzen.

Beispiel 9 Bernoulli-Ungleichung : 1+na (1+a)n soll gelten fr alle n aus |N

IA n=1

1+a (1+a) ist sicher richtig also gilt Beh. fr n=1

IS nn+1 IV es gelte 1+na (1+a)n fr n aus |N Zu zeigen: 1+(n+1)a (1+a)(n+1) Beweis: (1+a)n+1 = (1+a)n(1+a) (1+na)(1+a) = 1+na +a + na = 1+(n+1)a+na 1+(n+1)a Also gilt Beh fr n+1 Also gilt Behauptung fr alle n aus |N da na >0 gilt.

Beispiel 10

n 2n fr alle n aus |N mit n 5

IA: n=5 25 32 ist sicher richtig also gilt Beh fr n=5 IS n n+1 IV n 2n Zu zeigen (n+1) 2n+1 Beweis 2n+1 = 2n2 2n n+2n+1 da 2n+1 n (n+1) war die Beh. Also gilt Beh fr n+1 Also gilt Beh fr alle n aus |N www.Lern-aktiv.de Nachhilfeskripte und Nachhilfelehrer fr Schler und Studenten Thomas Musche, 0171-2814263 Naturwissenschaftlich-Mathematischer Unterricht


Beispiel 11 n!

n k

fr alle nk und n,k aus |N (n variabel)

1 =1 fr k gibt es die Mglichkeiten 0 und 1, in beiden Fllen resultiert 1 k Also gilt Behauptung fr n=1 n IS: nn+1 IV: n! gilt fr n aus |N. k n +1 Zu zeigen: Behauptung gilt auch fr n+1 : (n + 1)! k IA: n= 1 1! Beweis: (n+1)! = (n+1)n! (n + 1) n nach Induktionsvoraussetzung k

Wegen: n (n + 1)n! (n + 1)! (n + 1)! (n + 1)! = = (n + 1 k ) = (n + 1 k ) (n + 1) = k (n k )!k! (n k )!k! (n + 1 k )(n k )!k! (n + 1 k )!k! Gilt (n + 1) n n +1 n +1 = (n+1-k) k k k weil der Vorfaktor 1 ist. n n +1 daher gilt dann auch die k k

Somit kann man schlussfolgern: (n+1)! (n+1) Behauptung.



Teilbarkeitsinduktion Beweisen Sie durch vollstndige Induktion: Fr alle a,b,n N1: a-b T an-bn

Fr alle a, b, n N1: Induktionanfang: Induktionsvoraussetzung: Induktionschlu:nn+1 zu zeigen:

a-b T an-bn n=1 a-b T a1-b1 a-b T an-bn a-b T an+1-bn+1 a-b T an+1-bn+1 a-b T an-bn a-b T a-b a-b T (an-bn) a a-b T (a-b) bn (Multiplikationsregel der Teilerrelation) a-b T an+1-bna a-b T abn-bn+1 (Nach Additionregel der Teilerrelation) a-b T (an+1 - abn)+( abn- bn+1) a-b T an+1- bn+1 n n Also gilt fr alle a,b,n N1: a-b T a -b


Documents

vollständige Induktion mit Ungleichungen