Proof by Induction Question with regard to the Knight's Tour I have to prove that the formula $4n^2-12n+8$ gives the number of edges on a knight graph, where n is the number of vertices horizontally and vertically and n^2 is the number of vertices.
I've proved it for $n=4$ (the smallest possible value of $n$ with which the knight graph works) and I've assumed that the result is true for n=k but where do I go from here? How do I prove it works for $n=k+1$?
 A: The idea of induction is that given your answer for n=k, you can show that the same holds (in this case that the number of edges equals 4n^2-12n+8) for n=k+1.
To show this we must look at the number of edges that are added when you take a chessboard of k+1 x k+1 instead of k x k. So lets add a new row and column below and left of the old kxk board. I call this the new board. 
From the corners of this board you have 2 knight moves to the old board (and ofcourse 2 from the old board to these corners, but as we are counting edges and not moves we will only look at moves starting on the new board). The spaces next to the edges each have 3 options. All other new spaces have 4 options.
So the extra number of edges looks to be 3*2 (for the corners) + 4*3 (for the spaces next to the corners) + 2*((k+1)-4)*4 (for all other new spaces) = 6+12+8(k-3)=8k-6.
Note however that from the spaces next to the lower right corner you can also make a move to spaces on the new board, i.e. we counted them double. Therefore we have to substract 2 from the above answer.
Adding this all together; The new board containts all the moves the old one had + 8k-8 extra moves. I.e. 4k^2-12k+8 + 8k-8 = 4(k+1)^2-12(k+1)+8
A: Instead of solving the problem by induction, we can simply calculate the number of edges using our knowledge of how the knight moves. We consider six cases on a n x n chessboard when $n \ge 4$. To make the visualization easier, I have uploaded a picture of an 8 x 8 chessboard.

a) The knight is in the corner. When the knight is located in the corner, it can move to two different squares. There are four corners, so we will have $4 \cdot 2 = 8 $ edges.
b) The knight is located on a square on the edge of the board next to the corner. Here, the knight can move to three squares. As there are $8$ such squares (two next to every corner), we will have $8 \cdot 3 = 24$ edges.
c) The knight is located on the edge of the board but not on the squares in a) or b). Here, the knight has access to 4 squares. As there are $(n-4) \cdot 4$ such squares, we get $(n-4) \cdot 4 \cdot 4 = 16(n-4)$ edges.
d) The knight is on one of the squares that is adjacent to the corner but not on the edge. Here, the knight can move to $4$ squares, and there are $4$ such squares, so we have $4 \cdot 4 = 16$ edges.
e) The knight is on the row or column that is next to the row or column that's on the edge of the board, but not on the squares in d) or b). There are $(n-4) \cdot 4$ such squares and on each such square the knight can move to 6 squares, so we get $(n-4) \cdot 4 \cdot 6 = 24(n-4)$ edges.
f) The knight is on any other square, that is the squares that are not the two first or two last columns or the two top or two bottom rows. There are $(n-4) \cdot (n-4)$ such squares and on each such square, the knight can move to 8 squares, giving us $8 \cdot (n-4)^2$ edges.
Now we just calculate the sum of the edges in a) - f). Since we counted each edge twice, our answer will be half of this sum:
$\frac{16+24+16(n-4)+16+24(n-4)+8(n-4)^2}{2} = 4n^2 - 12n + 8$
Note: Incidentally, the answer is also valid for $n \ge 1$. For $n=1$ and $n=2$, the formula will give us the answer $0$, which is true since a knight on a 1 x 1 and a 2 x 2 chessboard has access to no squares, hence the corresponding knight graphs have no edges. A knight graph for the 3 x 3 chessboard is a disconnected graph with the circle graph $C_8$ and a lone vertex as components. The formula will give us that this graph will have $8$ edges, which is quite true.
