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 ?
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.