login
Numbers with two representations as the sum of two Fibonacci numbers.
9

%I #32 Jan 29 2017 14:04:19

%S 4,6,10,16,26,42,68,110,178,288,466,754,1220,1974,3194,5168,8362,

%T 13530,21892,35422,57314,92736,150050,242786,392836,635622,1028458,

%U 1664080,2692538,4356618,7049156,11405774,18454930,29860704,48315634,78176338,126491972

%N Numbers with two representations as the sum of two Fibonacci numbers.

%C A positive integer n has exactly two representations as the sum of two Fibonacci numbers if and only if n is twice a Fibonacci number and n >= 4. Conjectured by _John W. Layman_, Dec 20 2002. Proved by Max Alekseyev, Mar 02 2007.

%C From _Max Alekseyev_, Mar 02 2007: (Start)

%C Suppose that the number m has exactly two representations as the sum of two Fibonacci numbers. There are three types of representations possible:

%C (I) the sum of two equal Fibonacci numbers

%C (II) the sum of two consecutive Fibonacci numbers

%C (III) the sum of two distinct non-consecutive Fibonacci numbers

%C Lemma. The two representations of m > 2 must be of different types.

%C Proof. Two representations of m > 2 both of type (I) are not possible as 2*F(n) is a strictly increasing function for n >= 2. Similarly, two representations of m both of type (II) are not possible as F(n) + F(n+1) is a strictly increasing function for n >= 0. Finally, two representations of m both of type (III) are not possible as that would violate the property of the Fibonacci numeral system (the uniqueness of representation of all nonnegative integers).

%C Consider all possible pairs of representation types:

%C (I) and (II) are possible only for m = 2: 2 = 2*F(1) = 2*F(2) = F(1) + F(2) but m = 2 has more than two different representations.

%C (II) and (III) are not possible together as that would again violate the property of the Fibonacci numeral system.

%C Finally, (I) and (III) gives rise to the sequence of a(n) = 2 * F(n) = F(n+1) + F(n-1). QED (End)

%H Colin Barker, <a href="/A078642/b078642.txt">Table of n, a(n) for n = 1..1000</a>

%H Tanya Khovanova, <a href="http://www.tanyakhovanova.com/RecursiveSequences/RecursiveSequences.html">Recursive Sequences</a>

%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (1,1)

%F a(n) = 2F(n + 2), where F(n) is the n-th Fibonacci number.

%F a(n) = a(n - 1) + a(n - 2), n > 2 ; a(1) = 4, a(2) = 6 . G.f.: 2x*(2+x)/(1-x-x^2). - _Philippe Deléham_, Nov 19 2008

%F a(n) = 2F(n + 2) = F(n) + F(n + 3), where F(1) = F(2) = 1. - _Alonso del Arte_, Jul 07 2013

%F a(n) = (2^(-n)*((1-r)^n*(-3+r) + (1+r)^n*(3+r))) / r where r=sqrt(5). - _Colin Barker_, Jan 29 2017

%e 16 has exactly two representations as the sum of Fibonacci numbers: 16 = 3 + 13 and 16 = 8 + 8. Hence 16 belongs to the sequence.

%t t = Split@ Sort@ Flatten@ Table[Fibonacci[i] + Fibonacci[j], {i, 2, 39}, {j, 2, i}]; Take[ t[[ # ]][[1]] & /@ Select[ Range@Length@t, Length[ t[[ # ]]] > 1 &], 36] (* _Robert G. Wilson v_ *)

%o (PARI) a(n)=([0,1; 1,1]^(n-1)*[4;6])[1,1] \\ _Charles R Greathouse IV_, Oct 07 2015

%o (PARI) Vec(2*x*(2 + x) / (1 - x - x^2) + O(x^60)) \\ _Colin Barker_, Jan 29 2017

%Y Essentially the same as A006355 = number of binary vectors of length n containing no singletons; and as A055389: a(0)=1, then twice the Fibonacci sequence.

%K nonn,easy

%O 1,1

%A _Joseph L. Pe_, Dec 12 2002