Vollständige Induktion PDF

Preview

Summary

Download Vollständige Induktion PDF

Description

1 Vollständige Induktion Die vollständige Induktion besteht insgesamt aus zwei Teilen, die bei jedem Induktionsbeweis durchgeführt werden müssen. Es darf kein Teil weggelassen werden. Das sind zum einen der Induktionsanfang und zum anderen der Induktionsschritt. Am besten macht man sich dies an einigen Beispielen klar. Beispiel 1: Zeige, dass für 0 ≤ a ≤ 1 und ∀n ∈ ℕ gilt (1 + a) n ≤ 1 + (2 n − 1) a . Induktionsanfang: Für n=1 ergibt sich (1 + a) 1 = 1 + a ≤ 1 + (2 1 − 1) a = 1 + a . Der Induktionsanfang ist damit erbracht. Induktionsschritt: Von n auf n+1 Wir müssen zeigen, dass (1 + a )n +1 ≤ 1 + (2n +1 − 1)a und zwar unter der Induktionsvoraussetzung (IV), dass (1+ a )n ≤ 1+ (2n − 1)a für ein n schon bewiesen ist. Wir beginnen: ( IV )

n +1

(1 + a)

" = (1 + a) (1 + a) ≤ (1 + a)(1 + (2n − 1) a) n

n

n

= 1 + (2 − 1) a + a + (2 − 1) a² = 1 + (2n − 1 + 1 + (2n − 1) a) • a n

n

= 1 + (2 + (2 − 1) a) • a ≤ 1 + (2n +1 − 1)a Damit ist auch der Induktionsschritt erbracht und die Behauptung bewiesen. Beispiel 2: 2k −3 1 n = − n . 3k 3 3 k =2 n

Zeige mit vollständiger Induktion, dass ∀n ∈ ℕ mit n ≥ 2 gilt

∑

2

Induktionsanfang: Für n=2 ergibt sich

2k − 3 2 • 2 − 3 1 1 2 3 2 1 = = = − = − = . k 3 3² 9 3 3² 9 9 9 k =2

∑

Der Induktionsanfang ist erbracht. Induktionsschritt: Von n auf n+1 n +1

2k − 3 1 n + 1 = − n +1 und zwar unter der Induktionsvoraussetzung (IV), dass 3k 3 3 k =2 n 2k − 3 1 n = − n für ein n schon bewiesen ist. ∑ 3k 3 3 k =2

Wir zeigen

∑

( IV ) 2 k − 3 n 2 k − 3 2( n + 1) − 3 " 1 n 2( n + 1) − 3 ∑ 3k = k∑=2 3k + 3n +1 = 3 − 3n + 3n +1 k =2 1 n 2n + 2 − 3 1 n 2n − 1 1 3n 2n − 1 = − n+ = − n + n+1 = − n+1 + n+ 1 3 3 3 n+1 3 3 3 3 3 3 1 3n − 2 n + 1 1 n + 1 = − = − n+ 1 n+ 3 3 1 3 3 n +1

Damit ist alles gezeigt. Beispiel 3: Zeige mit vollständiger Induktion, dass ∀x ∈ ℝ, x ≠ 1 und ∀n ∈ ℕ gilt: n

∑ kx

k

=

k =1

x ( nx n +1 − ( n + 1) x n + 1) ( x −1)²

Induktionsanfang: Für n=1 erhalten wir: 1 x x x • ( x − 1)² kx k = x = =x ( x1 +1 − (1 + 1) x1 + 1) = ( x² − 2 x + 1) = ∑ (x − 1)² (x − 1)² (x − 1)² k =1 Damit ist der Induktionsanfang erbracht. Induktionsschritt: Von auf n+1 n +1

x n n ((n + 1) x +2 − (n + 2) x +1 + 1) unter der − x ( 1)² k =1 n x n 1 n Induktionsvoraussetzung (IV), dass ∑ kx k = (nx + − (n + 1) x + 1) schon für ein n x − ( 1)² k=1 bewiesen ist.

Wir müssen zeigen, dass ∑ kx k =

Starten wir also: n +1

( IV )

n

" =

x (nx n+ 1− (n + 1) x n + 1)+ (n + 1) x n+ 1 x − ( 1)² k =1 k =1 x x x nx n +1 − = + (n + 1)x n +1 (n + 1) x n + ( x −1)² ( x −1)² ( x −1)² 1 (nx n+ 2 − (n + 1)x n+ 1 + x + + (n + 1)x n+ 1 (x ² − 2x + 1)) = ( x −1)² x ((n + 1) xn +2 − (n + 2) xn +1 + 1) = ( x −1)²

∑ kx = k

∑ kx + (n + 1) x k

