ADVANCED ITERATIVE PROCESS $20$ POINTS

This is like a Fibonacci process but there are two differences:

The Fibonacci numbers need not be involved.

There are two intertwined sequences that depend on one another.

This problem involves considering strings of base $3$ digits $-$ i$.$e$.$ strings that use only the symbols $0,1,$ and $2.$ The word strings in emphasized here since there are not numbers. We care about string length and leading zeroes matter. For example, $012$ and $12$ are not equivalent $-$ the first is a string of length $3$ and the second is a string of length $2.$ Given a fixed length $n2$ we are interested in counting and possibly listing all strings of length $n$ which satisfy both of the following requirements:

All strings end in $22.$

The ending of $22$ is the first time that consecutive $2$ s have appeared.

Thus for example the strings $012$ and $22022$ are both invalid. The first doesn't end properly $($thus violating the first bullet$)$ and the second violates the second bullet by having two consecutive $2s$ before the end. $($Note that $222$ would also violate the second bullet$).$ For $n=2,3,4,$dots we define two sequences as follows:

$U_n$ is the number of valid strings of length $n$ which start with a $2.$

$K_n$ is the total number of valid strings of length $n.$

$($A$)5$ POINTS List the valid strings of lengths $2,3,$ and $4$ and determine $U_2,U_3,U_4,K_2,K_3,K_4.$

$($B$)10$ POINTS Find formulas for both $U_{n+1}$ and $K_{n+1}$ in terms of the collection of $U_p$ and $K_p$ with $pn.$ Note that we are not saying that all these values will be needed! Fully explain why your formula is correct!

$($C$)5$ POINTS How many valid strings of length $21$ are there? Explain how you computed this!