Practice Questions - Mathematical Induction PDF

Discrete Structures Practice Questions Show that if 𝑛𝑛 is a positive integer, then 𝑛𝑛(𝑛𝑛 + 1) 1 + 2 +··· +𝑛𝑛 =. 2 Conjec...

Discrete Structures Practice Questions Show that if 𝑛𝑛 is a positive integer, then 𝑛𝑛(𝑛𝑛 + 1) 1 + 2 +··· +𝑛𝑛 =. 2 Conjecture a formula for the sum of the first 𝑛𝑛 positive odd integers. Then prove your conjecture using mathematical induction. Conjecture a formula for the sum of the first 𝑛𝑛 positive even integers. Then prove your conjecture using mathematical induction. Let 𝑃𝑃(𝑛𝑛) be the statement that 12 + 22 +· · · +𝑛𝑛2 = 𝑛𝑛(𝑛𝑛 + 1)(2𝑛𝑛 + 1)/6 for the positive integer 𝑛𝑛. a) What is the statement P(1)? b) Show that P(1) is true, completing the basis step of the proof. c) What is the inductive hypothesis? d) What do you need to prove in the inductive step? e) Complete the inductive step, identifying where you use the inductive hypothesis. f ) Explain why these steps show that this formula is true whenever n is a positive integer. Use mathematical induction to show that 1 + 2 + 22 +··· +2𝑛𝑛 = 2(𝑛𝑛+1) − 1 for all nonnegative integers 𝑛𝑛. Use mathematical induction to prove this formula for the sum of a finite number of terms of a geometric progression with initial term 𝑎𝑎 and common ratio 𝑟𝑟: 𝑛𝑛 𝑗𝑗 2 𝑛𝑛 𝑎𝑎𝑟𝑟 𝑛𝑛+1 − 𝑎𝑎 𝑎𝑎𝑟𝑟 = 𝑎𝑎 + 𝑎𝑎𝑎𝑎 + 𝑎𝑎𝑟𝑟 +··· +𝑎𝑎𝑟𝑟 = when 𝑟𝑟 ≠ 1, 𝑟𝑟 − 1 𝑗𝑗=0 where 𝑛𝑛 is a nonnegative integer. Use mathematical induction to prove the inequality 𝑛𝑛 < 2𝑛𝑛 1 for all positive integers 𝑛𝑛. Page Topic: Mathematical Induction Discrete Structures Practice Questions Use mathematical induction to prove that 2𝑛𝑛 < 𝑛𝑛! for every integer 𝑛𝑛 with 𝑛𝑛 ≥ 4. (Note that this inequality is false for 𝑛𝑛 = 1,2, and 3.) Prove that 3 + 3 · 5 + 3 · 52 + · · · + 3 · 5𝑛𝑛 = 3(5𝑛𝑛+1 − 1)/4 whenever 𝑛𝑛 is a nonnegative integer. Use mathematical induction to prove that 𝑛𝑛3 − 𝑛𝑛 is divisible by 3 whenever 𝑛𝑛 is a positive integer. Prove that 𝑛𝑛2 − 1 is divisible by 8 whenever 𝑛𝑛 is an odd positive integer. Use mathematical induction to prove that 7(𝑛𝑛+2) + 8(2𝑛𝑛+1) is divisible by 57 for every nonnegative integer 𝑛𝑛. Use mathematical induction to show that if 𝑆𝑆 is a finite set with 𝑛𝑛 elements, where 𝑛𝑛 is a nonnegative integer, then 𝑆𝑆 has 2𝑛𝑛 subsets. An odd number of people stand in a yard at mutually distinct distances. At the same time each person throws a pie at their nearest neighbor, hitting this person. Use mathematical induction to show that there is at least one survivor, that is, at least one person who is not hit by a pie. (This problem was introduced by Carmony. Note that this result is false when there are an even number of people.) What is wrong with this “proof” that all horses are the same color? Let P(n) be the proposition that all the horses in a set of n horses are the same color. Basis Step: Clearly, P(1) is true. Inductive Step: Assume that P(k) is true, so that all the horses in any set of k horses are the same color. Consider any k + 1 horses; number these as horses 1, 2, 3,... , k, k + 1. Now the first k of these horses all must have the same color, and the last k of these must also have the same color. Because the set of the first k horses and the set of the last k horses overlap, all k + 1 must be the same color. This shows that P(k + 1) is true and finishes the proof by induction. 2 Page Topic: Mathematical Induction