Q1. There are infinitely many stations on a train route. Suppose that the train stops at the first stations and suppose that if the train stops at a station, then it stops at the next station, Show that the train stops at all stations.
Q2. Suppose that you know that a golfer plays the first hole of a golf course with an infinite number of holes and that if this golfer plays one hole, then the golfer goes on to play the next hole. Prove that this golfer plays every hole on the course.
Use mathematical induction in question 13 to prove summation formulae. Be sure to identify where you use the inductive hypothesis.
Q3. Let P(n) be the statement that 12 + 22 + · · · + n2 = n(n + 1)(2n + 1)/6 for the positive integer n.
a) What is the statement P(1)?
b) Show that P(1) is true, completing the basis step of the proof.
c) What is the inductive hypothesis?
d) What do you need to prove in the inductive step?
e) Complete the inductive step, identifying where you use the inductive hypothesis.
f) Explain why these steps show that this formula is true whenever n is a positive integer.
Q4. Let P(n) be the statement that 13 + 23 + · · · + n3 = (n(n + 1)/2)2 for the positive integer n.
(a) What is the statement P(1)?
(b) Show that P(1) is true, completing the basis step of the proof.
(c) What is the inductive hypothesis?
(d) What do you need to prove in the inductive step?
(e) Complete the inductive step, identifying where you use the inductive hypothesis.
(f) Explain why these steps show that this formula is true whenever n is a positive integer.
Q5. (a) Find a formula for the sum of the first n even positive integers.
(b) Prove the formula that you conjectured in part (a).
Q6. a) Find a formula for
1/1·2 + 1/2·3 + · · · + 1/n(n+1)
by examining the values of this expression for small values of n.
b) Prove the formula you conjectured in part (a).
Q7. a) Find a formula for
½ + ¼ + 1/8 + · · · + 1/2n
by examining the values of this expression for small values of n.
b) Prove the formula you conjectured in part (a).
Q8. Prove that
j=0∑n(-½)j = 2n+1 + (-1)n/3·2n
whenever n is a nonnegative integer.
Q9. Prove that 12 - 22 + 32 - · · · + (-1)n-1n2 = (-1)n-1 n(n+1)/2 whenever n is a positive integer.
Q10. Prove that for every positive integer n, k=1∑n k2k = (n-1)2n+1 + 2.
Q11. Prove that for every positive integer n,
1 · 2 + 2 · 3 + · · · + n(n + 1) = n(n+ 1)(n + 2)/3.
Q12. Prove that for every positive integer n,
1 · 2 · 3 + 2 · 3 · 4 + · · · + n(n + 1)(n + 2) = n(n + 1)(n + 2)(n + 3)/4.
Q13. Prove that j=1∑n j4 = n(n + 1)(2n + 1)(3n2 + 3n - 1)/30 whenever n is a positive integer.
Use mathematical induction to prove the inequalities in Question 14-22.
Q14. Let P(n) be the statement that n! < nn, where n integer greater than 1.
(a) What is the statement P(2)?
(b) Show that P(2) is true, completing the basis step of the proof.
(c) What is the inductive hypothesis?
(d) What do you need to prove in the inductive step?
(e) Complete the inductive step.
(f) Explain why these steps show that this inequality is true whenever n is an integer greater than 1.
Q15. Let P(n) be the statement that
1 + ¼ + 1/9 + · · · + 1/n2 < 2 - 1/n,
where n is an integer greater than 1.
(a) What is the statement P(2)?
(b) Show that P (2) is true, completing the basis step of the proof.
(c) What is the inductive hypothesis?
(d) What do you need to prove in the inductive step?
(e) Complete the inductive step.
(f) Explain why these steps show that this inequality is true whenever n is an integer greater than 1.
Q16. Prove that 3n < n! if n is an integer greater than 6.
Q17. Prove that 2n > n2 if n is an integer greater than 4.
Q18. For which nonnegative integers n is n2 < n!? Prove your answer.
Q19. For which nonnegative integers n is 2n + 3 < 2n? Prove your answer.
Q20. Prove that 1/(2n) ≤ [1 · 3 · 5 · · · · · (2n - 1)]/(2 · 4 · · · · · 2n) whenever n is a positive integer.
Q21. Prove that if h > -1, then 1 + nh ≤ (1 + h)n for all non-negative integers n. This is called Bernoulli's inequality.
Q22. Suppose that a and b are real numbers with 0 < b < a. Prove that if n is a positive integer, then an - bn ≤ nan-1 (a - b).