Proof by induction exercises

proof by induction divisibility and proof by induction examples with solutions
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Your Website URL(Optional)
Comment
ECE 250 Algorithms and Data Structures Proof by Induction Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 2006-2013 by Douglas Wilhelm Harder. Some rights reserved.Proof by Induction 2 Outline This topic gives an overview of the mathematical technique of a proof by induction – We will describe the inductive principle – Look at ten different examples – Four examples where the technique is incorrectly applied – Well-ordering of the natural numbers – Strong induction – Geometric problemsProof by Induction 3 1.4 Definition Suppose we have a formula F(n) which we wish to show is true for all values n ≥ n 0 – Usually n = 0 or n = 1 0 0 For example, we may wish to show that n nn1  F n k   2 k0 for all n ≥ 0Proof by Induction 4 1.4 Definition We then proceed by: – Demonstrating that F(n ) is true 0 – Assuming that the formula F(n) is true for an arbitrary n – If we are able to demonstrate that this assumption allows us to also show that the formula is true for F(n + 1), the inductive principle allows us to conclude that the formula is true for all n ≥ n 0Proof by Induction 5 1.4 Definition Thus, if F(n ) is true, F(n + 1) is true 0 0 and, if F(n + 1) is true, F(n + 2) is true 0 0 and, if F(n + 2) is true, F(n + 3) is true 0 0 and so on, and so on, for all n ≥ n 0Proof by Induction 6 1.4.1 Formulation Often F(n) is an equation: – For example, F(n) may be an equation such as: n nn1  kn  for 0  2 k0 n 2 2k1 n for n1  k1 n kn1 2 21 for n 0  k0 It may also be a statement: 3 – The integer n – n is divisible by 3 for all n ≥ 1Proof by Induction 7 1.4.2 Examples We will now look at ten examples At each case, we will show the inductive process... Proof by Induction 8 1.4.2.1 Example 1 n nn1  k Prove that is true for n ≥ 0  2 k0 0 0 01  k 0 – When n = 0:  2 k0 n nn1  – Assume that the statement is true for a given n: k  2 k0 – We now show: nn1 k n1 k   kk  00Proof by Induction 9 1.4.2.1 Example 1 n nn1  k Prove that is true for n ≥ 0  2 k0 0 0 01  k 0 – When n = 0:  2 k0 n nn1  – Assume that the statement is true for a given n: k  2 k0 – We now show: nn1 k n1 k   kk  00 nn1   n1  2 2 n1 n n1   2 n 2 n1 n1 n 2   22Proof by Induction 10 1.4.2.2 Example 2 2 Prove that the sum of the first n odd integers is n : n 2 2k1 n for n1  k1 1 2 2k111 – When n = 1:  k1 n 2 21kn  – Assume that the statement is true for a given n:  k1 – We now show: nn1 2k1 2 n11 2k1   kk  10Proof by Induction 11 1.4.2.2 Example 2 2 Prove that the sum of the first n odd integers is n : n 2 2k1 n for n1  k1 1 2 2k111 – When n = 1:  k1 n 2 21kn  – Assume that the statement is true for a given n:  k1 – We now show: nn1 2k1 2 n11 2k1   kk  11 2  2nn11  2  2nn 21 2 nn21 2  n 1 Proof by Induction 12 1.4.2.3 Example 3 n kn1 2 2 1 Prove that for n ≥ 0  k0 0 k 0 01 2 21 21  – When n = 0: k0 n kn1 – Assume that the statement is true for a given n: 2 2 1  k0 – We now show: nn1 k n1 k 2 2 2  kk  00Proof by Induction 13 1.4.2.3 Example 3 n kn1 2 2 1 Prove that for n ≥ 0  k0 0 k 0 01 2 21 21  – When n = 0: k0 n kn1 – Assume that the statement is true for a given n: 2 2 1  k0 – We now show: nn1 k n1 k 2 2 2  kk  00 nn  11  2 21 n1  221 n2  21Proof by Induction 14 1.4.2.4 Example 4 n n  n  2 Prove that   k k0  0 n 0  0 12 – When n = 0:  k 0 k0  n n  n  2 – Assume that the statement is true for a given n:  k k0  – We now show: nn1 n1 n1 n1 n1    k01 k n kk  01  Proof by Induction 15 1.4.2.4 Example 4 n n  n  2 Prove that   k k0  0 n 0  0 12 – When n = 0:  k 0 k0  n n  n  2 – Assume that the statement is true for a given n:  k k0  – We now show: nn1 n1 n1 n1 n1    k01 k n kk  01   n  nn  11  kk1 k1   n n n n1 n n n n n n  11  k k10 k k n k1 k1 k1 k0  Proof by Induction 16 1.4.2.4 Example 4 n n  n  2 Prove that   k k0  0 n 0  0 12 – When n = 0:  k 0 k0  n n  n  2 – Assume that the statement is true for a given n:  k k0  – We now show: nn1 n1 n1 n1 n1    k01 k n kk  01   n  nn  11   kk1 k1   n n n n1 n n n n n n  11   k k10 k k n k1 k1 k1 k0   n n   2  k k0 Proof by Induction 17 1.4.2.4 Example 4 n n  n  2 Prove that   k k0  0 n 0  0 12 – When n = 0:  k 0 k0  n n  n  2 – Assume that the statement is true for a given n:  k k0  – We now show: nn1 n1 n1 n1 n1    k01 k n kk  01   n  nn  11   kk1 k1   n n n n1 n n n n n n  11   k k10 k k n k1 k1 k1 k0   n n  nn1  2 2 2 2  k k0 Proof by Induction 18 1.4.2.5 Example 5 n1 n 1 r k r Prove that  1 r k0 1 0 1 r k r  1 – When n = 0: 1 r k0 n1 n 1 r k r – Assume that the statement is true for a given n:  1 r k0 – We now show: nn1 k n1 k r r r  kk  00Proof by Induction 19 1.4.2.5 Example 5 n1 n 1 r k r Prove that  1 r k0 1 0 1 r k r  1 – When n = 0: 1 r k0 n1 n 1 r k r – Assume that the statement is true for a given n:  1 r k0 – We now show: nn1 k n1 k r r r  kk  00 n1 1 r n1  r 1 r n1 n1 1rr  1 r  11 rr nn  11 11 r r r   1 r n1 n1 n1 n2 r rr11 r r  11 rrProof by Induction 20 1.4.2.6 Example 6 3 Prove by induction that n – n is divisible by 3 for all integers – This is slightly different • Choose a base case, say n = 0 • Next, prove that the truth of the formula for n implies the truth for n + 1 • Also, prove that the truth of the formula for n also implies the truth for n – 1 3 – When n = 0: 0 – 0 = 0 is divisible by 3 3 – Assume that the statement is true for a given n: n – 3 is divisible by 3 – We now show: 3 3 33 33 n1 n1 n 3n 3n1 n1 n1 n1 n 3n 3n1 n1  23 23  3 n n n n 3 n n n n  In both cases, the first term is divisible by 3, the second term is divisible by 3 by assumption; Consequently, their sum must also be divisible by 3