3

I am looking for a number of ternary strings of length n, that dont contain consecutive zeroes. This was already asked, but I am NOT looking for reccurence relation. Instead, I found this formula, which produces the same result :

$$ \frac{\sqrt3 + 2}{2\sqrt3}(1+\sqrt3)^n + \frac{\sqrt3-2}{2\sqrt3}*(1-\sqrt3)^n $$

Can anyone explain me, how was this formula found out ?

molnarriso
  • 31

1 Answers1

2

Unfortunately for you, I will have to resort to recurrence relations to answer this. (Perhaps someone else knows another way.)

The recurrence relation for this number (I know you don't want it, but you can find it here Recurrence relation for the number of ternary strings containing 2 consecutive zeros vs not containing) is a constant-coefficient linear recurrence relation. Constant-coefficient linear recurrence relations can be solved via solving a polynomial equation; see http://en.wikipedia.org/wiki/Recurrence_relation#Linear_homogeneous_recurrence_relations_with_constant_coefficients.

The same method will also give you formulas for things like the Fibonacci numbers.

Community
  • 1
Gyu Eun Lee
  • 18,793
  • It could technically be proven directly via induction, but i can almost guarantee the numbers involved would have been found from those polynomials from the recurrence relation first. – JMoravitz Dec 11 '14 at 04:04
  • as I have said, the queston you are answering has been aswered many times here. I am looking for the other way. I also know about multiplying by n-th power of matrix, which is also not a subject of this question. – molnarriso Dec 11 '14 at 04:06