How many ternary strings of length n contain two consecutive symbols that are the same?

A ternary string is a string that is composed of at most three different symbols. 021102 is a ternary string over {0, 1, 2}, and acbabbc is a ternary string over {a, b, c}.





How many strings of length n contain consecutive symbols that are the same?





Examples: abcabc does not qualify, because there are no repeated letters. abccba does, because c repeats itself consecutively.

How many ternary strings of length n contain two consecutive symbols that are the same?
I'll begin by determining how many ternary strings of length n *don't* contain consecutive symbols. I'll use induction:





length 1: 3 strings


length 2: 3*2 strings (each length 1 string has 2 possible suffixes that work)


length 3: 3*2*2 strings (2 suffixes for each length 2 string)


...


length n: 3 * (2^(n-1)) strings





The total number of length n ternary strings is 3^n. So the number containing consecutive symbols that are the same is


3^n - (3 * (2^(n-1))
Reply:There is a recurrence relation solution here:





http://ocw.mit.edu/NR/rdonlyre...





If I were motivated, I'd verify that the proposed solution fits the recurrence relation. Report It

Reply:countable number of strings can qualify for this.
Reply:Number of strings you want+Number of strings you don't want=all strings


therefore,


Number of strings you want=all strings-number of strings you don't want.





to find the number of all strings, there are 3 choices for the first symbol, 3 for the second, etc. so it's 3*3*3*...*3=3^n.





to find the number of strings you don't want, think of it this way, the first symbol could be anything, so that's 3 possibilities. For each of those choices of the first one, there are 2 other symbols that the second symbol could be. For each of those choices of the second one, there's 2 new choices for the third symbol (to make it different from the preceding symbol) etc. Therefore it's 3*2*2*2*...*2=3*2^(n-1)





Therefore, the number you want is 3^n-3*2^(n-1)
Reply:Do you mean just one pair, or at least one pair?