Talk:Zeckendorf's theorem

From Wikipedia, the free encyclopedia

  • Oppose merging. The theorem article gives the mathematical underpinning, while the coding article gives the practical persperctive. CompositeFan 17:15, 23 January 2007 (UTC)
  • Strongly oppose merging. Maybe next we should merge Differential equations and Classical mechanics, or Prime number and RSA encryption. Mathematics is more than just an organized collection of applications. --N Shar 18:18, 20 February 2007 (UTC)
  • Oppose merging. Echoing above comment about mathematical underpinning, why not merge this with the basic article on fibonacci numbers. 71.127.155.221 02:33, 28 February 2007 (UTC)SilverGirl
  • Oppose merging. Mathematics and its applications is not the same thing. Boris Bukh 21:09, 17 March 2007 (UTC)
In view of the above comments and the length of time that has passed, I have removed the "merge" tag from the article. Gandalf61 10:16, 18 March 2007 (UTC)

[edit] Proof of Zeckendorf's Theorem

I removed the following new section, headed Proof of Zeckendorf's Theorem, from the article:

Zeckendorf's Theorem can be proved by induction.
For n=1,2,3 it is clearly true, for n=4 we have 4=3+1.
Now let each n \leq k have a Zeckendorf's representation. If k + 1 is a Fibonacci Number then we're done, else there exists j such that Fj < k + 1 < Fj + 1. Now consider a = k + 1 − Fj. Since it is a < k, a has a Zeckendorf representation; moreover Fj + a < Fj + 1 then a < Fj − 1 so the Zeckendorf representation of a does not contain Fj − 1. Then k + 1 can be represented as a + Fj and we're done.

I removed this because it is not a full proof of Zeckendorf's theorem. It shows that every positive integer has a Zeckendorf representation, but in addition Zecekendorf's theorem also says that this representation is unique. This "proof" does not show uniqueness, so it only proves one half of Zeckendorf's theorem. Gandalf61 20:13, 14 August 2007 (UTC)

I copied a proof of uniqueness from PlanetMath. I hope that satisifies the complaint that the proof was not complete. Please feel free to reword it to be more in line with Wikipedia style. CompositeFan 17:20, 15 August 2007 (UTC)
I think thats only half of the uniqueness proof, the other half is proving that given any number there is only one Zeckendorf representation. --Ray andrew 18:04, 15 August 2007 (UTC)
As Ray Andrew says, the PlanetMath proof shows that two different integers cannot have the same Zeckendorf representation - but this is trivially obvious, anyway. What it does not do is show that one integer cannot have two different Zeckendorf representations - this is the difficult bit. As the "proof" is still incomplete, I have removed the section. Gandalf61 18:15, 15 August 2007 (UTC)
So if it's missing one bit, we delete the whole goddamn thing, right? Does that make sense for Wikipedia? Do we also go around deleting stubs because they're incomplete? Knodeltheory 19:26, 15 August 2007 (UTC)

The proof of the missing bit is not too hard, it comes down to showing that any sum of non consecutive Fibonacci numbers is strictly less then the "next largest" Fibonacci number (ie, find the largest Fibonacci number in the sum and use the next one). One can prove this by induction on the largest Fibonacci number in the sum. The base case is trivial. And to for induction if you assume it is true for sums with largest term less then or equal to $F_{n-1}$ then in a sum $S$ with largest term $F_n$ the sum of the other terms is $S-F_n$ and consists of non consecutive Fibonacci numbers less then or equal to $F_{n-2}$ thus by induction, $S-F_n < F_{n-1}$ so $S<F_{n-1}+F_n=F_{n+1}$. Please excuse the tex formating, and feel free to write this up nicely in wiki style with all the details filled in. --Ray andrew 20:06, 15 August 2007 (UTC)

Yes, I see where you go from there. If there is a source for this uniqueness proof then it could go into the article. Does anyone have a source ? Gandalf61 11:21, 16 August 2007 (UTC)

[edit] Reason for expansion needed message (sectstub)

