Author |
Topic: How do I prove this (Fibonacci vs powers of 2) (Read 1053 times) |
|
fiziwig
Junior Member
Posts: 78
|
 |
How do I prove this (Fibonacci vs powers of 2)
« on: Feb 17th, 2010, 1:12pm » |
 Quote  Modify
|
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!
|
| « Last Edit: Feb 17th, 2010, 1:14pm by fiziwig » |
 IP Logged |
|
|
|
pex
Uberpuzzler
Gender: 
Posts: 880
|
|
Re: How do I prove this (Fibonacci vs powers of 2)
« Reply #1 on: Feb 17th, 2010, 1:16pm » |
Quote Modify
|
Yes, that looks like a perfectly valid induction proof (if you combine it explicitly with the observation that K0 = 0 and K1 = 1).
|
|
IP Logged |
|
|
|
fiziwig
Junior Member
Posts: 78
|
|
Re: How do I prove this (Fibonacci vs powers of 2)
« Reply #2 on: Feb 17th, 2010, 1:31pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: How do I prove this (Fibonacci vs powers of 2)
« Reply #3 on: Feb 17th, 2010, 1:42pm » |
Quote Modify
|
on Feb 17th, 2010, 1:31pm, fiziwig wrote:| BTW k_1 = 2 but I get the point. |
|
And then K1 = 2 and K2 = 3 form a better base case, because arguing that K0 = 1 is not easy.
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: How do I prove this (Fibonacci vs powers of 2)
« Reply #4 on: Feb 17th, 2010, 1:52pm » |
Quote Modify
|
on Feb 17th, 2010, 1:42pm, pex wrote:| because arguing that K0 = 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
|
|
IP Logged |
--SMQ
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: How do I prove this (Fibonacci vs powers of 2)
« Reply #5 on: Feb 17th, 2010, 11:46pm » |
Quote Modify
|
Hmm, yes, it's just not as intuitive (or interesting, from a practical point of view).
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: How do I prove this (Fibonacci vs powers of 2)
« Reply #6 on: Feb 18th, 2010, 1:09am » |
Quote Modify
|
I guess we must have different intuitions.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: How do I prove this (Fibonacci vs powers of 2)
« Reply #7 on: Feb 18th, 2010, 1:43am » |
Quote Modify
|
Well, to be fair, K0 = 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.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: How do I prove this (Fibonacci vs powers of 2)
« Reply #8 on: Feb 18th, 2010, 1:58am » |
Quote Modify
|
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 K0=0. Only on a second though, I think "well, actually, doing nothing counts as one way".
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print