PROOF BY MATHEMATICAL INDUCTION
Mathematical induction is a common method of proof with large applications in mathematics and computer science. Proof by induction are not used to generate results but are used to determine the validity of a mathematical statement. Proof by mathematical induction can be broken up into three parts
There are two types of mathematical Induction.
1. Weak Induction: Assume S(k) is true and used to prove that it follow that S(k+1) is also true
2. Strong Induction: Assume: S(1),S(2),....,S(k) are all true and used to show that S(k+1) is true.
- Base Case
- Inductive Hypothesis
- Inductive Step
There are two types of mathematical Induction.
1. Weak Induction: Assume S(k) is true and used to prove that it follow that S(k+1) is also true
2. Strong Induction: Assume: S(1),S(2),....,S(k) are all true and used to show that S(k+1) is true.
|
EXAMPLE
Prove by Mathematical Induction that for any positive integer n, 1 + 2 + ... + n = n(n+1)/2. Proof. Let's let S(n) be the statement "1 + 2 + ... + n = (n (n+1)/2." Base Case. We must verify that S(1) is True. S(1) asserts "1 = 1(2)/2", which is clearly true. This completes the base case Inductive Hypothesis. Here we must prove the following assertion: "If there is a k such that S(k) is true, then (for this same k) S(k+1) is true." Thus, we assume there is a k such that 1 + 2 + ... + k = k (k+1)/2. (this can also be referred to as the inductive assumption.) We must prove, for this same k, the formula 1 + 2 + ... + k + (k+1) = (k+1)(k+2)/2. Inductive Step : 1 + 2 + ... + k + (k+1) = k(k+1)/2 + (k+1) = (k(k+1) + 2 (k+1))/2 = (k+1)(k+2)/2. The first equality is a consequence of the inductive assumption. |
MATHEMATICAL INDUCTION PLAYLIST |
DETAILED VIDEO TUTORIALS ON MOST COMMON INDUCTION PROBLEMS
#1 Principle of Mathematical Induction Prove 1+2+3+...+n=n(n+1)/2 maths hsc using proof by induction
#2 Mathematical Induction 2+2^2+2^3+...2^n=2(2^n-1) proof 5^n-2^n divisible by 3 discrete math
#3 Principle of mathematical induction prove proof 1+5+9+...+(4n-3)=n(2n-1)
# 4 Mathematical Induction prove 1/(1x2)+1/(2X3)+...+1/n(n+1)=n/(n+1)
#5 Principle of mathematical Induction n3+2n is divisible by 3 divides discrete n^3+2n pt VIII
#6 Proof prove by induction n^2 less 2n n squared less 2 to the n discrete
#7 Proof by induction 1+3+5+7+...+2n-1=n^2 discrete prove all n in N indu
#8 Proof by induction Σ k^2= n(n+1)(2n+1)/6 discrete principle
#9 Principle of mathematical Induction 8+2*8+3*8+...8n=8n(n+1)/2 precalculus discrete part VII
#10 Proof by induction prove 1+5+9+13+ +(4n-3)=n(4n-2)/2
#11 Proof by induction Σ k =n(n+1)/2 maths for all positive Year 12 hsc Extension 1
#12 Proof by induction 1^3+2^3+3^3+...+n^3= (n(n+1)/2)^2 n^2(n+1)^2/4 prove
#13 Proof prove 10^1+10^2+10^3+ +10^n = 10/9(10^n-1)discrete hsc maths year 12 by
#14 proof prove nth derivative of x^-1 is ( (-1)^n n !)/ x^(n+1) by induction
#15 proof prove induction 2^n is greater than or equal to 1+n inequality
#16 proof prove induction 3^n less than n+1! inequality hsc maths
#17 proof prove induction 8^n-1 is divisible by 7 divides