An n-sum of *type 1* is a finite sequence of positive integers a_{1}, a_{2}, ... , a_{r}, such that: (1) a_{1} + a_{2} + ... a_{r} = n; and (2) a_{1} > a_{2} + a_{3}, a_{2} > a_{3} + a_{4}, ... , a_{r-2} > a_{r-1} + a_{r}, and a_{r-1} > a_{r}. For example, there are five 7-sums of type 1, namely: 7; 6, 1; 5, 2; 4, 3; 4, 2, 1.

An n-sum of *type 2* is a finite sequence of positive integers b_{1}, b_{2}, ... , b_{s} such that: (1) b_{1} + b_{2} + ... + b_{s} = n; (2) b_{1} ≥ b_{2} ≥ ... ≥ b_{s}; (3) each b_{i} is in the sequence 1, 2, 4, ... , g_{j}, ... defined by g_{1} = 1, g_{2} = 2, g_{j} = g_{j-1} + g_{j-2} + 1; and (4) if b_{1} = g_{k}, then 1, 2, 4, ... , g_{k} is a subsequence. For example, there are five 7-sums of type 2, namely: 4, 2, 1; 2, 2, 2, 1; 2, 2, 1, 1, 1; 2, 1, 1, 1, 1, 1; 1, 1, 1, 1, 1, 1, 1.

Prove that for n ≥ 1 the number of type 1 and type 2 n-sums is the same.

**Solution**

Moderately hard.

Let f_{i} be the usual Fibonacci sequence defined by f_{1} = f_{2} = 1, f_{n} = f_{n-1} + f_{n-2}. A trivial induction gives that g_{n} = ∑_{1}^{n} f_{i}.

We show that there is a bijection between n-sums of type 2 with b_{1} = g_{k} and n sums of type 1 with k members.

Since a type 2 n-sum with b_{1} = g_{k} is made up entirely of elements of {g_{1}, g_{2}, ... , g_{k}} and includes each element at least once, there is a bijection between such n-sums and sequences of non-negative numbers c_{1}, c_{2}, ... , c_{k} satisfying (c_{1} + 1)g_{1} + (c_{2} + 1)g_{2} + ... + (c_{k} + 1)g_{k} = n (*).

Suppose a_{i} is a type 1 n-sum with k terms. Then condition (2) implies that a_{i} ≥ a_{i+1} + a_{i+2} + 1, for i < k - 1, and a_{k} ≥ 1, a_{k-1} ≥ 2. So a_{i} ≥ g_{i}. If we increase a_{i} above this minimum value, then that has a knock-on effect for a_{j} with j < i. In fact, we can write:

a_{k} = g_{1} + c_{k}f_{1};

a_{k-1} = g_{2} + c_{k}f_{2} + c_{k-1}f_{1};

a_{k-2} = g_{3} + c_{k}f_{3} + c_{k-1}f_{2} + c_{k-2}f_{1};

...

a_{1} = g_{k} + c_{k}f_{k} + c_{k-1}f_{k-1} + ... + c_{1}f_{1}.

Since the sum of the a_{i} is n, the c_{i} satisfy (*). Conversely, if c_{i} are any non-negative numbers satisfying (*), then the relations above give a type 1 n-sum a_{i}. So we have a bijection between type 1 n-sums with k members and non-negative c_{i} satisfying (*). Putting the two bijections together gives the claimed bijection between type 2 n-sums with largest member g_{k} and type 1 n-sums with k members.

It follows that there is a bijection between type 1 and type 2 n-sums.

© John Scholes

jscholes@kalva.demon.co.uk

21 Sep 1999