nsmathinduction.html

The Principle of Mathematical Induction

Hints | Solutions

Some statements that are true for any value of an integer or a natural variable can be proved using the method of mathematical induction.

The Principle of Mathematical Induction states:

statement p(1) is true, and
for any n if p(n) is true, then p(n + 1) is true,

then statement p(n) is true for all integer n > 1.

The following two are variations of the Principle of Mathematical Induction:

Variation 1:

statement p(k) is true, and
for any n > k if p(n) is true, then p(n + 1) is true,

then statement p(n) is true for all integer n > k.

Variation 2:

statement p(1) is true, and
for any n if p(1), p(2), ..., p(n) are true, then p(n + 1) is true,

then statement p(n) is true for all integer n > 1.

How does each variation differ from the Principle of Mathematical Induction?
Use the Principle of Mathematical Induction or one of its variations to solve these problems.
Prove that
1. n! > 3ⁿ for n = 7, 8, 9, ....
2. 2ⁿ > n² for n = 4, 5, 6, ....
Any convex polygon with n sides can be cut into n - 2 triangles. Prove it.
The triangle inequality states that the length of a triangle’s side is always smaller than the sum of the lengths of the other two sides of that triangle. Prove that a side length of
1. a quadrilateral
2. a pentagon
3. any polygon
is less than the sum of all its other side lengths.
Prove that if a plane is divided into regions by several lines, it is always possible to color all the regions with two different colors so that any two neighbor regions (regions that share a boundary segment or a boundary ray) are colored in different colors.
1. Prove that checkerboards 2 × 2, 4 × 4, 8 × 8, 16 × 16, ... with one corner square cut out can be cut into “corners” (squares 2 × 2 without one square).
2. What if the missing square is not in the corner of the checkerboard?
Suppose x + is an integer. Prove that x² + , x³ + , x³ + , ..., xⁿ + are also integers.
Prove that for n = 1, 2, 3, 4, ... $1 - 1-+ 1-- 1-+ ...+ --1----- -1- = 2 3 4 2n - 1 2n$ $1 1 1 1 1 ------+ ------+ ------+ ...+ -------+ --- n + 1 n + 2 n + 3 2n - 1 2n$

Hints

Problem | Solutions

Hint to problems 2-8. For each problem, what is n, the variable of induction?

Hint to problem 2. Use variation 1 of the Principle of Mathematical Induction. How many times will the left and the right parts grow if n becomes 1 larger?

Hint to problem 5. Consider n to be the number of lines. If the coloring is possible for n lines, then after drawing a new n + 1st line the coloring is correct on both sides of it. Only along this new line is there a clash. Can coloring of regions on one of the sides be changed to help?

Hint to problem 7. Use variation 2 of the Principle of Mathematical Induction.

Hint to problem 8. How does each sum change if n becomes 1 larger?

Solutions

Problem | Hints

