Representation as a Sum of Two Fibonacci Numbers

3 is an example of a number that can be represented in exactly one way as the sum of two Fibonacci numbers: 3 = 1 + 2 (order of addition is ignored). The sequence of such numbers begins: 2, 3, 5, 7, 8, 9, 11, 13, 14, 15, 18, 21, 22, 23, 24, 29, 34, 35, 36, 37,....

16 is an example of a number that can be represented in exactly two ways as the sum of two Fibonacci numbers: 16 = 3 + 13 = 8 + 8. The sequence of such numbers begins: 4, 6, 10, 16, 26, 42, 68, 110, 178, 288, 466, 754, 1220, 1974, 3194,....

Are there any numbers that can be represented in exactly N ways, N > 2, as the sum of two Fibonacci numbers? For the case N = 3, I have checked up to 1.2 x 10^4 and have found no such numbers.

Joseph Pe

The people on the math faculty at the university I attended might chide me for not writing this up more formally. Too bad. I want to write this up before someone beats me to it.

Consider the set S(k), which is the set of the first k Fibonacci numbers, and the set A(k) which is the set of numbers resulting from the addition of any two *different* numbers in S(k).

We will consider the fist two numbers in the series here to be 1 and 2.

S(1) is {1} and A(1) is {} S(2) is {1, 2} and A(2) is {3} s(3) is {1, 2, 3} and A(3) is {3, 4, 5}

Now consider what happens to A(k) when the Kth Fibonacci number is added. The number added to the set S(k+1) is equal to the highest sum in A(k) so the numbers added to A(k) will all be greater than the Kth Fibonacci number (because the smallest element in S(k+1) is 1) and by induction you can never express a given number as the sum of two *different* Fibonacci numbers in more than one way. Numbers that are two times the Kth Fibonacci will accordingly have 2 representations if you remove the requirement for the addends to be different.

What I want to look into now (I never thought about it before) is why it apparently seems to be possible to express every number as the sum of two different Fibonacci numbers. (Undoubtedly, someone already figured that out, and I just have to find it in the literature.)

These two facts combined also lead to the surprising (to me) conclusion that every Fibonacci Number is the average of two other Fibonacci numbers. That's weird, but very cool.

Craig K

[Nice proof and interesting conjecture snipped.]

This is actually pretty easy, but I like it anyway:

F(n) + F(n) = F(n+1) - F(n-1) + F(n) = F(n+1) + F(n-2).

I take back the part about this being an interesting conjecture. 12 is the first that can't be, I think.

Jonathan Dushoff

Search for 'Zeckendorf.'

To expand on this a bit: the Zeckendorf representation expresses each positive integer uniquely as a sum of Fibonacci numbers F_n, n>=2, with no two adjacent. If x can be expressed as the sum of two different Fibonacci numbers F_n and F_m, n < m, then either the two are adjacent, in which case x = F_n + F_{n+1} = F_{n+2}, or they are not, in which case F_n + F_m is the Zeckendorf representation of x. In either case there is only one way to do this. So if x is expressible in two different ways as the sum of two Fibonacci numbers, one way must be with the two Fibonacci numbers equal, i.e. x = 2 F_n. The Zeckendorf representation of 2 F_n is F_{n+1} + F_{n-2}, so 2 F_n can be written as the sum of two Fibonacci numbers (if n >= 2: I leave the cases n <= 2 as an exercise). Thus the numbers expressible in two ways as a sum of two Fibonacci numbers are just twice the Fibonacci numbers. There are none expressible in more than two ways. And those that are not expressible as the sum of two Fibonacci numbers are the ones with more than two numbers in their Zeckendorff representation.

Department of Mathematics http://www.math.ubc.ca/~israel University of British Columbia Vancouver, BC, Canada V6T 1Z2

Extending this discussion to equal triples of sums:

7 = 5 + 1 + 1 = 3 + 3 + 1 = 3 + 2 + 2 9 = 7 + 1 + 1 = 6 + 2 + 1 = 5 + 2 + 2

So there are numbers expressible as equal sums of 3 Fibonacci numbers.

What about sums of n-pairs for n>3?

For reading and size reasons, I will list no more than 5 for each. Moreover, only those with exactly n pairs are counted here.

