Here is a concatenation table to get all of the colorings of a row of three squares. We used the results of the two-square concatenations to get the column headings for this table:
Notice that we have 2^3 = 8 different results.
We can create all the possible colorings of four squares by creating a table with 8 columns and concatenating each string with either a or b. Or we could use the results of the 2-square table like this:
If we continue this process until we get strings of 9, how many strings do we end up with?