wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> general problem-solving / chatting / whatever >> How do I prove this (Fibonacci vs powers of 2)
        
(Message started by: fiziwig on Feb 17^th, 2010, 1:12pm)

Title: How do I prove this (Fibonacci vs powers of 2)
Post by fiziwig on Feb 17^th, 2010, 1:12pm

On a totally unrelated subject I was looking at on/off patterns of lights where no two adjacent lights are permitted to be on. In other words, given all N-bit binary numbers, how many of them have no two adjacent 1's?

The pattern goes 2(of 2), 3(of 4), 5(of 8 ), 8(of 16), 13(of 32), 21(of 64), 34(of 128 ). ...

This is by observation. So how do I prove that this Fibonacci pattern goes on indefinitely?

I'm not a math wiz, but does this make sense: If I add a digit on the left of an n-digit number I still get to use all those K_n patterns when the added digit is 0, but I only get to use the K_(n-1) patterns (i.e. the K from the next previous n) if the new digit is 1 because the previous leftmost digit is adjacent to a 1 and is therefore forced to be 0. Therefore, I get K_n + k_(n-1) patterns with n+1 bits.

Is that a real proof?

thanks,
--gary

on edit: 8 in parens turned smiley on me!

Title: Re: How do I prove this (Fibonacci vs powers of 2)
Post by pex on Feb 17^th, 2010, 1:16pm

Yes, that looks like a perfectly valid induction proof (if you combine it explicitly with the observation that K₀ = 0 and K₁ = 1).

Title: Re: How do I prove this (Fibonacci vs powers of 2)
Post by fiziwig on Feb 17^th, 2010, 1:31pm

Thank you. ( BTW k_1 = 2 but I get the point. :) ) I just wanted to be sure it was true before I went ahead and based some coding on it.

Title: Re: How do I prove this (Fibonacci vs powers of 2)
Post by pex on Feb 17^th, 2010, 1:42pm

on 02/17/10 at 13:31:40, fiziwig wrote:

BTW k_1 = 2 but I get the point.

:-[
And then K₁ = 2 and K₂ = 3 form a better base case, because arguing that K₀ = 1 is not easy.

Title: Re: How do I prove this (Fibonacci vs powers of 2)
Post by SMQ on Feb 17^th, 2010, 1:52pm

on 02/17/10 at 13:42:31, pex wrote:

because arguing that K₀ = 1 is not easy.

Really? There is exactly one empty string of binary digits (in the same way there is exactly one empty set), and it does not have two adjacent ones. Seems like a fairly straightforward argument to me... ;)

--SMQ

Title: Re: How do I prove this (Fibonacci vs powers of 2)
Post by pex on Feb 17^th, 2010, 11:46pm

Hmm, yes, it's just not as intuitive (or interesting, from a practical point of view).

Title: Re: How do I prove this (Fibonacci vs powers of 2)
Post by towr on Feb 18^th, 2010, 1:09am

I guess we must have different intuitions.

Title: Re: How do I prove this (Fibonacci vs powers of 2)
Post by pex on Feb 18^th, 2010, 1:43am

Well, to be fair, K₀ = 1 agrees with my intuition as well - but I can imagine that for someone who has less mathematical experience, it is more intuitive to work with nonempty strings.

Title: Re: How do I prove this (Fibonacci vs powers of 2)
Post by Grimbal on Feb 18^th, 2010, 1:58am

That would be an "educated intuition". I bet you have stumbled over a similar question, like how many ways to arrange 0 items into n boxes and recall that. To be honest, my immediate intuition says you can do nothing with nothing. So K₀=0. Only on a second though, I think "well, actually, doing nothing counts as one way".