Mathematical Induction Homework Help, Assignment Help, Online Tutor, Tutoring

Submit Assignment

* *

Payment Online Assignment Help

Trigonometry Homework

Homework Help

sfsf

Mathematical Induction

Let us consider some illustrative examples:

Example 1: Suppose we have stamps of two different denominations, 3 cents and 5 cents. We want to show that it is possible to make up exactly any postage of 8 cents or more using stamps of these two denominations. Clearly, the approach of showing case by case how to make up postage of 8 cents, 9 cents, 10 cents, and so on, using 3-cent and 5-cent stamps will not be a fruitful one, because there is an infinite number of cases that if it is possible to us consider an alternative approach. We want to show that if it is possible to make up exactly a postage of k + 1 cents using 3-cent and 5-cent stamps. We examine two cases: suppose we make up postage of k cents using at least one 5-cent stamp. Replacing a 5-cent stamp by two 3-cent stamps will yield a way to make up postage of k + 1 cent. On the other hand, suppose we make up postage of k cents using 3-cent stamps only. Since k ≧ 8, there must be at least three 3-cent stamps. Replacing 3-cent stamps by two 5-cent stamps will yield a way to make up postage of k + 1 cent. Since it is obvious how we can make up postage of 8 cents, we conclude that we can make up a postage of 9 cents, which, in turn, leads us to conclude that we can make up a postage of 10 cents, which, in turn, leads us to conclude that we can make up a postage of 11 cents, and so on.

Example 2: Suppose we remove a square from a standard 8 × 8 chessboard. Given 2l L-shaped triominoes, we want to know whether it is possible to tile the 63 remaining squares of the chessboard with triominoes. (By tiling the remaining squares of the chessboard, we mean covering each of them exactly once without parts of the triominoes extending over the removed square or the edges of the board). The answer to our question is affirmative. We can actually prove a general result, which we shall proceed to do.

A chessboard with one of its squares removed will be referred to as a defective chessboard. We want to show that any defective 2ⁿ × 2ⁿ chessboard can be tiled with L-shaped triominoes. It is trivially obvious that a defective 2 × 2 chessboard can be tiled with an L-shaped triomino. Let us now assume that any defective 2^k × 2^k chessboard can be tiled with L-shaped triominoes and proceed to show that any defective 2^k+1× 2^k+1 chessboard can also be tiled with L-shaped triominoes. Consider a defective 2^k+1 × 2^k+1 chessboard. Let us divide the chessboard into four quadrants, each of which is a 2^k × 2^k chessboard. One of these 2^k × 2^k chessboards is a defective one. Furthermore, by placing an L-shaped triomino at the centre of the 2^k+1 × 2^k+1 chessboard, we can imagine that the other three quadrants are also defective 2^k × 2^k chessboards. Since, we assume that any defective 2^k × 2^k chessboard can be tiled with L-shaped triominoes; we can tile each of the quadrants with L-shaped triominoes, and conclude that any defective 2^k+1 × 2^k+1 chessboard can be tiled with L-shaped triominoes. Thus, starting with the tiling of any defective 2 × 2 chessboard, we have proved that we can tile any 2ⁿ × 2ⁿ defective chessboard.

These two examples illustrate a very powerful proof technique in mathematics known as the principle of mathematical induction. For a given statement involving a natural number n, if we can show that:

1. The statement is true for n = n₀; and

2. The statement is true for n = k + 1, assuming that the statement is true for n = k, (K ≧ n₀)