How many n digits base $3$ numbers do exist such that they never contain pattern '$20$'? (first find a recurrence relation)
Asked
Active
Viewed 72 times
0
-
1What have you tried? Can you list out the number of cases for small values of $n$? Can you guess what the recurrence is? – Calvin Lin Feb 04 '14 at 22:13
-
trying to guess is used for find closed form of sequence, but in this case i want a recurrence relation. – Emad Feb 04 '14 at 22:16
-
Yes, but that offers you a way to figure out what the recurrence relation is, which makes proving it easier (if you have no idea how to approach it). – Calvin Lin Feb 04 '14 at 22:19
-
Can you have numbers with leading zeroes? Like $0000112_3$? – John Feb 04 '14 at 22:19
-
@John That doesn't really matter, since you can subtract those cases away after you have done the calculation. – Calvin Lin Feb 04 '14 at 22:20
-
@John Yes we can! – Emad Feb 04 '14 at 22:20
1 Answers
2
Hint: Let $a(n)$ be the sequence we are looking for. Let $b(n) , c(n), d(n)$ be the number of ternary strings (and so they can start with 0) which do not contain the pattern '20', and start with 0, 1 and 2 respectively.
What equations can you get?
Claim: $a(n) = b(n) + c(n) + d(n)$.
Claim: $b(n) = c(n) = b(n-1) + c(n-1) + d(n-1)$.
Claim: $d(n) = c(n-1) + d(n-1)$.
Can you take it from here?
$b(n) = a(n-1)$, $d(n) = a(n-1) - b(n-1) = a(n-1) - a(n-2)$. Hence ...
Calvin Lin
- 68,864
-
-
@Emad Yes, and it's a short skip to the end, which you can finish out. Note that the recurrence relation could involve more terms than just 2, which is why I asked you to guess what it looks like first. It will be of the form $a(n) = Ba(n-1) + Ca(n-2) + D$, where $B, C, D$ are constants. – Calvin Lin Feb 04 '14 at 22:28
-