# 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?

**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 (

We will call the pod of the character (

Let

What is the recurrence formula

##### 1 Answer

#### Explanation:

First we have to find

Then, what do we need to calculate

Three words strings to have every maximum blocks odd words are categorized into two types.

Strings like

Strings like

This pattern continues for every

The recurrence formula