Thus, there are five rows of length three. Furthermore, the construction suggests a recursive approach to generating all the rows of length ${tex`n`}. The rows of length ${tex`n`} could be constructed from the rows of length ${tex`n-2`} and the rows of length ${tex`n-1`}: - We construct a row of length ${tex`n`} from a row of length ${tex`n-2`} by appending an empty square and then a king. - We construct a row of length ${tex`n`} from a row of length ${tex`n-1`} by appending an empty square. This yields all the rows of length ${tex`n`} and is exactly how the boards of length 8 were constructed above. Furthermore, if we let ${tex`K_n`} denote the number of ways to place kings on a row of length ${tex`n`}, this construction shows that ${tex.block`K_n = K_{n-1} + K_{n-2}.`} This makes it easy to count the number of ways to place kings on a row of length ${tex`n`}.

Length of the row	1	2	3	4	5	6	7	8
Number of ways	2	3	5	8	13	21	34	55

Note that each term in the second row is the sum of the previous two terms. This is the same recursive formula for the famous Fibonacci sequence: ${tex.block`F_1 = 1, \: F_2 = 1, \: F_n = F_{n-1} + F_{n-2},`} which yields ${tex.block`(1,1,2,3,5,8,\ldots).`} Note that our sequence ${tex`K_n`} is shifted two steps from the Fibonacci sequence. Thus, another way to write write the solution to our simpler problems is as ${tex`F_{10} = 55`}.