Representations found by the greedy algorithm

[Max A.]

On 12/19/06, Alec Mihailovs <alec at mihailovs.com> wrote:
> From: "Kimberling, Clark" <ck6 at evansville.edu>
>
> > Suppose x=(1+sqrt(5))/2.  The greedy algorithm finds that every positive
> > integer N has a representation
> >
> > N = c0/x + c1/x^2 + c2/x^3 + ...
> >
> > Can someone prove that c1, c2, c3, ... are all 0 except for finitely
> > many 1's?
> >
> > Examples:
> >
> > 4 = 6/x + 1/x^3 + 1/x^6
> >
> > 5 = 8/x + 1/x^6
> >
> > 6 = 9/x + 1/x^2 + 1/x^6
> >
> > 22 = 35/x + 1/x^3 + 1/x^5 + 1/x^7 + 1/x^10.
>
> Such a representation is not unique.

It is unique as soon as there are no two consecutive coefficients
(i.e., c(k) and c(k+1) for some k) both equal to 1.
And the greedy algorithm finds exactly such representations.

Max