I found a nice explanation (from some other site) on how to get this formula T(n) = fib(n+2).
Consider the set of all binary numbers of length n that end with 0. The first n-1 positions can be anything (0 or 1). So if we take the set of all binary numbers of length n-1 and append 0 to each of its element we get this set. Therefore size of this set is T(n-1). Consider the set of all binary numbers of length n that end with 1. Now, the (n-1)th position has to be 0 (because of the constraint). But there is no constraint on the first n-2 positions. So if we take the set of all binary numbers of length n-2 and append 01 to each of its element we get this set. Therefore size of this set is T(n-2). Therefore T(n) = T(n-1) + T(n-2). Since T(1) = 2 and T(2) = 3 we get T(n) = fib(n+2). -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
