As usual, we start with the definitions.
PRINCIPLE OF MATHEMATICAL INDUCTION To prove that P(n) is true for all positive integers n, where P (n) is a propositional function, we complete two steps:
- BASIS STEP: We verify that P (1) is true.
- INDUCTIVE STEP: We show that the conditional statement P (k) → P (k + 1) is true for all positive integers k.
The definition above is from the textbook Discrete Mathematics and its Applications by Rosen.
Now we can solve the exercise by completing the two steps from the principle of mathematical induction.
1- Basis step:
P(1): 1×1! = (1+1)! -1
Notice that in this case, the basis step is n=1 because n is a positive integer.
1×1! = (1+1)! -1
1 = 2! -1 = 2 -1 =1
This concludes the basis step.
2- Inductive step:
P(k): 1·1!+2·2!+···+k·k!=(k+1)!−1
P(K+1):1·1!+2·2!+···+k·k! + (k+1)(k+1)!=((k+1)+1)!−1
Notice that to state P(k+1), we used P(k). On the left side of the equation, we added the term that goes after the kth term (k+1 term) and on the right side of the equation we substitute k by k+1.
Now, let’s simplify.
P(K+1):1·1!+2·2!+···+k·k! + (k+1)(k+1)!=((k+1)+1)!−1
1·1!+2·2!+···+k·k! + (k+1)(k+1)!=(k+2)!−1
Substituting P(k) in P(k+1) we get,
P(k+1):(k+1)!−1 + (k+1)(k+1)!=(k+2)!−1
(k+1)![1+(k+1)] -1 = (k+2)!−1
(k+1)!(k+2) -1 = (k+2)!−1
According the definition of factorial, n!=nx(n-1)!
Therefore, (k+2)! = (k+2)(k+2-1)! = (k+2)(k+1)!
P(k+1); (k+2)! -1 = (k+2)!−1 ⧠
By now, you sure realized how important is the knowledge you learned in previous educational levels, such as algebra, working logarithms, etc. Most of the time, that knowledge is compulsory to be able to complete a proof by induction.
Related pots:
- a) Find a formula for the sum of the first n even positive integers. Prove the formula that you conjectured in part (a)
- Prove that 1^2−2^2+3^2−···+(−1)^(n−1)n^2=(−1)^(n−1) n(n + 1)/2 whenever n is a positive integer
- Prove that 1^2 +3^2 +5^2 +···+(2n+1)^2 =(n+1) (2n + 1)(2n + 3)/3 whenever n is a nonnegative integer
- Mathematical induction with examples
