Talk:Zeckendorf's theorem

• 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)

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 $F_{j}<k+1<F_{j+1}$. Now consider $a=k+1-F_{j}$. Since it is $a<k$, a has $a$ Zeckendorf representation; moreover $F_{j}+a<F_{j+1}$ then $a<F_{j-1}$ so the Zeckendorf representation of $a$ does not contain $F_{j-1}$. Then $k+1$ can be represented as $a+F_{j}$ 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)

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)

New concerns about proof

I'm concerned about the bit that reads

The first part of Zeckendorf's theorem (existence) can be proved by induction. ..... Then k + 1 can be represented as $a+F_{j}$. Moreover, it is obvious that each Zeckendorf representation corresponds to only one integer.

It is possible that $a$ and $F_{j}$ may have '1' in the same place or in adjacent places. The proof can be patched along the following lines: do people agree?

• If they are in the same place i.e. there is repeated $F_{l}$ in the representation for some l, then this number itself has a Z-representation. (*)
  • If they are in adjacent places, the representation ....0110... can be replaced by .....0001.. because the sum of two Fibs is the next Fib. (**)

However, the result of doing (*) or (**) may create a further problem, in which case (*) or (**) can be repeated ... (I suppose)

Am I right? Would anybody like to write this up in full? Johnbibby (talk) 07:55, 18 June 2008 (UTC)

$a$ and $F_{j}$ cannot have '1' in the same place or in adjacent places because $a<F_{j-1}$. so the highest Fibonacci number that can possibly be in the Zeckendorf representation of $a$ is $F_{j-2}$. Gandalf61 (talk) 07:48, 21 June 2008 (UTC)

unique?

Note: F-series: f1=0, f2=1, f3=1, f4=2, f5=3,...; 3 is a F-number, but also 3=1+2=f2+f4, the sum of 2 not succeeding F-numbers.??Nijdam (talk) 21:29, 16 October 2011 (UTC)

Alternative existence proof

I am considering providing the following proof by induction of the existence part of the theorem:-

Base step: clearly, 1 has a representation (or, alternatively, we could start at 0).

Induction:-

Suppose k has a representation; clearly it must be of the form 1...10 or 1...01 or 1...00. Clearly, if we temporarily relax the requirement that there be no consecutive 1s in the representation of k+1, k+1 can be represented as 1...11 or 1...10 or 1...01 respectively. Now consider the effect of applying the following repair algorithm to restore the requirement: halt if there are no consecutive 1s; find the leftmost consecutive pair of 1s; clearly this has a 0 to the left of it (possibly implied, if the representation of k+1 currently begins with a pair of 1s), so the leftmost consecutive pair of 1s falls within a triple 011; replace this triple with the triple 100; and repeat. Clearly, each iteration maintains the sum of the representation, by the definition of the Fibonacci numbers, so it remains a representation of k+1. Clearly, each iteration reduces the total number of 1s by 1, and so the iteration must terminate as there are only finitely many 1s to begin with. But clearly the iteration can only terminate on a representation with no consecutive 1s (which must be, as shown, a representation of k+1), so there must be a representation of k+1 with no consecutive 1s (and we have constructed it from that of k). Q.E.D.

Would this be an acceptable contribution, perhaps after editing to tidy it up? Maybe it would read more easily if it were rewritten as a proof by infinite descent? PMLawrence (talk) 08:08, 26 December 2013 (UTC)

I don't think this is as clear or as concise as the existence proof that is already in the article. I think it is only worth including a second existence proof if thus one has a reliable source. Gandalf61 (talk) 09:31, 26 December 2013 (UTC)

On the first point, that's why I was wondering if this would read better if presented in its proof by infinite descent version. Also, judging by such proofs as the irrationality of the square root of 2, there is merit in presenting variant proofs using different approaches, and not just presenting "best" proofs, precisely because the approaches are different - readers can learn different "meta" stuff from each approach. As for sourcing this proof, isn't it of the nature of the beast that a mathematical proof provides its own authority, unlike (say) an assertion about current events? After all, there isn't any such source given for any of the current proof (yes, that has been flagged here - though not for those proofs at the square root of 2 that are unsourced - but nobody has followed that up in over a year, and at least having a different variant would buttress the current situation). PMLawrence (talk) 11:28, 26 December 2013 (UTC)