Each cell of a grid of unit squares is to be colored white or black. Compute the number of such colorings for which no square is a single color.
Solution
Let denote the number of ways to color a grid subject only to the given constraint, and denote the number of ways to color a grid subject to the given constraint, but with the added restriction that the first column cannot be colored black-black. Consider the first column of a grid that is not subject to the additional constraint. It can be colored black-white or white-black, in which case the leftmost square is guaranteed not to be monochromatic, and so the remaining subgrid can be colored in ways. Otherwise, it is colored white-white or black-black; WLOG, assume that it's colored black-black. Then the remaining subgrid is subject to both constraints, so there are ways to color the remaining subgrid. Hence . Now consider the first column of a grid that is subject to the additional constraint. The first column cannot be colored black-black, and if it is colored white-black or black-white, there are ways to color the remaining subgrid by similar logic to the previous case. If it is colored white-white, then there are ways to color the remaining subgrid, again by similar logic to the previous case. Hence . Therefore, we have , and so . Finally, we have (as the only possibility is to, well, do nothing) and (as any coloring is admissible), so .