# A054770

karttu at megabaud.fi karttu at megabaud.fi
Wed Jun 7 01:27:16 CEST 2000

> ID Number: A054770
> Sequence:  2,6,9,13,17,20,24,27,31,35,38,42,46,49,53,56,60,64,67,71,74,
>            78,82,85,89,93,96,100,103,107,111,114,118,122,125,129,132,
>            136,140,143,147,150,154,158,161,165,169,172,176,179,183,187,
>            190,194,197,201,205,208,212
> Name:      Not the sum of distinct Lucas numbers 1,3,4,7,11 ... (A000204).
>
> _________________________________________________________________________
>
> Conjecture by dww (= David W. Wilson):
> a_n = [((5+sqrt(5))/2)n]-1
> (= [(phi + 2)*n] - 1, where phi is the golden ratio (1+sqrt(5))/2)
>
> Proof or disproof ?

Antreas,

I think that basically you have forgotten the zeroth Lucas number 2,
present in the alternative entry of the Lucas sequence in EIS:

ID Number: A000032 (Formerly M0155)
Sequence:  2,1,3,4,7,11,18,29,47,76,123,199,322,521,843,1364,2207,3571,
5778,9349,15127,24476,39603,64079,103682,167761,271443,
439204,710647,1149851,1860498,3010349,4870847,7881196,
12752043,20633239,33385282
Name:      Lucas numbers (beginning at 2): L(n) = L(n-1) + L(n-2).
Maple:     with(combinat): A000032:=n->fibonacci(n+1)+fibonacci(n-1);
Keywords:  nonn,nice,easy
Offset:    0
Author(s): njas

With that 2 present, I think you could represent all integers
as a sum of distinct Lucas numbers.

See about the Wythoff Array, the Zeckendorf Expansion, etc,
starting from:

http://www.research.att.com/~njas/sequences/classic.html

and note that that L(n) = F(n-1)+F(n+1).

Look especially at the sequences:

ID Number: A003231 (Formerly M2618)
Sequence:  3,7,10,14,18,21,25,28,32,36,39,43,47,50,54,57,61,65,68,72,
75,79,83,86,90,94,97,101,104,108,112,115,119,123,126,130,
133,137,141,144,148
Name:      Related to a Beatty sequence.
References L. Carlitz, R. Scoville and T. Vaughan, Some arithmetic functions
related to Fibonacci numbers, Fib. Quart., 11 (1973), 337-386.
Keywords:  nonn
Offset:    1
Author(s): njas

ID Number: A000201 (Formerly M2322 and N0917)
Sequence:  1,3,4,6,8,9,11,12,14,16,17,19,21,22,24,25,27,29,30,32,33,35,
37,38,40,42,43,45,46,48,50,51,53,55,56,58,59,61,63,64,66,67,
69,71,72,74,76,77,79,80,82,84,85,87,88,90,92,93,95,97,98,100
Name:      Lower Wythoff sequence (a Beatty sequence): [ n*tau ].
Offset:    1
Author(s): njas

ID Number: A022342
Sequence:  0,2,3,5,7,8,10,11,13,15,16,18,20,21,23,24,26,28,29,31,32,34,
36,37,39,41,42,44,45,47,49,50,52,54,55,57,58,60,62,63,65,66,
68,70,71,73,75,76,78,79,81,83,84,86,87,89,91,92,94,96,97,99,
100,102,104,105
Name:      Integers with "even" Zeckendorf expansions (don't end with ...+F1 =
...+1); also, apart from 1st term, a(n) = Fibonacci successor to n-1.
Formula:   a(n) = [ n tau^2 ] - n - 1; or [ n tau ] -1.
Example:   The succesors to 1, 2, 3, 4=3+1 are 2, 3, 5, 7=5+2.
Keywords:  nonn,nice,easy
Offset:    1
Author(s): Marc Le Brun (mlb at well.com)

(Here tau = phi = Golden ratio)

So, I guess that indeed A054770[n] = [(tau + 2)*n] -1 = [tau*n]+2n - 1
thus A054770[n] = A003231[n]-1, and
also A003231[n] = A000201[n]+2n = A022342[n]+1+2n

Also, Edouard Zeckendorf's original article mentioned in
the footnote mentioned of Eric's page:

http://mathworld.wolfram.com/ZeckendorfRepresentation.html

Zeckendorf, E. ``Représentation des nombres naturels par
une somme des nombres de Fibonacci ou de nombres de Lucas.''
Bull. Soc. Roy. Sci. Liège 41, 179-182, 1972.

would be an interesting to read, because of that "ou de nombres de Lucas"
part. (Does anybody have a copy?)

Zeckendorf Expansion (with Fibonacci numbers) gives all
the binary sequences with no adjacent 1's in turn.
Convert these back to binary, and you will see:

ID Number: A003714
Sequence:  0,1,2,4,5,8,9,10,16,17,18,20,21,32,33,34,36,37,40,41,42,64,
65,66,68,69,72,73,74,80,81,82,84,85,128,129,130,132,133,136,
137,138,144,145,146,148,149,160,161,162,164,165,168,169,170,
256,257,258,260
Name:      Fibbinary numbers: if n = F_i1+F_i2+...+F_ik is the Zeckendorf
representation of n (i.e. write n in Fibonacci number system) then a(n)
= 2^{i1-1}+2^{i2-1}+...+2^{ik-1}.
Keywords:  nonn,base,nice
Offset:    0
Author(s): njas

<NEIL, shouldn't this be:
... then a(n) = 2^{i1-2}+2^{i2-2}+...+2^{ik-2}.
because Zeckendorf Expansion never uses F(1) because F(2) is also 1,
if we use the indexing F(0) = 0, F(1) = 1, F(2) = 1, F(3) = 2, etc.>

However, if I try to construct a Lucas number system,
I'll run into difficulties:

...,76,47,29,18,11, 7, 4, 3, 1, 2
0, 0, 0, 0, 0 = 0
1, 0 = 1
0, 1 = 2
1, 0, 0 = 3
1, 0, 0, 0 = 4
0, 1, 0, 1 = 5 = but also 1, 0, 1, 0 (4+1)

so we don't have anymore a unique representation of each integer
as a sum of distinct non-consecutive Lucas numbers.

It doesn't help if I switch the places 1 and 2, because then:

4 = 1000 (i.e. 4), but also 101 (i.e. 3+1).

In any case, you should be able to construct a proof with this material,
and with few of the identities given in
http://mathworld.wolfram.com/FibonacciNumber.html

Terveisin,
Gia sou,
Salut

Antti Karttunen
E-mail: karttu at megabaud.fi