Discrete Mathematics

[sam444]

Find and solve a recurrence relation for the number of different square subboards of any size that can be drawn on an n × n chessboard.

I'm not sure even how to attempt this problem. I know it is an inhomogeneous recurrence relation, but thats about it. Any help would be greatly appreciated.

 

[galactus]

I saw this problem in a combinatorics class. It's rather typical if one studies recurrence relations.

If you look at a 1X1 board, of course, there is 1 square.

On a 2X2 board one can make 5 square subboards.

On a 3X3, there are 14 subboards.

On a 4X4, there are 30 subboards

and so on

Notice the difference between the numbers.

5-1=4
14-5=9
30-14=16

Perfect squares...

So, the recurrence is $\displaystyle f_{n-1}+n^{2}$

$\displaystyle f(2)=f(1)+2^{2}=1+4=5$

$\displaystyle f(3)=f(2)+3^{2}=5+9=14$

$\displaystyle f(4)=f(3)+4^{2}=14+16=30$

and so on.

The closed form for the sum of the n^2 is

$\displaystyle \frac{n(n+1)(2n+1)}{6}$

So, how many for a normal 8X8 board?.

$\displaystyle \frac{8(8+1)(2*8+1)}{6}=204$