practice problems pending

Q1)  A square of dimension (n-1) * (n-1) is divided into (n-1)^2 unit squares in the chess board manner. Now, each of these (n^2) vertices of these squares are to be painted black or blue such that each unit square has exactly two black vertices. In how many ways can this be done?
S1.

Look at an individual square.
There are 2 ways for it to yield 2 black vertices.
One horizontal edge blue(or black), other black(or blue).
Or 1 color each on top edge, and similarly on bottom edge.

Once you expand the pattern, there will be only 2 ways to get it done.
Each row alternates or each column alternates or both alternate.

Case 1: Each row alternates. So each row can start with one of 2 colors and then the pattern is fixed.
So 2^n ways since there are 'n' rows.
Case 2: Each column alternates. 2^n again.
Case 3: Both alternate. Exactly 2 ways like a chessboard.

Total: 2^n.2 - 2 = 2^(n+1) - 2.

Q2.

S2.
As the diagram shows a 2x2 bounding box can hold 2 different squares.
That rule actually generalized to any kxk bounding box. It can hold 'k' different squares.

How may KxK bounding boxes are there?
K= 1 => n^2
K = 2 => (n-1)^2
K = k => (n - k + 1)^2
K = n => (1)^2

So total squares:
Sigma[k * (n - k + 1)^2] k = 1 to n
Let n - k + 1 = m
Expr. becomes Sigma[(n-m+1)*m^2], m = 1 to n
 = (n+1)*sigma(m^2) - sigma(m^3)
 = (n+1)*n*(n+1)*(2n+1)/6 - [n(n+1)/2]^2
 = n(n+1)^2[(2n+1)/6 - n/4]
 = n(n+1)^2/12 * (4n + 2 - 3n)
= n(n+2)(n+1)^2/12