As stated elsewhere on this talk page, the proof section is incomplete because it's missing the one last bit that drives it home. It's proven that each integer has a Z. representation, and that no two integers can have the same Z. representation. The only thing that's missing is to prove that no single integer can have two Z. reps. Knodeltheory 19:33, 15 August 2007 (UTC)

I have three objections to the new "proof" section:
  1. It is not well written - but that could be fixed if it was worth the effort.
  2. It only proves the simpler (and almost trivial) half of the theorem - but maybe someone will complete it.
  3. The most serious objection is that without an independent and reliable source the "proof" section is OR - and PlanetMath is not an independent source because CompositeFan, who created the latest version of the "proof" section, also wrote the PlanetMath articles on Zeckendorf's theorem and Zeckendorf representations.
But I am happy to wait a few days to see if someone can complete and source this section. Gandalf61 19:47, 15 August 2007 (UTC)
  1. All the misplaced capitalization, crunched-up mathematical expressions, etc. were horrible. But thanks to the Wikipedia model, I can fix that. It's a short section, so I don't mind fixing it.
  2. Maybe for us who know about this is trivial. Those who don't know might appreciate being walked through the simpler first half, and it might even help them understand the tougher second half.
  3. Yes, she did, but didn't PrimeFan write the proofs over there? Since PrimeFan is also a Wikipedia editor, this objection still stands.
From MathWorld, I've identified three volumes of Fib. Quart. with articles on Zeckendorf's theorem: 2, 10 and 34. I can only find 34 right now, it has an article on p. 147 by Grabner, Tichy et al on a couple of rather advanced conjectures on the LSD of a Zeckendorf representation. I'm guessing 2 proves the more elementary things. Anton Mravcek 20:44, 15 August 2007 (UTC)
Okay - if people find the induction proof of the existence half of the theorem (the first paragraph of the "proof" section) useful then I have no objection to keeping it in the article, although I think it could be simplified. And Ray Andrew has outlined an approach to proving the uniqueness half of the theorem above - if we can find a source to show this approach is not OR, then that can be included as well. But can we please agrree to remove the part that shows that two different integers cannot have the same Zeckendorf representation ? All this says is that a sum cannot have two different totals, which really is trivial. I think this paragraph has only crept in because of a misunderstanding of what "unique" meant in this theorem. Gandalf61 11:50, 16 August 2007 (UTC)
I agree that the simple half of the uniqueness proof should be vastly simplified (or even ignored). You could use a one line prof, for instance: Clearly a number is uniquely determined by its Zeckendorf representation. Do we really need sources for these proofs? Because I really did just come up with the outline proof for the other half after thinking about it for a bit (but I am very familiar with the topic as my thesis involved the Zeckendorf representation). I assume though that that is how the original proof goes (if not it should be because its damn straight forward). I might have some free time next week to make the proof look nice, if someone does not do it first. --Ray andrew 13:06, 16 August 2007 (UTC)
I think that the spirit of the no OR rules is so that someone doesn't publish some genius proof here and then they get angry because their proof is out in public. But who would honestly cry if their proof that 1 + 1 = 2 got published here rather in a journal? Of course I'm not saying Ray andrew's proof is that simple, but compared to Wiles' proof of Fermat's last theorem, it looks more like the proof of 1 + 1. CompositeFan 19:27, 18 August 2007 (UTC)
P.S. The linked Springer article hints at the proof. It cites D.E. Daykin, "Representation of natural numbers as sums of generalised Fibonacci numbers" J. London Math. Soc. , 35 (1960) pp. 143–160 to back up that only Fibonacci numbers work for this purpose, but I have a hunch that it might also say something about what we want here. CompositeFan 19:42, 18 August 2007 (UTC)
Still no source for the uniqueness proof, but I have decided that an unsourced proof is better than a gaping hole, so I have added an outline of the uniqueness proof to the article, following Ray Andrew's approach. Gandalf61 10:37, 28 August 2007 (UTC)