# Question #3ecb0

Oct 3, 2017

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: $\left(0\right) \left(1\right) \left(2\right)$.

${K}_{2} = 6$ because the 2-words string from the set $\left\{0 , 1 , 2\right\}$ in which the two maximum blocks have single word are
$\left(0 , 1\right) \left(0 , 2\right) \left(1 , 0\right) \left(1 , 2\right) \left(2 , 0\right) \left(2 , 1\right)$.

${L}_{2} = 7$, as all strings without adjacent 0 and 2 are
$\left(0 , 0\right) , \left(0 , 1\right) , \left(1 , 0\right) , \left(1 , 1\right) , \left(1 , 2\right) , \left(2 , 1\right) , \left(2 , 2\right)$

Thus, ${L}_{2} = {K}_{2} + \frac{1}{3} {K}_{1}$ is true.

[Part 2]
What we need to do is to find a recurrence for ${K}_{n}$ $\left(n \ge 3\right)$ .

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} = 2 {K}_{n - 1} + {K}_{n - 2} \text{ } \left(n \ge 3\right)$

[Part3] Then we are going to find the recurrence of ${L}_{n}$ $\left(n \ge 3\right)$ .
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} = 2 {L}_{n} + {L}_{n - 1} \text{ } \left(n \ge 2\right)$

[Part 4] This is the main section of mathematical induction. ($n = k \to n = k + 1$)

Suppose that ${L}_{k} = {K}_{k} + \frac{1}{3} {K}_{k - 1}$ is true for a certain $k \ge 2$.
Using the recurrences in Part 2 and Part 3:
${L}_{k + 1} = 2 {L}_{k} + {L}_{k - 1}$
$= 2 \left({K}_{k} + \frac{1}{3} {K}_{k - 1}\right) + \left({K}_{k - 1} + \frac{1}{3} {K}_{k - 2}\right)$
$= 2 {K}_{k} + \frac{5}{3} {K}_{k - 1} + \frac{1}{3} {K}_{k - 2}$

${K}_{k + 1} + \frac{1}{3} {K}_{k} = \left(2 {K}_{n} + {K}_{n - 1}\right) + \frac{1}{3} \left(2 {K}_{n - 1} + {K}_{n - 2}\right)$
$= 2 {K}_{k} + \frac{5}{3} {K}_{k - 1} + \frac{1}{3} {K}_{k - 2}$

We reached ${L}_{k + 1} = {K}_{k + 1} + \frac{1}{3} {K}_{k}$ at last!

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