FOUR:

8 : 1+1+1+5; 1+1+3+3; 1+2+2+3; 2+2+2+2 10 : 1+1+3+5; 1+2+2+5; 1+3+3+3; 2+2+3+3 11 : 1+1+1+8; 1+2+3+5; 2+2+2+5; 2+3+3+3 13 : 1+1+3+8; 1+2+2+8; 1+2+5+5; 2+3+3+5 15 : 1+1+5+8; 1+3+3+8; 2+2+3+8; 2+3+5+5

FIVE:

11 : 1+1+1+3+5; 1+1+2+2+5; 1+1+3+3+3; 1+2+2+3+3; 2+2+2+2+3 12 : 1+1+1+1+8; 1+1+2+3+5; 1+2+2+2+5; 1+2+3+3+3; 2+2+2+3+3 88 : 1+3+8+21+55; 2+2+8+21+55; 2+5+5+21+55; 2+5+13+13+55; 2+5+13+34+34 90 : 1+5+8+21+55; 1+8+13+13+55; 1+8+13+34+34; 1+13+21+21+34; 3+3+8+21+55 140 : 1+3+13+34+89; 1+8+8+34+89; 1+8+21+21+89; 1+8+21+55+55; 2+2+13+34+89

SIX:

12 : 1+1+1+1+3+5; 1+1+1+2+2+5; 1+1+1+3+3+3; 1+1+2+2+3+3; 1+2+2+2+2+3; 2+2+2+2+2+2 13 : 1+1+1+1+1+8; 1+1+1+2+3+5; 1+1+2+2+2+5; 1+1+2+3+3+3; 1+2+2+2+3+3; 2+2+2+2+2+3 229 : 1+3+13+34+89+89; 1+8+8+34+89+89; 1+8+21+21+89+89; 1+8+21+55+55+89; 1+8+55+55+55+55; 2+2+13+34+89+89 231 : 1+5+13+34+89+89; 3+3+13+34+89+89; 3+8+8+34+89+89; 3+8+21+21+89+89; 3+8+21+55+55+89; 3+8+55+55+55+55 234 : 1+8+13+34+89+89; 1+13+21+21+89+89; 1+13+21+55+55+89; 1+13+55+55+55+55; 1+21+34+34+55+89; 1+34+34+55+55+55

These continue on and on... (for any n...)

How about without duplication of addends? I found none for n=3 or n=4. I found some for n=5:

414 : 1+2+13+21+377; 1+2+34+144+233; 3+5+8+21+377; 3+13+21+144+233; 3+34+55+89+233 419 : 1+2+5+34+377; 3+5+13+21+377; 3+5+34+144+233; 8+13+21+144+233; 8+34+55+89+233 474 : 1+2+5+89+377; 3+5+34+55+377; 3+5+89+144+233; 8+13+21+55+377; 8+34+55+144+233 647 : 1+2+13+21+610; 1+2+34+233+377; 3+5+8+21+610; 3+13+21+233+377; 3+34+89+144+377 652 : 1+2+5+34+610; 3+5+13+21+610; 3+5+34+233+377; 8+13+21+233+377; 8+34+89+144+377

SIX:

304 : 1+2+5+8+55+233; 1+2+13+21+34+233; 1+2+13+55+89+144; 3+5+8+21+34+233; 3+5+8 +55+89+144; 3+13+21+34+89+144 448 : 1+2+5+8+55+377; 1+2+13+21+34+377; 1+2+13+55+144+233; 3+5+8+21+34+377; 3+5+ 8+55+144+233; 3+13+21+34+144+233 482 : 1+2+5+8+89+377; 1+2+13+34+55+377; 1+2+13+89+144+233; 3+5+8+34+55+377; 3+5+ 8+89+144+233; 3+13+34+55+144+233 490 : 1+2+8+13+89+377; 1+2+21+34+55+377; 1+2+21+89+144+233; 3+8+13+34+55+377; 3+ 8+13+89+144+233; 3+21+34+55+144+233 492 : 2+3+8+13+89+377; 2+3+21+34+55+377; 2+3+21+89+144+233; 5+8+13+34+55+377; 5+ 8+13+89+144+233; 5+21+34+55+144+233

And so on.