Question

Question #3ecb0

Answer 1

We can prove this using mathematical induction.
The answer got too lengthy and there will be some improvement.

Explanation:

[Part 1] Base case(`n=2`)
To show that the recurrence is true for `n=2` we have to evaluate `L_1`, `L_2`, `K_1` and `K_2`.

`K_1=L_1=3` is obvious, 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)`.

`L_2=7`, as all strings without adjacent 0 and 2 are
`(0,0),(0,1),(1,0),(1,1),(1,2),(2,1),(2,2)`

Thus, `L_2=K_2+1/3K_1` is true.

[Part 2]
What we need to do is to find a recurrence for `K_n` `(n>=3)` .

This part is long, so I posted it in another article.
https://socratic.org/questions/what-is-the-recurrence-formula-for-k-n-k-n-is-the-number-of-strings-a-1-a-2-a-n-

The result is `K_1=3, K_2=6, K_n=2K_(n-1)+K_(n-2)" "(n>=3)`

[Part3] Then we are going to find the recurrence of `L_n` `(n>=3)` .
Again, I posted it in another article.
https://socratic.org/questions/what-is-the-recurrence-formula-for-l-n-l-n-is-the-number-of-strings-a-1-a-2-a-n--2
The result is `L_1=3, L_2=7, L_(n+1)=2L_n+L_(n-1)" "(n>=2)`

[Part 4] This is the main section of mathematical induction. (`n=k->n=k+1`)

Suppose that `L_k=K_k+1/3K_(k-1)` is true for a certain `k>=2`.
Using the recurrences in Part 2 and Part 3:
`L_(k+1)=2L_k+L_(k-1)`
`=2(K_k+1/3K_(k-1))+(K_(k-1)+1/3K_(k-2))`
`=2K_k+5/3K_(k-1)+1/3K_(k-2)`

`K_(k+1)+1/3K_k=(2K_n+K_(n-1))+1/3(2K_(n-1)+K_(n-2))`
`=2K_k+5/3K_(k-1)+1/3K_(k-2)`

We reached `L_(k+1)=K_(k+1)+1/3K_(k)` at last!

[Part 1] and [Part 4] ensure that the proof is completed.