# Question #3ecb0

##### 1 Answer

We can prove this using mathematical induction.

The answer got too lengthy and there will be some improvement.

#### Explanation:

[**Part 1**] Base case(

To show that the recurrence is true for

Thus,

[**Part 2**]

What we need to do is to find a recurrence for

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

[**Part3**] Then we are going to find the recurrence of

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

[**Part 4**] This is the main section of mathematical induction. (

Suppose that

Using the recurrences in Part 2 and Part 3:

We reached

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