How many ways are there to color vertexes of a $n\times n$ square that in every $1\times 1$ squares we should have $2$ blue and $2$ red vertexes? How many ways are there to color vertexes of a $n\times n$ square that in every $1\times 1$ squares we should have $2$ blue and $2$ red vertexes?
My attempt:I had found an answer but it is not in the book because for the first corner we can choose two vertexes to color blue which gives a multiply of $3$ but the answer in the book is $2(2^{n+1}-1)$.Any hints?
 A: HINT
Color the $n+1$ vertices of one side of the square. If there are ever two vertices of the same color next to each other along this side, the colors of all the rest of the vertices are determined. If this does not happen, then think what happens once you color the first vertex of the next line.
A: if the first row is not alternating then there are $2^n-1$ sequences.
If the first row is alternating then every row must be alternating, so there are another $2^n$ sequences.
A: You have a free choice at every vertex on the first row of the grid. Since there are $n\mathord+1$ vertices, that's $2^{n+1}$ options. 
If the pattern chosen is not one of the $2$ alternating-colour options, fulfilling the criterion means that the rest of the grid colouring is already determined. However, for the alternating-colour options, every subsequent row can be either of the alternating-colour options and still meet the requirement, giving a total of $2^{n+1}$ alternating-colour options. 
Total then is $(2^{n+1}-2) +2^{n+1} = 2^{n+2}-2 = 2(2^{n+1}-1)$ as expected.
Your initial $\binom 42=6$ choices in the first square is valid, but cannot be propagated out to the rest of the square on an equal footing, so the factor of $3$ there does not persist. Specifically the choice of diagonally separated colours gives different subsequent choice options from adjacent colours, so you really have $4+2$ options rather than $3\times 2$, if that makes sense to you.
