Problem — Given an n × n chessboard, our problem is to count the number of ways we can place two queens on the board in such a way that they do not attack each other

"To get a recursive solution, we may focus on the last row and last column of the n× n board (Fig. 3.4). First, if there are no queens on the last row or column, the number of combinations is simply q(n − 1). Then, there are 2n − 1 positions for a queen on the last row or column. It attacks 3(n − 1) squares, so there are n*n − 3(n − 1) − 1 positions for the other queen. Finally, there are (n − 1)(n − 2) combinations where both queens are on the last row or column. Since we counted those combinations twice, we have to remove this number from the result. By combining all this, we get a recursive formula q(n) = q(n − 1) + (2n − 1)(n*n − 3(n − 1) − 1) − (n − 1)(n − 2) = q(n − 1) + 2(n − 1)^2(n − 2), which provides an O(n) solution to the problem."

Sorry if this is a dumb question. I am having trouble understanding the last bit which talks about the case where there are two queens placed on the last row or column of the board ((n-1)(n-2)). Why do we have to remove this from the result? (Why can't it simply be q(n) = q(n − 1) + (2n − 1)(n*n − 3(n − 1) − 1)?)

Also, there's a follow up

"Finally, it turns out that there is also a closed-form formula q(n) = n^4/2 - 5n^3/3 + 3n^2/2 - n/3 which can be proved using induction and the recursive formula. Using this formula, we can solve the problem in O(1) time."

How does one go about finding the closed form formula given a recurrence relation?