# Recursion question I think?

The new cases I am getting are:

Case 1: CDXXXXXX

Case A: DCDXXXXX

Case 2: DDCDXXXX

Case B: DDDCDXXX

Case 3: DDDDCDXX

Case C: DDDDDCDX

Case 4: DDDDDDCD

Case D: DDDDDDDC

Where D can be A or B. and X can be A, B, or C. So, D has 2 possibilities and X has 3 possibilities. We can find the total strings by the following calculations:

2*(3^6) = 1458
(2^2)*(3^5) = 972
(2^3)*(3^4) = 648
(2^4)*(3^3) = 432
(2^5)*(3^2) = 288
(2^6)*3 = 192
(2^6)*3 = 192

Summing them up this time we get:
1458+972+648+432+288+192+192 = 4182

6561 - 4182 = 2379
We get 2379 valid strings this time.

f(n) = 2^n + 3^n
This is the pattern rule Wolframalpha gave me for 2,5,13,35,97,275 which are the strings for 1 to 6 digits . So it turns out it wasn't a recursion question I guess... But still Im not sure how we get this. I have to explain my answer to my teacher so how would I show my work?

f(n) = 2^n + 3^n where the 8 letter string is when n = 7
So what would be more correct is
f(n) = 2^(n-1) + 3^(n-1)

Last edited:
Im confused again... for length 4 someone told me they only got 33 possibilities.
they calculated only the valid strings
DDDD
CCDD
DCCD
DDCC
CCCD
DCCC
CCCC

Problem is I don't see how its wrong so now I'm second guessing myself

No, this answer is not right. I don't understand your reasoning in post # 10: you looks at some special cases, then list a bunch of numbers in the end. Where do those numbers come from?
Actually, I am not sure. The number I got on my computer at the time of my previous post is wrong: I calculated all cases where every C is isolated.

Actually, I am not sure. The number I got on my computer at the time of my previous post is wrong: I calculated all cases where every C is isolated.
I got [imath]3280[/imath] ways of isolated C's based on a pattern depends on 2-letter and 3-letter strings!

This is why I asked for the final solution, so that we can compare our answers with it. If we are wrong we can improve it more.

f(n) = 2^n + 3^n
This is the pattern rule Wolframalpha gave me for 2,5,13,35,97,275 which are the strings for 1 to 6 digits . So it turns out it wasn't a recursion question I guess... But still Im not sure how we get this. I have to explain my answer to my teacher so how would I show my work?

I got [imath]3280[/imath] ways of isolated C's based on a pattern depends on 2-letter and 3-letter strings!

This is why I asked for the final solution, so that we can compare our answers with it. If we are wrong we can improve it more.
I think my previous answer is somehow also wrong... Someone got 33 strings for length 4 and for them they got a recursive formula:
a(n) = 3a(n-1)-2a(n-2)+2a(n-3)

2,5,13,33,83,209,527.. this is the pattern someone gave me

Can you see how many valid strings you get for strings of length 4? Just to make sure we are on the same page

Actually, I am not sure. The number I got on my computer at the time of my previous post is wrong: I calculated all cases where every C is isolated.
I get a number between 3000 and 3500 by subtracting arrangements with isolated C's from the total, which I think is what you are saying.
I got [imath]3280[/imath] ways of isolated C's based on a pattern depends on 2-letter and 3-letter strings!

This is why I asked for the final solution, so that we can compare our answers with it. If we are wrong we can improve it more.
My answer (which I haven't yet double-checked) is different.

2,5,13,33,83,209,527.. this is the pattern someone gave me

Can you see how many valid strings you get for strings of length 4? Just to make sure we are on the same page
[imath]41[/imath]

I get a number between 3000 and 3500 by subtracting arrangements with isolated C's from the total, which I think is what you are saying.

My answer (which I haven't yet double-checked) is different.
Probably, you are the correct one professor Dave because I trust on your calculations on these type of questions!

[imath]41[/imath]
I think there is a mistake , I brute forced that question and only got 33 strings

I get a number between 3000 and 3500 by subtracting arrangements with isolated C's from the total, which I think is what you are saying.

My answer (which I haven't yet double-checked) is different.
Is it 3351?

[imath]41[/imath]
I get 21 ... but about to check it.

No, that's clearly wrong. I'll go back to my calculations.

I think there is a mistake , I brute forced that question and only got 33 strings
By valid strings I meant [imath]AAAA[/imath] and [imath]ACCA[/imath] for example are included.

Yes I included those
By valid strings I meant [imath]AAAA[/imath] and [imath]ACCA[/imath] for example are included.
Here is the list I tested
AAAA
AAAB
AABA"
AABB
AACC
ABAA
ABAB
ABBA
ABBB
ABCC
ACCA
ACCB
ACCC
BAAA
BAAB
BABA
BABB
BACC
BBAA
BBAB
BBBA
BBBB
BBCC
BCCA
BCCB
BCCC
CCAA
CCAB
CCBA
CCBB
CCCA
CCCB
CCCC

Yes I included those

Here is the list I tested
AAAA
AAAB
AABA"
AABB
AACC
ABAA
ABAB
ABBA
ABBB
ABCC
ACCA
ACCB
ACCC
BAAA
BAAB
BABA
BABB
BACC
BBAA
BBAB
BBBA
BBBB
BBCC
BCCA
BCCB
BCCC
CCAA
CCAB
CCBA
CCBB
CCCA
CCCB
CCCC
This means that there are [imath]81 - 33 = 48[/imath] invalid strings while my not well developed formula gives me [imath]40[/imath]. I am wondering if professor Dave has the same result as this!

This means that there are [imath]81 - 33 = 48[/imath] invalid strings while my not well developed formula gives me [imath]40[/imath]. I am wondering if professor Dave has the same result as this!
I also get 33 valid strings.

I think I found a way to use recursion. Not super elegant, but good enough to allow computing the answer by hand. Using the same notation as @5ugxr used in post #5 we can break all sequences of length [imath]n[/imath] into the following classes (each class starts with 0 or 2+ C's followed by D followed by a good string of smaller length, and the class is named according to the position of the first non-C):

 Class 0 DX..X First non-C at position 0, the rest of the string is good. Class 2 CCDX...X First non-C at position 2, the rest of the string is good. Class 3 CCCDX..X Class 4 CCCCDX...X ..... ...... Class [imath]n-1[/imath] CCC...CD All C's except the last Class [imath]n[/imath] CCC...C All C's

In each class the X's following D must form a good sequence. This means that the number [imath]F_n[/imath] of good classes of length [imath]n[/imath] can be expressed through [imath]F_k[/imath] for [imath]k<n[/imath]. I still could not find a nice expression for [imath]F_n[/imath], but I could compute [imath]F_8[/imath] using recursion.

Someone on discord found the recursive formula a(n) = 3a(n-1)-2a(n-2)+2a(n-3)
Their explaination was:

take all the valid strings of length n-1 and append an A,B or C at the end in 3a(n-1) ways.the ones ending in A,B are valid, but some of the ones ending in C aren't, namely when the (n-1)-st digit is A or B. there are 2a(n-2) of these, since to construct them, you start with a valid string of length n-2 and append AC or BC at the end. moreover, there are those valid strings ending in ACC or BCC which are not obtained in the preceding way (the first n-1 digits of these strings are not themselves valid), and there are 2a(n-3) of these (edited)

wondering if the reasoning is right