Induction In Discrete Structure By (Ishrat Hayat Malik)
Define: Induction is a mathematical method which is used to show a statement, a system or a theorem is real for each natural number.
The method entails two steps to prove a statement, as mentioned beneath −
The method entails two steps to prove a statement, as mentioned beneath −
Example
3n−13n−1 is a multiple of 2 for n = 1, 2, ...
Solution
Step 1 − For n=1,31−1=3−1=2n=1,31−1=3−1=2 which is a multiple of 2
Step 2 − Let us assume 3n−13n−1 is true for n=kn=k, Hence, 3k−13k−1 is true (It is an assumption)
We have to prove that 3k+1−13k+1−1 is also a multiple of 2
3k+1−1=3×3k−1=(2×3k)+(3k−1)3k+1−1=3×3k−1=(2×3k)+(3k−1)
The first part (2×3k)(2×3k) is certain to be a multiple of 2 and the second part (3k−1)(3k−1) is also true as our previous assumption.
Hence, 3k+1–13k+1–1 is a multiple of 2.
So, it is proved that 3n–13n–1 is a multiple of 2.
Problem 2
1+3+5+...+(2n−1)=n21+3+5+...+(2n−1)=n2 for n=1,2,…n=1,2,…
Solution
Step 1 − For n=1,1=12n=1,1=12, Hence, step 1 is satisfied.
Step 2 − Let us assume the statement is true for n=kn=k.
Hence, 1+3+5+⋯+(2k−1)=k21+3+5+⋯+(2k−1)=k2 is true (It is an assumption)
We have to prove that 1+3+5+...+(2(k+1)−1)=(k+1)21+3+5+...+(2(k+1)−1)=(k+1)2 also holds
1+3+5+⋯+(2(k+1)−1)1+3+5+⋯+(2(k+1)−1)
=1+3+5+⋯+(2k+2−1)=1+3+5+⋯+(2k+2−1)
=1+3+5+⋯+(2k+1)=1+3+5+⋯+(2k+1)
=1+3+5+⋯+(2k−1)+(2k+1)=1+3+5+⋯+(2k−1)+(2k+1)
=k2+(2k+1)=k2+(2k+1)
=(k+1)2=(k+1)2
So, 1+3+5+⋯+(2(k+1)−1)=(k+1)21+3+5+⋯+(2(k+1)−1)=(k+1)2 hold which satisfies the step 2.
Hence, 1+3+5+⋯+(2n−1)=n21+3+5+⋯+(2n−1)=n2 is proved.
Problem 3
Prove that (ab)n=anbn(ab)n=anbn is true for every natural number nn
Solution
Step 1 − For n=1,(ab)1=a1b1=abn=1,(ab)1=a1b1=ab, Hence, step 1 is satisfied.
Step 2 − Let us assume the statement is true for n=kn=k, Hence, (ab)k=akbk(ab)k=akbk is true (It is an assumption).
We have to prove that (ab)k+1=ak+1bk+1(ab)k+1=ak+1bk+1 also hold
Given, (ab)k=akbk(ab)k=akbk
Or, (ab)k(ab)=(akbk)(ab)(ab)k(ab)=(akbk)(ab) [Multiplying both side by 'ab']
Or, (ab)k+1=(aak)(bbk)(ab)k+1=(aak)(bbk)
Or, (ab)k+1=(ak+1bk+1)(ab)k+1=(ak+1bk+1)
Hence, step 2 is proved.
So, (ab)n=anbn(ab)n=anbn is true for every natural number n
Video Tutorial In Urdu
Video Tutorial In Urdu
0 comments:
Post a Comment
If You Have Any Problem While Downloading Comment Below