Mathematics Dictionary
Dr. K. G. Shih
Mathematical Induction
Subject
Symbol Defintion
Example : Abs(x) = square of x
AL 14 00 |
- Outlines
AL 14 01 |
- Definiton
AL 14 02 |
- Sum[n*(n+1)/2] = n*(n+1)*(n+2)/6
AL 14 03 |
- Sum[n^2] = n*(n+1)*(2*n+1)/6
AL 14 04 |
- Sum[n^3] = ((n*(n+1))/2)^2
AL 14 05 |
- 1/(1*2) + 1/(2*3) + ..... + 1/(n*(n+1)) = 1 - 1/(n+1)
AL 14 06 |
- Sum[1/((2*n-1)*(2*n+1)) = (1 - 1/(2*n+1))/2
AL 14 07 |
- Sum[1/(n*(n+1)*(n+2)] = n*(n+3)/(4*(n+1)*(n+2)
AL 14 08 |
- Sum[(2*n-1)^2] = n*(4*n^2 - 1)/3
AL 14 09 |
- Sum[n*((n+1)^2)] = n*(n+1)*(n+2)*(3*n+5)/12
AL 14 10 |
- S(n) = (1 -4/1)*(1 - 4/9)*(1 - 4/25)*(1 - 4/49)*......
AL 14 11 |
- S(n) = (1 + 1)*(1 + 1/2)*(1 + 1/3)*.....*(1 + 1/n) = n + 1
AL 14 12 |
- S(n) = (1^2)/(1*3) + (2^2)/(3*5) + (3^2)/(5*7) + .... = (n*(n+1))/(2*(2*n+1))
AL 14 13 |
- Is this series S(n) = 2 + 4 + 6 + ..... + 2*n = (n + 1/2)^2 true ?
AL 14 14 |
- Is S(n) = n^2 + n + 41 always a prime number ?
AL 14 15 |
- Prove that ((n^3) + 3*(n^2) + n)/3 is an integer
AL 14 16 |
- Prove that (2*(n^3) + 3*(n^2) + n) is divisible by 6
AL 14 17 |
- Prove that 1! + 2! + 3! + 4! + ..... + n! = 3^(n-1)
Answers
AL 14 01. Defintion
Induction method
A series S(n) = Sum[T(n)] is true for all interal number
It must satisfy the following two tests
Part 1 : It is true for n = 1, 2, and 3
Part 2 : It is true for n = k + 1
Example : 1 + 2 + 3 + .... + k = k*(k+1)/2
Check the sum of the series is true for k = 1, k = 2 and k = 3
k = 1 : LHS = S(1) = 1 and RHS = 1*(1+1)/2 = 1. The series is true for k = 1
k = 2 : LHS = S(2) = 3 and RHS = 2*(2+1)/2 = 3. The series is true for k = 2
k = 3 : LHS = S(3) = 6 and RHS = 3*(3+1)/2 = 6. The series is true for k = 3
Add (k+1)th term to both sides
LHS = 1 + 2 + 3 + ..... + k + (k+1)
RHS = k*(k+1)/2 + (k+1)
RHS = (k+1)*(k/2 + 1)
RHS = (k+1)*((k+1) + 1)/2
RHS remains the same form n*(n+1)/2 if n = k + 1
Since it satisfies test 1 and test 2. Hence it is true for all numbers
Other method : Use AP series formula
T(1) = 1
T(n) = n
S(n) = n*(t(1)+T(n))/2 = n*(n+1)/2
Go to Begin
AL 14 02. S(n) = 1 + 3 + 6 + + .... + n*(n+1)/2 = n*(n+1)*(n+2)/6
Proof using induction method : test 1
n = 1
LHS = 1
RHS = 1*(1+1)*(1+2)/6 = 1
n = 2
LHS = 1 + 3 = 4
RHS = 2*(2+1)*(2+2)/6 = 4
n = 3
LHS = 1 + 3 + 6 = 10
RHS = 3*(3+1)*(3+2)/6 = 10
Test 2
Add (n+1)th term to both sides
LHS = 1 + 3 + 6 + .... + n*(n+1)/2 + (n+1)*(n+2)/2
RHS = n*(n+1)*(n+2)/6 + (n+1)*(n+2)/2
RHS = (n + 1)*(n + 2)*(n/6 + 1/2)
RHS = (n + 1)*((n + 1) + 1)*((n + 1) + 2)/6
RHS = S(n+1)
Go to Begin
AL 14 03. Using induction prove that 1^2 + 2^2 + ... + n^2 = n*(n+1)*(2*n+1)/6
Induction method : Test 1
n = 1
LHS = 1
RHS = 1*(1+1)*(2*1+1)/6 = 1
n = 2
LHS = 1 + 4 = 5
RHS = 2*(2+1)*(2*2+1)/6 = 5
n = 3
Test 2
Add t(n+1) to both sides
LHS = 1 + 2^2 + 3^2 +.... + k^2 + (k+1)^2 = S(k+1)
RHS = k*(k+1)*(2*k+1)/6 + (k+1)^2
RHS = (k+1)*(k*(2*k+1)/6+(k+1))
RHS = (k+1)*(2*k^2+k)/6+(k+1))
RHS = (k+1)*(2*k^2 + k + 6*(k+1))/6
RHS = (k+1)*(2*k^2 + 7*k + 6)/6
RHS = (k+1)*(k+2)*(2*k+3)/6
RHS = (k+1)*((k+1)+1)*(2*(k+1)+1)/6
RHS = S(k + 1)
Other proof methods
Sum[n^2] = ?
More methods to prove
Go to Begin
AL 14 04. Prove 1^3 + 2^3 + 3^3 + ..... + n^3 = ((n*(n+1)/2)^2
Sum[n^2] = ?
Various methods to prove
Go to Begin
AL 14 05. Prove that 1/(1*2) + 1/(2*3) + ..... + 1/(n*(n+1)) = 1 - 1/(n+1)
Proof : test 1
n = 1 : LHS = 1/2 and RHS = 1 - 1/2 = 1/2
n = 2 : LHS = 1/2 + 1/6 = 4/6 = 2/3 and RHS = 1 - 1/3 = 2/3
n = 3 : LHS = 2/3 + 1/12 = 9/12 = 3/4 and RHS = 1 - 1/4 = 3/4
Test 1 is true
Test 2
Add T(n+1) to 1/((n+1)*(n+2) to both sides
RHS = 1 - 1/(n + 1) + 1/((n + 1)*(n + 2))
RHS = 1 - ((n + 2) - 1)/((n + 1)*(n + 2))
RHS = 1 - (n + 1)/((n + 1)*(n + 2))
RHS = 1 - 1/((n + 1) + 1)
Hence it is true for all integers terms
Other method : Conjective
1/(1*2) = 1 - 1/2
1/(2*3) = 1/2 - 1/3
1/(3*4) = 1/3 - 1/4
......
1/((n-1)*n) = 1/(n-1) - 1/n
1/((n*(n+1)) = 1/n - 1/(n+1)
Sum all on the left hand side = LHS
Sum all on the right hand side = 1 - 1/(n+1)
Go to Begin
AL 14 06. Sum[1/((2*n-1)*(2*n+1)) = (1 - 1/(2*n+1))/2
Proof : Test 1
n = 1 : LHS = 1/3 and RHS = (1 - 1/3)/2 = 1/3
n = 2 : LHS = 1/3 + 1/15 = 6/15 = 2/5 and RHS = (1 - 1/5)/2 = 2/5
n = 3 : LHS = 2/5 + 1/35 = 3/7 and RHS = (1 - 1/7)/2 = 3/7
Test 1 is true
Test 2
Add T(n+1) = 1/((2*n+1)*(2*n+3) to both sides
RHS = (1 - 1/(2*n + 1))/2 + 1/((2*n + 1)*(2*n + 3))
RHS = 1/2 - 1/(2*(2*n + 1)) + 1/((2*n + 1)*(2*n + 3))
RHS = 1/2 - ((2*n + 3) - 2)/(2*(2*n + 1)*(2*n + 3)))
RHS = 1/2 - (2*n+1)/(2*(2*n + 1)*(2*n + 3))
RHS = 1/2 - 1/(2*(2*n + 3))
RHS = (1 - 1/(2*(n+1) + 1))/2
Hence it is true for all integers terms
Other method : Conjective
1/(1*3) = 1 - 1/3 = 2/3
1/(3*5) = 1/3 - 1/5 = 2/15
1/(3*4) = 1/5 - 1/7 = 2/35
......
1/((2*n-3)*(2*n-1)) = 1/(2*n-3) - 1/(2*n-1)
1/((2*n-1)*(2*n+1)) = 1/(2*n-1) - 1/(2*n+1)
Sum all on the left hand side = LHS
Sum all on the right hand side = 1 - 1/(2*n+1)
Go to Begin
AL 14 07. Sum[1/(n*(n+1)*(n+2)] = n*(n+3)/(4*(n+1)*(n+2)
Induction method : Test 1
n = 1, LHS = 1/6 and RHS = 1*4/(4*2*3) = 1/6
n = 2, LHS = 1/6 + 1/24 = 5/24 and RHS = 2*5/(4*3*4) = 5/24
n = 3, LHS = 5/24 + 1/(3*4*5) = 40 and RHS = 3*6/(4*4*5) = 9/40
Test 1 is true
Test 2
Both sides add T(n+1) = 1/((n+1)*(n+2)*(n+3))
We expect RHS = ((n+1)*((n+1)+3)/(4*((n+1)+1)*((n+1)+2))
Proof
RHS = (n*(n+3))/(4*(n+1)*(n+2)) + 1/((n+1)*(n+2)*(n+3))
RHS = (n*(n+3)*(n+3) + 4)/(4*(n+1)*(n+2)*(n+3))
RHS = (n^3 + 6*n^2 + 9*n + 4)/(4*(n+1)*(n+2)*(n+3))
RHS = ((n + 4)*(n^2 + 2*n +1))/(4*(n+1)*(n+2)*(n+3))
RHS = ((n+1)*(n+4))/(4*(n+2)*(n+3))
RHS = ((n+1)*((n+1)+3))/(4*((n+1)+1)*((n+1)+2))
Test 2 is true
Other method : Conjecture
1/(1*2*3) = (1/(1*2) - 1/(2*3))/2 = 1/6
1/(2*3*4) = (1/(2*3) - 1/(3*4))/2 = 1/24
1/(3*4*5) = (1/(3*4) - 1/(4*5))/2 = 1/60
Hence we have results
T(n) = 1/(n*(n+1)*(n+2)) = (1/(n*(n+1)) - 1/((n+1)*(n+2)))/2
Sum of LHS = given series
Sum of RHS = (1/2 - 1/((n+1)*(n+2)))/2
Hence RHS = (n*(n+3))/(4*(n+1)*(n+2))
Go to Begin
AL 14 08. Sum[(2*n-1)^2] = n*(4*n^2 - 1)/3
Induction method
n = 1, LHS = 1 and RHS = 1
n = 2, RHS = 10 and RHS = 2*(16 - 1)/3 = 10
....
Both sides add (2*n + 1)
We expect RHS = ((n+1)*(4*(n+1)^2 - 1)/3
Proof
RHS = n*(4*n^2 - 1)/3 + (2*n + 1)^2
RHS = (4*n^3 - n) + (12*n^2 +12*n + 3))/3
RHS = (4*n^3 + 12*n^2 + 11*n + 3))/3
RHS = ((n+1)*(4*N^2 + 8*n +3))/3
RHS = (n+1)*(4*(n+1)^2 - 1)/3
Other method
Sum[(2*n-1)^2] = Sum[(4*n^2 - 4*n + 1)]
Use formula
Sum[1] = n
Sum[n] = n*(n+1)/2
Sum[n^2] = n*(n+1)*(2*n+1)/6
Sum[(2*n-1)^2] = Sum[(4*n^2 - 4*n + 1)]
= Sum[4*n^2] - Sum[4*n] + Sum[1]
= 4*n*(n+1)*(2*n+1)/6 - 4*n*(n+1)/2 + n
= n*(4*(n+1)*(2*n+1)/6 - 2*n - 2 + 1)
= n*(8*n^2 + 12*n + 4 - 12*n - 12 + 6)/6
= n*(8*n^2 - 2)/6
= n*(4*n^2 - 1)/3
Go to Begin
AL 14 09. Sum[n*((n+1)^2)] = n*(n+1)*(n+2)*(3*n+5)/12
Induction : Test 1
n = 1, LHS = 1*2^2 = 4 and RHS = (1*2*3*8)/12 = 4
n = 2, LHS = 4 + 2*9 = 22 and RHS = (2*3*4*11)/12 = 22
n = 3, LHS = 22 + 3*16 = 70 and RHS = (3*4*5*14)/12 = 70
Test 1 is true
Test 2
Both sides add T(n+1) = (n+1)*(n+2)^2
We expect RHS = (n+1)*((n+1)+1)*((n+1)+2)*(3*(n+1)+5)/12
Proof
RSH = n*(n+1)*(n+2)*(3*n+5)/12 + (n+1)*(n+2)^2
RSH = (n+1)*(n+2)*(n*(3*n+5)+12*(n+2))/12
RSH = (n+1)*(n+2)*(3*n^2+17*n+24)/12
RSH = (n+1)*(n+2)*(n+3)*(3*n+8)/12
Other method
Sum[n*(n+1)^2] = Sum[(n^3 + 2*n^2 + n)]
Use formula
Sum[n] = n*(n+1)/2
Sum[n^2] = n*(n+1)*(2*n+1)/6
Sum[n^3] = (n*(n+1)/2)^2
Sum[n^3 + 2*n^2 +n]
= Sum[n^3] + Sum[2*n^2] + Sum[n]
= (n*(n+1)/2)^2 + 2*n(n+1)*(2*n+1)/6 + n*(n+1)/2
= n*(n+1)*(n*(n+1)/4) + (2*n+1)/3 + 1/2
= n*(n+1)*(3*n^2 + 3*n + 8*n + 4 + 6)/12
= n*(n+1)*(3*n^2 - 11*n + 10)/12
= n*(n+1)*(n+2)*(3*n+5)/12
Go to Begin
AL 14 10. S(n) = (1 - 4/1)*(1 - 4/9)*(1 - 4/25)*.....*(1 - 4/((2*n-1)^2)
Question : S(n) = (1 - 4/1)*(1 - 4/9)*(1 - 4/25)*.....*(1 - 4/((2*n-1)^2)
1. Conjecture a formula for this series
2. Prove the formula by induction
Solution
S(1) = (1 - 4) = -3
S(2) = (1 - 4)*(1 - 4/9) = -3*5/9 = -5/3
S(3) = -(5/3)*(1 - 4/25) = -(5/3)*(21/25) = -7/5
Hence the conjecture formula is S(n) = -(2*n + 1)/(2*n - 1)
Proof by induction
Since T(n) = (1 - 4/((2*n - 1)^2)
Hence T(n+1) = (1 - 4/((2*n + 1)^2)
S(n)*T(n+1) = -(2*n + 1)/(2*n - 1)*T(n+1)
We expect RHS = -(2*n + 3)/(2*n + 1)
-((2*n + 1)/(2*n - 1))*(1 - 4/((2*n + 1)^2)
= -((2*n + 1)/(2*n - 1))*(((2*n + 1)^2 - 4)/((2*n + 1)^2)
= -(4*n^2 + 4*n + 1 - 3)/((2*n - 1)*(2*n + 1))
= -((2*n - 1)*(2*n + 3))/((2*n - 1)*(2*n + 1))
= -(2*n + 3)/(2*n + 1)
Test 1 and test 2 of induction are correct
Hence S(n) = -(2*n+1)/(2n-1) is the correct formula
Go to Begin
AL 14 11. S(n) = (1 + 1)*(1 + 1/2)*(1 + 1/3)*.....*(1 + 1/n) = n + 1
Test 1
S(1) = 1 + 1 = 2 and RHS = 1 + 1 = 2. It is true
S(2) = 2*(1 + 1/2) = 3 and RHS = 2 + 1 = 3. It is true
S(3) = 3*(1 + 1/3) = 4 and RHS = 3 + 1 = 4. It is true
Hence test 1 is correct
Test 2
Both side multiply by T(n+1)
We expect RHS = (n+1) + 1
RHS = (n+1)*(1 + 1/(n+1))
RHS = (n+1)*((n+1) + 1)/(n+1)
RHS = (n+1) + 1
Hence test 2 is correct
Hence the S(n) = n + 1 is correct for all n
Go to Begin
AL 14 12. S(n) = (1^2)/(1*3) + (2^2)/(3*5) + (3^2)/(5*7) + .... = (n*(n+1))/(2*(2*n+1))
Test 1
S(1) = (1^2)/(1*3) = 1/3 and RHS = 1*(1 + 1)/(2*(2*1 + 1) = 1/3. It is true
S(2) = 1/3 + (2^2)/(3*5) = 3/5 and RHS = 2*(2+1)/(2*(2*2+1) = 3/5. It is true
S(3) = 3/5 + (3^2)/(5*7) = 6/7 and RHS = 3*(3+1)/(2*(2*3+1) = 6/7. It is true
Hence test 1 is correct
Test 2 : Add T(n+1) to both sides and expect ((n+1)*(n+2))/(2*(2*(n+1)+1))
T(n) = (n^2)/((2*n-1)*(2*n+1))
T(n+1) = ((n+1)^2)/((2*n+1)*(2*n+3))
RHS = (n*(n+1))/(2*(2*n+1)) + ((n+1)^2)/((2*n+1)*(2*n+3))
RHS = (n*(n+1)*(2*n+3) + 2*(n+1)^2)/(2*(2*n+1)*(2*n+3))
RHS = ((n+1)*(n+2)*(2*n+1))/(2*(2*n+1)*(2*n+3))
RHS = ((n+1)*(n+2)/(2*(2*n+3))
Hence Test 2 is also correct
Go to Begin
AL 14 13. Is this series 2 + 4 + 6 + ..... + 2*n = (n + 1/2)^2 true ?
Part 1 test
n = 1 : LHS = 2 and RHS = (1.5)^2 = 2.25
Hence test 1 not true
Part 2 test
RHS = (n + 1/2)^2 + 2*(n + 1)
RHS = n^2 + n + 1/4 + 2*n + 2
RHS = n^2 + 3*n + 9/4
RHS = (n + 3/2)^2
RHS = ((n + 1) + 1/2)^2
Hence test 2 is true
Conclusion
Since test 1 is not true, Hence the sum of this series is not for all numbers
Go to Begin
AL 14 14. Is S(n) = n^2 + n + 41 always a prime number ?
Test 1
n = 1, S(1) = 1 + 1 + 41 = 43 and it is a prime
n = 2, S(2) = 4 + 2 + 41 = 47 and it is a prime
n = 3, S(3) = 9 + 3 + 41 = 53 and it is a prime
Test 1 is true
Test 2
S(n) = n*(n + 1) + 41
S(40) = 40*(40 + 1) + 41 = 40*41 + 41 = 41*(40 + 1) = 41^2
Hence it is not a prime if n = 40
Conclusion
Since test 2 is not true, hence S(n) is not always a prime
Note : We can also use n = 41
S(n) = n*(n + 1) + 41
S(41) = 41*(41+1) + 41 = 41*42 + 41 = 41*(42 + 1) = 41*43
Hence it is not prime if n = 41
Go to Begin
AL 14 15. Prove that ((n^3) + 3*(n^2) + n)/3 is an integer
Keyword
Series : Sum[n*(n+1)/2] = n*(n+1)*(n+2)/6
Proof
((n^3) + 3*(n^2) + n)/3 = n*(n+1)*(n+2)/3
Sum[n*(n+1)/2] = n*(n+1)*(n+2)/6 is integer
Hence ((n^3) + 3*(n^2) + n)/3 = 2*Sum[n*(n+1)/2] and it is integer
Go to Begin
AL 14 16. Prove that (2*(n^3) + 3*(n^2) + n) is divisible by 6
Prove that 1! + 2! + 3! + 4! + ..... + n! = 3^(n-1) Keyword
Series : Sum[n^2] = n*(n+1)*(2*n+1)/6
Proof
(2*(n^3) + 3*(n^2) + n) = n*(n+1)*(2*n+2)
Sum[n^2] = n*(n+1)*(2*n+1)/6 is integer
Hence (2*(n^3) + 3*(n^2) + n)/3 = 6*sum[n^2] and it is divisble by 6
Similar Question
Is (2*(n^3) + 3*(n^2) + n)/6 always an integer ?
Go to Begin
AL 14 17. Prove that S(n) = 1! + 2! + 3! + 4! + ..... + n! = 3^(n-1)
Induction test 1
n = 1 : LHS = 1 and RHS = 3^0 = 1. It is true
n = 2 : LHS = 1+2 = 3 and RHS = 3^1 = 3. It is true
n = 3 : LHS = 1+2+6 = 9 and RHS = 3^2 = 9. It is true
Test 1 is true
Test 2
n = 4 : LHS = 1 + 2 + 6 + 24 = 33 and RHS = 3^3 = 27. It is not true
Hence we do not need to add T(n+1) = (n+1)! to both sides
Conclusion
Hence the S(n) = 3^(n-1) is not True
Go to Begin
AL 14 18. Prove that S(n) = (1 + 3/1)*(1 + 5/4)*(1 + 7/9) + ..... = (n+1)^2
Induction test 1
n = 1 : LHS = 4 and RHS = (1+1)^2 = 4. It is true
n = 2 : LHS = 4*(9/4) = 9 and RHS = (2+1)^2 = 9. It is true
n = 3 : LHS = 9*(16/9) = 16 and RHS = (4+1)^2 = 16. It is true
Test 1 is true
Test 2
T(n) = 1 + (2*n+1)/(n^2)
Multiply T(n+1) = (1 + (2*n+3)/((n+1)^2))
We expect S(n+1) = (n+2)^2
RHS = ((n+1)^2)*(1 + (2*n+3)/((n+1)^2)
RHS = (n+1)^2 + (2*n+3)
RHS = n^2 + 2*n + 1 + 2*n + 3
RHS = n^2 + 4*n + 4
RHS = (n+2)^2
Test 2 is true
Conclusion
Hence the S(n) = 3^(n-1) is not True
Go to Begin
AL 14 00. Outines
Induction method
Test 1 : First check the sequence is true n = 1, n = 2, n = 3
Test 2 : Both sides add (n+1)th terms is still true
Make right hand side to have the same results
Example :
RHS = n(n+1)/2
After add (n+1)th term, RHS = (n+1)*((n+1)+1)/2
Formula : See series in AL 08 00
Sum[n^1] = n*(n+1)/2
Sum[n^2] = n*(n+1)*(2*n+1)/2
Sum[n^3] = (n*(n+1)/2)^2
Sum[n^4] = n*(n+1)*(6*n^3+9*n^2+n-1)/30
Sum[n*(n+1)/2] = n*(n+1)*(n+2)/6
Sum[n*(n+1)*(n+2)/(3!)] = n*(n+1)*(n+2)*(n+3)/(4!)
Sum[n*(n+1)*(n+2)*(n+3)/(4!)] = n*(n+1)*(n+2)*(n+3)*(n+4)/(5!)
Sum[1/(n*(n+1))] = 1 - 1/(n+1)
Sum[1/((2*n-1)*(2*n+1)) = (1 - 1/(2*n+1))/2
Go to Begin
Show Room of MD2002
Contact Dr. Shih
Math Examples Room
Copyright © Dr. K. G. Shih, Nova Scotia, Canada.
