Understanding Mathematical Induction for Integer Sequences
Dive into the concept of mathematical induction, a powerful technique for proving theorems based on infinite sequences of integers. Explore examples, base cases, inductive steps, and proofs to bolster your understanding.
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
Mathematical Induction ICS 6D Sandy Irani
Induction is a technique for proving facts/theorems that are parameterized by an infinite sequence of integers. For example . Theorem: For every integer n 1, ? ?(? + 1) 2 ? = ?=1
? ?(? + 1) 2 ? ? : ? = ?=1
Let P(n) be an assertion that depends on a natural number n. Theorem: For every integer n 1, P(n) is true. An inductive proof of the theorem consists of two parts: 1) Base case: proof that P(1) is true. 2) Inductive step: proof that for all k 1, P(k) implies P(k+1)
Inductive Proof Theorem: For every integer n 1, ? ?(? + 1) 2 ? = ?=1
Inductive Step ?+1 ? (? + 1)(? + 2) 2 ?(? + 1) 2 then ? = ? = For k 1, if ?=1 ?=1
Inductive Step ?+1 ? (? + 1)(? + 2) 2 ?(? + 1) 2 then ? = ? = For k 1, if ?=1 ?=1
A similar example Theorem: For every integer n 1, ? ?(? + 1)(2? + 1) ?2= 6 ?=1
Theorem: For every integer n 1, ? ?(? + 1)(2? + 1) ?2= 6 ?=1
Proof: By induction on n. + ) 1 + Base case: n = 1. 1 1 ( 1 1 )( 2 1 j = = = 2 12 1 j 6 1 So the theorem is true for n = 1. Inductive step: For k 1, suppose that We will show that j + ) 1 + + ) 1 + ) 1 + + + + + 1 k ( )(( 1 ( 2 )( 1 ( 1 )( 2 )( 2 ) 3 k k k k k k = = 2 j 6 6 1
+ 1 k k j = + ( + k 2 2 2 ) 1 j j 1 1 ( j + ) 1 + 1 )( 2 k k k by the inductive hypothesis = + 2) 1 + ( k 6 )( + ) 1 + ) 1 + 2 ( 1 2 ( 6 k k k k = + 6 6 + ) 1 + + ) 1 + 2 ( 1 )( 2 ( 6 k k k k = 6 + + + + ( 1 )[ 2 ( k ) 1 ( 6 1 )] k k k = 6 + + + ( 1 )( 2 )( 2 ) 3 k k k + + + 2 ( 1 )[ 2 7 ] 6 k k k = = 6 6 Therefore the equality holds for every n 1.
Proof of an inequality by induction Theorem: For any n 3, n2 7n + 12 0
Principle of Mathematical Induction Let P(n) be a statement parameterized by natural numbers. If the following two conditions are true: 1. P(c) is true for come constant c. 2. For k c, P(k) implies P(k+1) then P(n) is true for any n c.
Inequalities: true or false For every a, b, if a b, then a > b For every a, b, if a > b, then a b For every a, b, if a = b, then a b For every a, b, if a = b, then a > b For every x, if x 4, then x 1 For every x, if x 1, then x 4
Proving Inequalities A > B > C > D > E A = B = C = D = E A B C = D E A B > C = D E
Proof of an inequality by induction Theorem: For any n 3, n2 7n + 12 0
Another inequality by induction Theorem: For any n 4, n! > n2
Yet another theorem to prove by induction Theorem: For every integer n 1, 3 evenly divides 22n-1 3 evenly divides integer m m is an integer multiple of 3 m = 3j for some integer j
An inductive proof about a sequence defines by a recurrence relation. The sequence {gn} is defined as follows: g0= 1 gn=3gn-1 + 2n, for n 1
Change of Index in a Recurrence Relation gn=3gn-1 + 2n, for n 1
An inductive proof about a sequence defines by a recurrence relation. Theorem: Let {gn} be the sequence defined as follows: g0= 1 gn=3gn-1 + 2n, for n 1 Then for n 0, gn=(5/2)3n n (3/2)
