Strong Mathematical Induction Principles and Examples
Explore the concept of strong mathematical induction, with detailed explanations and examples including proofs related to prime divisibility and properties of sequences. Understand the basis step, inductive step, and how to apply the principle to various mathematical scenarios.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Principle of Strong Mathematical Induction Let P(n) be a statement defined for integers n; a and b be fixed integers with a b. Suppose the following statements are true: 1. P(a), P(a+1), , P(b) are all true (basis step) 2. For any integer k>b, if P(i) is true for all integers i with a i<k, then P(k) is true. (inductive step) Then P(n) is true for all integers n a.
Example: Divisibility by a Prime Theorem: For any integer n 2, Proof (by strong mathematical induction): 1) Basis step: The statement is true for n=2 because 2 | 2 and 2 is a prime number. 2) Inductive step: Assume the statement is true for all i with 2 i<k P(i) (inductive hypothesis) ; show that it is true for k . n is divisible by a prime. P(n) P(2) P(k) 2
Example: Divisibility by a Prime Proof (cont.): We have that for all i Z with 2 i<k, P(i) i is divisible by a prime number. We must show: P(k) k is also divisible by a prime. Consider 2 cases: a) k is prime. Then k is divisible by itself. b) k is composite. Then k=a b where 2 a<k and 2 b<k. Based on (1), p|a for some prime p. p|a and a|k imply that p|k (by transitivity). Thus, P(n) is true by strong induction. (1) (2)
Proving a Property of a Sequence Proposition: Suppose a0, a1, a2, is defined as follows: a0=1, a1=2, a2=3, ak = ak-1+ak-2+ak-3 for all integers k 3. Then an 2nfor all integers n 0. Proof (by strong induction): 1) Basis step: The statement is true for n=0: a0=1 1=20 for n=1: a1=2 2=21 for n=2: a2=3 4=22 P(n) P(0) P(1) P(2)
Proving a Property of a Sequence Proof (cont.): 2) Inductive step: For any k>2, Assume P(i) is true for all i with 0 i<k: ai 2i for all0 i<k . Show that P(k) is true: ak 2k ak= ak-1+ak-2+ak-3 2k-1+2k-2+2k-3 20+21+ +2k-3+2k-2+2k-1 = 2k-1 2k Thus, P(n) is true by strong induction. (1) (2) (based on (1)) (as a sum of geometric sequence)
