i guess we are saying the same thing. On Wed, Jun 9, 2010 at 1:29 AM, Senthilnathan Maadasamy < [email protected]> wrote:
> 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]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says "Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up." Man bursts into tears. Says "But, doctor...I am Pagliacci." -- 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.