Variation 1 does not require the statement which is being proved to be true for every natural value of n beginning with 1. Instead, in this variation the statement is proved true for any n from some point on. Variation 2 assumes that the statement is true for any value of n prior to given one, not only to the previous one, and then requires proof that it is true for the given one.
1. If n = 7, then n! = 7! = 540 and 3ⁿ = 3⁷ = 2187, and thus n! > 3ⁿ. Assume that for some value of n > 7 it is true that n! > 3ⁿ. Then, multiplying the left part of this inequality by n + 1 and the right part of the inequality by 3 would only strengthen the inequality, and meanwhile we obtain n! × (n + 1) > 3ⁿ × 3, or (n + 1)! > 3ⁿ⁺¹. Thus, by the first variation of the principle of mathematical induction, the statement is true for any n > 7.
2. The proof is similar to the one in 3(a), only in the step of induction add 2ⁿ and 2n + 1 to the corresponding parts of the inequality assumed to be true. Use also the chain 2ⁿ > n² > 3n > 2n + 1, which is true for n > 3.
A rectalgle can be cut into 2 triangles, so for n = 4 the statement is correct. Suppose the statement is correct for another value of n, n > 4. Then it is also correct for n + 1, as we first cut one triangle off the polygon by a diagonal, leaving an n-sided polygon, which then can be cut into n - 2 triangles by the assumption.
1. Consider a quadrilateral ABCD. We need to prove that AB < BC + CD + DA. Draw diagonal AC; by the triangle inequality AB < BC + AC. Also by the triangle inequality (this time applied to triangle ACD) AC < CD + DA. Therefore, AB < BC + CD + DA.
2. Draw a diagonal that will cut the pentagon into a triangle and a quadrilateral. Let the quadrilateral contain the side that you are proving is shorter than the sum of the rest side lengths of the pentagon. In 2(a) it was proved that the side of a quadrilateral is shorter than the sum the lengths of its other sides. The length of the side of the quadrilateral which is a diagonal of the pentagon can be replaced by the sum of the other two side lengths, it will only strengthen the inequality (because this sum is greater than the replaced length of the diagonal).
3. For a triangle the statement is true; it is the familiar triangle inequality. Assume the statement is true for an n-sided polygon. Consider a polygon with n + 1 sides. Draw a diagonal that will cut it into an n-sided polygon and a triangle. By assumption one side is smaller that the sum of the lengths of the other sides of the n-sided polygon. One of these other sides is the diagonal of the original polygon. Substituting the length of this side by the sum of lengths of two other sides of the cut-off triangle, we only strengthen the inequality. Therefore, as the statement is true for a triangle (n = 3), and if it is true for n (n > 3) it is also true for n + 1, the statement is true for any polygon (n > 3).
For one line it works: just use a color for each region. Suppose it works for n lines also. Color the regions as required, and then draw the n + 1st line. On one side of the new line, switch the color of each region to the opposite.
1. For n = 1 we get a 2 × 2 checkerboard without a corner square, which is already “precut.” Suppose it is possible to cut into corners a checkerboard 2ⁿ × 2ⁿ without a corner square, where n > 1. Then, given a checkerboard 2ⁿ⁺¹ × 2ⁿ⁺¹, we can cut into three complete checkerboards 2ⁿ × 2ⁿ and one checkerboard 2ⁿ × 2ⁿ without a corner square. The last one can be cut by assumption, and the first three can be turned into checkerboards without a corner square by cutting off one corner from each:
  
  Then each of the three checkerboards can be cut into corners by assumption.
2. The proof is exactly the same as in 6(a).
For n = 1 the statement is correct: if x + is an integer, then x¹ + is also an integer, because it is exactly the same. No need to check the statement for n = 2, but it also does no harm, so we can do it. For n = 2, xⁿ + = x² + = (x + )² - 2, which is an integer, as x + is an integer as a difference of two integers.
Assume that xⁿ + is an integer for all values of n < k. Then (x^k + )(x + ) = (x^k+1 + ) + (x^k-1 + ) is also an integer as the product of two integers. The value of the expression in the second parenthesis is also an integer (by assumption), and so x^k+1 + is an integer as the difference of two integers.
For n = 1 the equality holds: 1 - = . Assume it holds for some value of n. Show that it then holds for n + 1. By assumtion, $1 - 1-+ 1-- 1-+ ...+ --1----- -1- = 2 3 4 2n - 1 2n$ $1 1 1 1 1 ------+ ------+ ------+ ...+ -------+ ---. n + 1 n + 2 n + 3 2n - 1 2n$ Adding - to both sides of the equation will give the required left side: $1- 1- 1- ---1--- -1- --1---- ----1---- 1- 2 + 3 - 4 + ...+ 2n - 1- 2n + 2n + 1 - 2(n + 1) =$ $1 1 1 1 1 1 1 ------+ ------+ ------+ ...+ ------+ ---+ -------- --------- n + 1 n + 2 n + 3 2n- 1 2n 2n + 1 2(n + 1)$
The right side:
$--1---+ --1---+ --1---+ ...+ --1---+ 1--+ ---1---- ----1---- n + 1 n + 2 n + 3 2n- 1 2n 2n + 1 2(n + 1)$ can be changed to $--1---+ --1---+...+ ---1---+ -1-+ ---1---+( --1---- ---1----), n + 2 n + 3 2n - 1 2n 2n + 1 n + 1 2(n + 1)$ which is equal to $--1---+ --1---+ ...+ ---1---+ 1--+ ---1---+ ---1----, n + 2 n + 3 2n - 1 2n 2n + 1 2(n + 1)$ which is precisely what must be on the right side.