Induction Examples PDF

Induction Examples Question 1. Prove using mathematical induction that for all n ≥ 1, n(3n − 1) 1 + 4 + 7 + · · · + (3n − 2) =....

Induction Examples Question 1. Prove using mathematical induction that for all n ≥ 1, n(3n − 1) 1 + 4 + 7 + · · · + (3n − 2) =. 2 Solution. For any integer n ≥ 1, let Pn be the statement that n(3n − 1) 1 + 4 + 7 + · · · + (3n − 2) =. 2 Base Case. The statement P1 says that 1(3 − 1) 1= , 2 which is true. Inductive Step. Fix k ≥ 1, and suppose that Pk holds, that is, k(3k − 1) 1 + 4 + 7 + · · · + (3k − 2) =. 2 It remains to show that Pk+1 holds, that is, (k + 1)(3(k + 1) − 1) 1 + 4 + 7 + · · · + (3(k + 1) − 2) =. 2 1 + 4 + 7 + · · · + (3(k + 1) − 2) = 1 + 4 + 7 + · · · + (3(k + 1) − 2) = 1 + 4 + 7 + · · · + (3k + 1) = 1 + 4 + 7 + · · · + (3k − 2) + (3k + 1) k(3k − 1) = + (3k + 1) 2 k(3k − 1) + 2(3k + 1) = 2 3k 2 − k + 6k + 2) = 2 3k 2 + 5k + 2) = 2 (k + 1)(3k + 2) = 2 (k + 1)(3(k + 1) − 1) =. 2 Therefore Pk+1 holds. Thus, by the principle of mathematical induction, for all n ≥ 1, Pn holds.  Induction Examples Question 2. Use the Principle of Mathematical Induction to verify that, for n any positive integer, 6n − 1 is divisible by 5. Solution. For any n ≥ 1, let Pn be the statement that 6n − 1 is divisible by 5. Base Case. The statement P1 says that 61 − 1 = 6 − 1 = 5 is divisible by 5, which is true. Inductive Step. Fix k ≥ 1, and suppose that Pk holds, that is, 6k − 1 is divisible by 5. It remains to show that Pk+1 holds, that is, that 6k+1 − 1 is divisible by 5. 6k+1 − 1 = 6(6k ) − 1 = 6(6k − 1) − 1 + 6 = 6(6k − 1) + 5. By Pk , the first term 6(6k − 1) is divisible by 5, the second term is clearly divisible by 5. Therefore the left hand side is also divisible by 5. Therefore Pk+1 holds. Thus by the principle of mathematical induction, for all n ≥ 1, Pn holds.  Induction Examples Question 3. Verify that for all n ≥ 1, the sum of the squares of the first 2n positive integers is given by the formula n(2n + 1)(4n + 1) 12 + 22 + 32 + · · · + (2n)2 = 3 Solution. For any integer n ≥ 1, let Pn be the statement that n(2n + 1)(4n + 1) 12 + 22 + 32 + · · · + (2n)2 =. 3 Base Case. The statement P1 says that (1)(2(1) + 1)(4(1) + 1) 3(5) 12 + 22 = = = 5, 3 3 which is true. Inductive Step. Fix k ≥ 1, and suppose that Pk holds, that is, k(2k + 1)(4k + 1) 12 + 22 + 32 + · · · + (2k)2 =. 3 It remains to show that Pk+1 holds, that is, (k + 1)(2(k + 1) + 1)(4(k + 1) + 1) 12 + 22 + 32 + · · · + (2(k + 1))2 =. 3 12 + 22 + 32 + · · · + (2(k + 1))2 = 12 + 22 + 32 + · · · + (2k + 2)2 = 12 + 22 + 32 + · · · + (2k)2 + (2k + 1)2 + (2k + 2)2 k(2k + 1)(4k + 1) = + (2k + 1)2 + (2k + 2)2 (by Pk ) 3 k(2k + 1)(4k + 1) 3(2k + 1)2 + 3(2k + 2)2 = + 3 3 k(2k + 1)(4k + 1) + 3(2k + 1)2 + 3(2k + 2)2 = 3 k(8k + 6k + 1) + 3(4k 2 + 4k + 1) + 3(4k 2 + 8k + 4) 2 = 3 (8k 3 + 6k 2 + k) + (12k 2 + 12k + 3) + (12k 2 + 24k + 12) = 3 8k 3 + 30k 2 + 37k + 15 = 3 On the other side of Pk+1 , (k + 1)(2(k + 1) + 1)(4(k + 1) + 1) (k + 1)(2k + 2 + 1)(4k + 4 + 1) = 3 3  Induction Examples (k + 1)(2k + 3)(4k + 5) = 3 2 (2k + 5k + 3)(4k + 5) = 3 8k 3 + 30k 2 + 37k + 15 =. 3 Therefore Pk+1 holds. Thus, by the principle of mathematical induction, for all n ≥ 1, Pn holds.  Induction Examples Question 4. Consider the sequence of real numbers defined by the relations √ x1 = 1 and xn+1 = 1 + 2xn for n ≥ 1. Use the Principle of Mathematical Induction to show that xn < 4 for all n ≥ 1. Solution. For any n ≥ 1, let Pn be the statement that xn < 4. Base Case. The statement P1 says that x1 = 1 < 4, which is true. Inductive Step. Fix k ≥ 1, and suppose that Pk holds, that is, xk < 4. It remains to show that Pk+1 holds, that is, that xk+1 < 4. √ xk+1 = 1 + 2xk √ < 1 + 2(4) √ = 9 =3 < 4. Therefore Pk+1 holds. Thus by the principle of mathematical induction, for all n ≥ 1, Pn holds.  Induction Examples Question 5. Show that n! > 3n for n ≥ 7. Solution. For any n ≥ 7, let Pn be the statement that n! > 3n. Base Case. The statement P7 says that 7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040 > 37 = 2187, which is true. Inductive Step. Fix k ≥ 7, and suppose that Pk holds, that is, k! > 3k. It remains to show that Pk+1 holds, that is, that (k + 1)! > 3k+1. (k + 1)! = (k + 1)k! > (k + 1)3k ≥ (7 + 1)3k = 8 × 3k > 3 × 3k = 3k+1. Therefore Pk+1 holds. Thus by the principle of mathematical induction, for all n ≥ 1, Pn holds.  Induction Examples Question 6. Let p0 = 1, p1 = cos θ (for θ some fixed constant) and pn+1 = 2p1 pn − pn−1 for n ≥ 1. Use an extended Principle of Mathematical Induction to prove that pn = cos(nθ) for n ≥ 0. Solution. For any n ≥ 0, let Pn be the statement that pn = cos(nθ). Base Cases. The statement P0 says that p0 = 1 = cos(0θ) = 1, which is true. The statement P1 says that p1 = cos θ = cos(1θ), which is true. Inductive Step. Fix k ≥ 0, and suppose that both Pk and Pk+1 hold, that is, pk = cos(kθ), and pk+1 = cos((k + 1)θ). It remains to show that Pk+2 holds, that is, that pk+2 = cos((k + 2)θ). We have the following identities: cos(a + b) = cos a cos b − sin a sin b cos(a − b) = cos a cos b + sin a sin b Therefore, using the first identity when a = θ and b = (k + 1)θ, we have cos(θ + (k + 1)θ) = cos θ cos(k + 1)θ − sin θ sin(k + 1)θ, and using the second identity when a = (k + 1)θ and b = θ, we have cos((k + 1)θ − θ) = cos(k + 1)θ cos θ + sin(k + 1)θ sin θ. Therefore, pk+2 = 2p1 pk+1 − pk = 2(cos θ)(cos((k + 1)θ)) − cos(kθ) = (cos θ)(cos((k + 1)θ)) + (cos θ)(cos((k + 1)θ)) − cos(kθ) = cos(θ + (k + 1)θ) + sin θ sin(k + 1)θ + (cos θ)(cos((k + 1)θ)) − cos(kθ) = cos((k + 2)θ) + sin θ sin(k + 1)θ + (cos θ)(cos((k + 1)θ)) − cos(kθ) = cos((k + 2)θ) + sin θ sin(k + 1)θ + cos((k + 1)θ − θ) − sin(k + 1)θ sin θ − cos(kθ) = cos((k + 2)θ) + cos(kθ) − cos(kθ) = cos((k + 2)θ). Therefore Pk+2 holds. Thus by the principle of mathematical induction, for all n ≥ 1, Pn holds.  Induction Examples Question 7. Consider the famous Fibonacci sequence {xn }∞ n=1 , defined by the relations x1 = 1, x2 = 1, and xn = xn−1 + xn−2 for n ≥ 3. (a) Compute x20. (b) Use an extended Principle of Mathematical Induction in order to show that for n ≥ 1, [( √ )n ( √ )n ] 1 1+ 5 1− 5 xn = √ −. 5 2 2 (c) Use the result of part (b) to compute x20. Solution. (a) 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765 (b) For any n ≥ 1, let Pn be the statement that [( √ )n ( √ )n ] 1 1+ 5 1− 5 xn = √ −. 5 2 2 Base Case. The statement P1 says that (  √ )1 ( √ )1 1 1+ 5 1− 5  x1 = √  − 5 2 2 [ √ √ ] 1 1+ 5 1− 5 = √ − 5 2 2 [ √ √ ] 1 1+ 5−1+ 5 = √ 5 2 [ √ ] 1 2 5 = √ 5 2 = 1, which is true. The statement P2 says that (  √ )2 ( √ )2 1 1+ 5 1− 5  x2 = √  − 5 2 2  Induction Examples [( √ ) ( √ )] 1 1+2 5+5 1−2 5+5 =√ − 5 4 4 [( √ √ )] 1 1+2 5+5−1+2 5−5 =√ 5 4 [ √ ] 1 4 5 =√ 5 4 = 1, which is again true. Inductive Step. Fix k ≥ 1, and suppose that Pk and Pk+1 both hold, that is, (  √ )k ( √ )k 1 1+ 5 1− 5  xk = √  − , 5 2 2 and (  √ )k+1 ( √ )k+1 1 1+ 5 1− 5 xk+1 =√  − . 5 2 2 It remains to show that Pk+2 holds, that is, that (  √ )k+2 ( √ )k+2 1 1+ 5 1− 5 xk+2 = √  − . 5 2 2 xk+2 = xk + xk+1 (  (  √ )k ( √ )k √ )k+1 ( √ )k+1 1 1+ 5 1− 5  1 1+ 5 1− 5 =√  − +√  −  5 2 2 5 2 2 (  √ )k ( √ )k+1 ( √ )k ( √ )k+1 1 1+ 5 1+ 5 1− 5 1− 5 =√  + − −  5 2 2 2 2 (  √ )k ( √ ) ( √ )k ( √ ) 1 1+ 5 1+ 5 1− 5 1− 5  =√  1+ − 1+ 5 2 2 2 2 (  √ )k ( √ ) ( √ )k ( √ ) 1  1+ 5 3+ 5 1− 5 3− 5  =√ − 5 2 2 2 2 (  √ )k ( √ ) ( √ )k ( √ ) 1 1+ 5 6+2 5 1− 5 6−2 5  =√  − 5 2 4 2 4  Induction Examples ( ) √ )k ( √ ) ( √ )k ( √ 1 1+ 5 1+2 5+5 1− 5 1−2 5+5  =√  − 5 2 4 2 4 (  √ )k ( √ )2 ( √ )k ( √ )2 1 1+ 5 1+ 5 1− 5 1− 5  =√  − 5 2 2 2 2 (  √ )k+2 ( √ )k+2 1 1+ 5 1− 5 =√  − . 5 2 2 Therefore Pk+2 holds. Thus by the principle of mathematical induction, for all n ≥ 1, Pn holds. (c) Plugging n = 20 in a calculator yields the answer quickly.