Damit sind wir fertig.

n+ 1

Beispiel 4: Seien a1 , a2 ,... reelle Zahlen mit 0 ≤ a ≤ 1, ∀ n ∈ ℕ . Man zeige ∀n ∈ ℕ : n

n

k =1

k =1

∑ ak − ∏ a k ≤ n − 1 1

1

k =1

k =1

Induktionsanfang: Für n=1 erhalten wir ∑ a k − ∏ a k = a1 − a1 = 0 ≤ 1 − 1 = 0 . Damit ist der Induktionsanfang erbracht. Induktionsschritt: Von n auf n+1: n +1

n +1

k =1

k =1

Wir müssen zeigen, dass ∑ a k − ∏ a k ≤ n und zwar unter der Induktionsvoraussetzung (IV), n

dass

n

∑a −∏a k

k=1

n +1

n +1

k

≤ n − 1 schon für ein n bewiesen ist.

k=1

n

∑ a − ∏a = ∑ a k

k =1

k

k =1

k =1

k

n

n

n

k =1

k =1

k =1

+ a n +1 − ∏ a k • a n +1 = ∑ a k − ∏ a k • a n +1 + a n +1

( IV )

" ≤ n, denn 0 ≤ a ≤ 1, ∀ n ∈ ℕ

Damit ist auch der Induktionsanfang erbraucht und die Behauptung bewiesen. Beispiel 5: n

Behauptung: ∀n ∈ ℕ : ∑ k( k!) = ( n +1)! −1 k =0

0

Induktionsanfang: Für n=0 ergibt sich

∑ k ( k !) = 0 • 0! = 0 • 1 = 0 = (0 + 1)!− 1 = 1− 1= 0 . k =0

Für Ungläubige nochmal den Induktionsanfang für n=1: 1

∑ k ( k !) = 0 • 0!+ 1• 1! = 1 = (1+ 1)!− 1 = 2 − 1 = 1 k =0

Induktionsschritt: Von n auf n+1 n +1

Wir müssen zeigen, dass ∑ k (k !) = (n + 2)!− 1 gilt und zwar unter der k =0 n

Induktionsvoraussetzung (IV), dass ∀n ∈ ℕ : ∑ k ( k !) = ( n +1)!−1 für ein n schon bewiesen k =0

ist. ( IV )

" k k k k n n = + + + = ( !) ( !) ( 1)( 1)! ( n + 1)!− 1+ ( n + 1)(n + 1)! ∑ ∑ n +1

n

k =0

k =0

= ( n +1)!(1 + n +1) −1 = ( n + 2)( n +1)!−1 = ( n + 2)!− 1 Auch hier ist alles gezeigt.

Beispiel 6: Sei g : ℝ → ℝ beliebig oft differenzierbar und f : ℝ → ℝ, f ( x ) := e x • g ( x ) . n  n Wir wollen zeigen, dass für alle n ∈ ℕ gilt f ( n ) ( x ) = ex • [∑  • g ( k ) (x )] . k= 0  k  Induktionsanfang: Für n=1 ergibt sich zum einen:

f '(x ) = ex • g (x ) + ex • g '(x ) = e x (g (x ) + g '(x )) Und zum anderen: 1 1  1  1 f (1) ( x) = ex • [∑   • g (k ) ( x)] = ex •   • g (0) ( x) +   • g (1) ( x ) = ex ( g ( x ) + g '( x )) k =0  k  0  1 

Damit ist der Induktionsanfang erbracht. Induktionsschritt: Von n auf n+1: n +1 n + 1   (k ) Wir müssen f (n+ 1) ( x ) = e x • [∑  • g (x )] zeigen unter der Induktionsvoraussetzung k k =0   n n   (IV), dass f (n ) ( x ) = e x •[∑   • g (k ) (x )] schon für ein n bewiesen ist. k =0  k  Auf in die Binomialkoeffizienten-Schlacht: ( IV )

n " x  n k (x )]' = [e • [∑   • g ( ) (x )]]' k k =0   n n n  n  x k x k = e • ∑   • g ( ) ( x) + e • ∑   • g ( +1) ( x) k k k= 0   k= 0   n n n n x k k+ = e [ ∑   • g ( ) ( x ) + ∑   • g ( 1) (x )] k k k= 0   k= 0   n n  n  = e x (∑   • g (k ) (x ) +   • g ( k +1) ) k =0  k  k  n +1  n + 1 (k )  n  (k ) =e x ∑  • g (x ) +   • g (x ) k=0  k  k  n +1 n + 1   (k ) =e x ∑  • g (x ) k=0  k 

f

( n+1)

