Distinct sums of Fibonacci numbers

The total number of [not necessarily distinct] sums is $\dbinom{15}{3}=455$ . We must now find where two different triples have the same sum.

First, we will show that no two pairs can have the same sum. Consider the largest element of either pair, and call it $f_a$ . Clearly, this element cannot appear in both pairs, since then the pairs would be identical. Let the other element in that set be $f_b$ , and let $(f_c,f_d)$ , where $c>d$ , be the other pair. Therefore, $a>c>d>b$ . We must have that $f_a+f_b=f_c+f_d$ However, we also know that $f_a=f_{a-1}+f_{a-2}\ge f_c+f_d$ Also, $f_a+f_b>f_{a-1}+f_{a-2}\ge f_c+f_d$ Therefore, no two pairs can have a collision.

Now, we will find when two triples have a collision. Let the largest element in either triple be $f_a$ . It must not appear in the other triple since no two pairs have the same sum. Let the two other elements of the triple be $f_b$ and $f_c$ . Let the other triple be $(f_d,f_e,f_f)$ , where $d>e>f$ . We know that $f_a=f_{a-1}+f_{a-2}\ge f_d+f_e$ If $d\neq a-1$ , then $d<a-1$ , $e<a-2$ , and $f<a-3$ , and

$\begin{aligned} f_a&=f_{a-1}+f_{a-2}=f_{a-1}+f_{a-3}+f_{a-4} \\ &>f_{a-2}+f_{a-3}+f_{a-4}\ge f_d+f_e+f_f \end{aligned}$

Therefore, $d=a-1$ . Also, if $e<a-2$ and $f<a-3$ , then $f_a=f_{a-1}+f_{a-2}=f_{a-1}+f_{a-3}+f_{a-4}\ge f_d+f_e+f_f$ Therefore, $e=a-2$ . Now, we must have $f_b+f_c=f_f$ This only occurs when $(b,c)$ is a permutation of $(f-1,f-2)$ . Therefore, our triples become $(f_a,f_{f-1},f_{f-2})$ $(f_f,f_{a-1},f_{a-2})$ If $a=16$ , then there are 10 possibilities for $f$ , 4 through 13. Similarly, our total overcounting is $10+9+8+7+6+5+4+3+2+1=55$ The answer is $455-55=\boxed{400}$ .

This question essentially boils down into how many triples of Fibonacci numbers in this range can have the same sum. By the definition of the Fibonacci numbers, $F_n + F_{n+1} = F_{n+2}$ . Thus, if we have two triples of such numbers, then we can make two triples of distinct Fibonacci numbers that have the same sum. For example, given $F_2, F_3, F_4, F_7, F_8, F_9$ , then $F_2 + F_3 + F_9 = F_4 + F_7 + F_8$ .

Finding the number of such triplet pairs, we find $55$ . Now we find to prove that there are no other.

Since all elements of $S_{15}$ are positive integers, we can't have $F_n + F_m + F_p = F_q$ or else the RHS would be larger with the addition. The two other options are $F_n + F_m + F_p = F_p + F_x + F_y \rightarrow F_n + F_m = F_x + F_y$ or $F_n + F_m = F_x$ (while obviously being distinct from the example above).

For the former, WLOG say $F_n$ is the largest of the four, then since they are all distinct the largest sum $F_x + F_y$ could have would be $F_n$ , and since $F_m$ is positive there are no solutions.

For the latter, we look to find two nonconsecutive positive fibonacci numbers such that when added they equal the sum of a positive fibonacci number. If the larger number is $F_n$ , then necessarily the smaller number must be $F_{n - 1}$ or else the sum would be too little to reach $F_{n + 1}$ .

Thus the number of distinct sums is $455 - 55 = 400$ .

We have $F_i + F_{i+1} - F_{i+2} = 0 = F_j + F_{j+1} - F_{j+2}$ or

$F_i + F_{i+1} + F_{j+2} = F_j + F_{j+1} + F_{i+2}$ , where $i,i+1,i+2,j,j+1,j+2$ are distinct positive integers

Let $(a,b,c,d)$ denote the values of $F_i, F_{i+1},F_j, F_{j+1}$ respectively

So the set of equal sums consists of

$(1,2,4,5), (1,2,5,6), (1,2,6,7), (1,2,7,8) , \ldots , (1,2,13,14)$

$(2,3,5,6), (2,3,6,7), (1,2,7,8), \ldots , (2,3,13,14)$

$(3,4,6,7), (3,4,7,8), \ldots , (3,4,13,14)$

$.$

$.$

$.$

$(9,10, 12,13), (9, 10, 13, 14)$

$(10,11, 13, 14)$

Which gives a total of $1+2+3 + \ldots + 10 = 55$

[ e.g: $(9,10,12,13)$ means $F_9 + F_{10} + F_{14} = F_{12} + F_{13} + F_{11}$ ]

So the total number of different possible sums is ${15 \choose 3} - 55 = \boxed{400}$

Note : we can also generalize for any integer $n$ (still with 3 three distinct elements chosen).

If $n < 6, N(S_n) = {n \choose 3}$

If $n \geq 6, N(S_n) = {n \choose 3} - \frac {1}{2} (n-4)(n-5)$