In chess, the knight can move in eight directions. It can move two squares vertically followed by one square horizontally. It can also move two squares horizontally followed by one square vertically. Since the vertical motion can be up or down and the horizontal motion can be left or right, there are eight squares on a chessboard where a knight can be positioned after one move.

Suppose that we have an nn chessboard with a knight placed in one of the corners. (A normal chessboard is 8 8.) Prove by induction that for n 4, the knight in the corner can be placed in any square of the n n chessboard after a finite sequence of legal knight moves. Note that the knight is not allowed to wander off the board and must stay within the confines of the n n chessboard. For example, the white knight in the figure above can only move to two places after one move. In your proof by induction, you should start with a large chessboard, then consider one or more smaller chessboards (at least 4 4) within it. By the induction hypothesis (and symmetry), you can assume that a knight can move from any corner of the smaller board to any position in the smaller board. Use this to show that a knight can move from any corner of the larger board to any position in the larger board. Some ground rules: You must make good use of induction. Do not describe the sequence of moves made by the knight directly. You must not use iteration instead of induction. (I.e., do not say something like, Continuing in this manner, the knight can reach any position on the board.