Recurrence Relation Models

[corrion]

Hey all,

I've been working on my homework for the past few hours, and I got stuck on one of the questions:

A) Find a recurrence relation for the number of n-digit binary sequences with no pair of consecutive 1s.
B) Repeat for n-digit ternary sequences.
C) Repeat for n-digit ternary sequences with no consecutive 1s or consecutive 2s.

For part A, I figured the recurrence relation is a[sub:2u0r5agx]n[/sub:2u0r5agx] = a[sub:2u0r5agx]n-1[/sub:2u0r5agx] + (a[sub:2u0r5agx]n-1[/sub:2u0r5agx] - a[sub:2u0r5agx]n-2[/sub:2u0r5agx]), but I can't be sure that for part B, the relation for a ternary sequence is a[sub:2u0r5agx]n[/sub:2u0r5agx] = a[sub:2u0r5agx]n-1[/sub:2u0r5agx] + (a[sub:2u0r5agx]n-1[/sub:2u0r5agx] - a[sub:2u0r5agx]n-2[/sub:2u0r5agx]) + a[sub:2u0r5agx]n-1[/sub:2u0r5agx]. Is my logic correct? I have no idea how to approach part C, so a bit of guidance there would be great.

Thanks.

 

[soroban]

Hello, corrion!

I have a conjecture for part (A) . . .

A) Find a recurrence relation for the number of n-digit binary sequences with no pair of consecutive 1's.

\(\displaystyle \text{I used }brute\:f\!orce\text{ and cranked them out up to }n = 6.\)

. . \(\displaystyle \begin{array}{c|cc} n & a(n) \\ \hline \\ 1 & 1 \\ \\ 2 & 3 \\ & & (1+3)+1 \,=\,5 \\3 & 5 \\ & & (3+5)-1 \,=\,7 \\ 4 & 7 \\ & & (5+7) + 1 \,=\,13 \\ 5& 13 \\ & & (7+13)-1\,=\,19\\ 6 & 19 \end{array}\)


\(\displaystyle \text{I think the recurrence is: }\;a(n) \;=\;a(n-1) + a(n-2) + (-1)^{n+1}\)

 

[corrion]

Ah, I get it now. I also figured out that your answer is the same as 2[sup:3r4dscp4]n[/sup:3r4dscp4] - n - 1. Thanks for the response!

 

[pka]

In the pervious post there is some undercounting going on.
In the first place, \(\displaystyle a_1 = 2\) because the strings are {0,1}.
\(\displaystyle a_2 = 3\)
Also, \(\displaystyle a_4 = 8\) because the strings are {0000,1000,0100,0010,0001,1010,1001,0101}.

In general \(\displaystyle a_n = a_{n-1} + a_{n-2}\).
Because any string in \(\displaystyle a_n\) either begins with a 0, in which case the rest of the string belongs to \(\displaystyle a_{n-1}\); or begins with a 10, in which case the rest of the string belongs to \(\displaystyle a_{n-2}\).