Tyrone had a good solution to this problem:

Each time the table gets bigger, we add a new ring round the edge. In a (2N+1)x(2N+1) ring, we need N+1 colours.
Here

N=

n-1 2

. So we need to work out 1+2+3+¼+N+1. But using the formula for the (N+1)th triangular number, this is

(N+1)(N+2) 2

. Since

N=

n-1 2

, the answer is

(n+1)(n+3) 8

.