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=\frac{n-1}{2}$. So we need to work out $1+2+3+\dots +N+1$. But using the formula for the $(N+1)$th triangular number, this is $\frac{(N+1)(N+2)}{2}$. Since $N=\frac{n-1}{2}$, the answer is $\frac{(n+1)(n+3)}{8}$.