(x) = [ f

( n)

Ein alternativer Lösungsvorschlag würde die Leibniz-Regel benutzen.

Beispiel 7: Klassiker sollen bei dieser Zusammenstellung auch nicht fehlen. n

Wir zeigen nun ∑ k ³ = k=1

n²( n + 1)² . 4 1

Induktionsschritt: Für n=1 erhalten wir trivialerweise

∑ k ³ = 1³ = 1 = k =1

1²(1 +1)² 4 = =1. 4 4

Der Induktionsanfang ist erbracht. Induktionsschritt: Von n auf n+1 n +1 ( n +1)²( n + 2)² unter der Induktionsvoraussetzung (IV), dass Wir zeigen ∑ k ³ = 4 k =1 n n²( n + 1)² ∑= k ³ = 4 schon für ein n bewiesen ist. k 1 (IV )

" n ²(n + 1)² n ²(n + 1)² 4(n + 1)³ k k n = + + = + ( n +1)³ = + ³ ³ ( 1)³ ∑=1 ∑=1 4 4 4 k k n ²(n + 1)² + 4(n + 1)³ (n + 1)²(n ² + 4n + 4) (n + 1)²(n + 2)² = = = 4 4 4 n +1

n

Induktionsschritt ist erbracht und Behauptung bewiesen. Beispiel 8: n

Wir zeigen jetzt

∑ k² = k =1

n( n + 1)(2 n + 1) . 6 1

Induktionsanfang: Für n=1 erhalten wir die wahre Aussage ∑ k² = 1² = 1 = k =1

1(1 + 1)(2 + 1) =1 . 6

Induktionsschritt: Von n auf n+1 n +1 (n + 1)(n + 2)(2(n + 1) + 1) (n + 1)(n + 2)(2n + 3) Wir zeigen ∑ k ² = unter der = 6 6 k =1 n n (n + 1)(2n + 1) Induktionsvoraussetzung (IV), dass ∑ k ² = schon für ein n bewiesen ist. 6 k=1 ( IV )

" n( n + 1)(2n + 1) n( n + 1)(2n + 1) 6( n + 1)² k k n = + + = + ( n + 1)² = + ² ² ( 1)² ∑= ∑= 6 6 6 k 1 k 1 n (n + 1)(2n + 1)+ 6(n + 1)² (n + 1)[n (2n + 1)+ 6(n + 1)] (n + 1)(n + 2)(2n + 3) = = = $ 6 6 6 durch Ausmultiplizieren n +1

n

verifiziert man dies

Damit ist der Induktionsschritt erbracht und alles gezeigt.

Beispiel 9:  2n  n  n  Wir behaupten: ∀ n ∈ ℕ :   = ∑   ² .  n  k= 0  k 0 0  0   0 Induktionsanfang: Für n=0 erhalten wir   = 1 = ∑   ² =   ² = 1² = 1 . k =0  k  0  0 Induktionsanfang ist erbracht.

Induktionsschritt: Von n auf n+1:  2( n+ 1)  n +1  n+ 1  Wir zeigen  =∑  ² und zwar unter der Induktionsvoraussetzung (IV), dass  n + 1  k =0  k   2n  n  n  ∀n ∈ ℕ :   = ∑   ² für ein n schon bewiesen ist.  n  k= 0 k  n n +1 n + 1  n +1   n +1  n +1   ² ² ² = + =   ∑    ∑ ² ∑ k =0  k  k =0  k   n + 1 k =0  k  n +1

Damit haben wir alles gezeigt. Beispiel 10: n

Wir behaupten, dass ∀n ∈ ℕ, n ≥ 1 gilt

 2n 

∑ 2k  = 2 k =0





2n − 1

.

1  2   2  2 Induktionsanfang: Für n=1 erhalten wir ∑   =   +   = 1 + 1 = 2 = 22− 1 = 2 . k=0  2k   0  1  Der Induktionsanfang ist erbracht.

Induktionsschritt: Von n auf n+1: n +1 2  n +2 = 22( n+ 1)−1 = 22 n+ 1 unter der Induktionsvoraussetzung (IV), dass Wir müssen ∑   k= 0  2 k  n  2n  ∑=  2k  = 2 2n−1 für ein n schon bewiesen ist, zeigen. k 0  Es ergibt sich entsprechend: ( IV ) " n 2 n  2 n +1 2 n −1+ 2 2 n −1 = 2² • 2 = 4• ∑   2 =2 k =0  2 k  Daraus folgt die Behauptung, denn: n  2n 22 n +1 = ∑  k = 0  2k  n  2n  ⇒ 22 n = 2∑   k =0  2k  Wir sind fertig.

Beispiel 11: Auch jetzt nochmal ein Klassiker, und zwar die Bernoullische Ungleichung: Für x ≥ 1 gilt (1 + x )n ≥ 1 + nx . Induktionsanfang: Für n=1 erhalten wir (1 + x ) 1 = 1 + x ≥ 1 + x . Induktionsschritt: Von n auf n+1 Wir zeigen (1+ x )n+ 1 ≥ 1+ (n + 1)x unter der Induktionsvoraussetzung (IV), dass (1 + x )n ≥ 1 + nx für ein n bewiesen ist. ( IV )

" = (1 + x )(1 + x ) ≥ (1 + x )(1 + nx ) = 1 + nx + x + nx ² nx" ²> 0 = 1 + (n + 1)x + nx ² ≥ 1 + (n + 1)x n +1

n

(1 + x )

Damit ist auch der Induktionsschritt erbracht und die Behauptung bewiesen. Beispiel 12: n

n

k =1

k =1

Jetzt zeigen wir noch die verallgemeinerte Bernoullische Ungleichung ∏ 1 + xk ≥ 1 + ∑ xk . 1

1

k =1

k =1

Induktionsanfang: Für n=1 erhalten wir ∏1 + xk = 1 + x1 ≥ 1 + ∑ xk = 1 + x1 . Induktionsschritt: Von n auf n+1: n +1

n +1

Wir zeigen ∏ 1+ x k ≥ 1+ k =1

n

n

k =1

k =1

∑x

k

unter der Induktionsvoraussetzung (IV), dass

k =1

∏1 + xk ≥ 1 + ∑ xk schon für ein n bewiesen ist. ( IV )

n n n " 1 ( 1 )(1 ) (1 )(1 ) 1 x x x x x x x x + = + + ≥ + + = + + + ∑ k ∑ k n+ 1 n+ 1 ∑ xk ∏ k ∏ k n+1 n+1 n +1

n

k =1

k =1

n+1

k=1

n

n+ 1

= 1 + ∑ xk + xn +1 ∑ xk ≥ 1 + ∑ xk k=1 k= 1 k= 1 % &'& ( >0

Mehr haben wir nicht mehr zu tun.

k=1

k=1

Beispiel 13: Für alle n ∈ ℕ, n ≥ 4 gilt n !> 2n . Induktionsanfang: für n=4 ergibt sich durch einfaches Nachrechnen 4! = 24 > 2 4 = 16 . Der Induktionsanfang stimmt also schon mal. Induktionsschritt: Von n auf n+1 Wir zeigen (n + 1)!> 2n +1 unter der Induktionsvoraussetzung (IV), dass n! > 2 n für ein n schon bewiesen ist. ( IV )

(*) " " n ( n + 1)! = ( n + 1) n! > ( n + 1)2 > 2n +1 = 2 • 2n

Wir erklären noch den Schritt (*): (n + 1)2 n > 2 n+1 = 2 • 2 n n +1 > 2

n > 1 (wahr nach Voraussetzung n ≥ 4) Damit ist der Induktionsschritt erbracht und die Behauptung bewiesen. Beispiel 14: n

Wir zeigen

k   n +1 

∑ m  =  m +1  .

    Induktionsanfang: Wir setzen n=1. Aus der Bedingung folgt sofort, dass m=1. Damit ergibt sich: 1  k  1  1 +1   2  ∑= 1  = 1  = 1 = 1 +1  =  2  = 1 k 1        Induktionsschritt: Von n auf n+1 n +1 k   n + 2  Wir müssen zeigen ∑   =   und zwar unter der Induktionsvoraussetzung (IV), dass k =m  m   m +1  n  k   n + 1 ∑   =  m + 1 für ein n schon bewiesen ist. k= m  m    k =m

(IV )  k  n  k   n +1  "  n +1   n +1  (n + 1)! (n + 1)! +   = ∑  + =  + = ∑ k= m  m  k= m  m   m   m + 1  m  ( n − m)!( m +1)! ( n +1 − m)! m! ( n +1)! ( n +1)! ( n +1 − m)( n +1)! ( m +1)( n +1)! = + = + (n − m)!(m +1)! ( n + 1 − m)!m ! ( n + 1 − m)!( m + 1)! ( n + 1 − m)!(m + 1)! (n +1 − m)(n +1)! + (m +1)(n +1)! (n +1)!(n +1 − m + m +1) = = (n +1 − m )!(m + 1)! (n + 1 − m )!(m + 1)! n +1

(n + 2)(n + 1)! (n + 2)! n + 2  = = (n +1 − m)!(m + 1)! (n + 1 − m)!(m + 1)!  m +1  Damit ist auch der Induktionsschritt erbracht und die Behauptung bewiesen. =...