What is the recurrence formula for #K_n#? #K_n# is the number of strings (#a_1,a_2,...,a_n) with words from set {0, 1, 2} under the following conditions.

This problem is originally asked by @smkwd.
https://socratic.org/questions/how-to-prove-that#484241

I divided it into smaller parts so as to avoid getting the answer too long.

--Here is the divided question--
Consider a string (#a_1,a_2,...,a_n#) with words from set {0, 1, 2}.
We will call the pod of the character (#a_i,a_(i+1),. . . a_j#), where #1≤i≤j≤n# and #a_i = a_(i + 1) =. . . = a_j#. The block is called maximum if it is not contained in no longer block. For example, in string (1, 0, 0, 2, 1, 1) the maximum blocks are (1), (0, 0), (2), (1, 1).
Let #K_n# be the number of such lengths #n# of words from the set {0, 1, 2} in which all maximal blocks have odd lengths.

What is the recurrence formula #K_n# satisfies?

1 Answer
yumean1119
Oct 4, 2017

#K_1=3, K_2=6, K_n=2K_(n-1)+K_(n-2)" "(n>=3)#

Explanation:

First we have to find #K_1# and #K_2#.

#K_1=3# as there are only three string: #(0) (1) (2)#.

#K_2=6# because the 2-words string from the set #{0,1,2}# in which the two maximum blocks have single word are
#(0,1) (0,2) (1,0) (1,2) (2,0) (2,1)#.

Then, what do we need to calculate #K_n# #(n>=3)# ?

Three words strings to have every maximum blocks odd words are categorized into two types.
Strings like #color(red)"(0,0,0)"# are obtained by adding two words that are same as the last word of one word string(i.e. #color(red)"(0)+(0,0)"# and so on.)

Strings like #color(blue)"(0,1,2)"# are obtained by adding a word different from the last word of two words strings. (i.e. #color(blue)"(0,1)+(2)"# and so on.)

This pattern continues for every #n>=3#.
The recurrence formula #K_n# satisfies is:
#K_1=3, K_2=6, K_n=color(blue)(2K_(n-1))+color(red)(K_(n-2))" "(n>=3)#

Related questions
See all questions in Combinations and Permutations
Impact of this question
1959 views around the world
You can reuse this answer
Creative Commons License