login
a(n) = Fibonacci(n) - n.
14

%I #47 Jun 02 2022 14:48:43

%S 0,0,-1,-1,-1,0,2,6,13,25,45,78,132,220,363,595,971,1580,2566,4162,

%T 6745,10925,17689,28634,46344,75000,121367,196391,317783,514200,

%U 832010,1346238,2178277,3524545,5702853,9227430,14930316,24157780,39088131,63245947,102334115,165580100,267914254

%N a(n) = Fibonacci(n) - n.

%C E(n) = Fib(n+4)-(n+4): cost of maximum height Huffman tree of size n for Fibonacci sequence (Fibonacci sequence is minimizing absolutely ordered sequence of Huffman tree). - Alex Vinokur (alexvn(AT)barak-online.net), Oct 26 2004

%D Vinokur A.B, Huffman trees and Fibonacci numbers, Kibernetika Issue 6 (1986) 9-12 (in Russian); English translation in Cybernetics 21, Issue 6 (1986), 692-696.

%H Harry J. Smith, <a href="/A065220/b065220.txt">Table of n, a(n) for n = 0..300</a>

%H Gregory Dresden, <a href="https://arxiv.org/abs/2206.00115">On the Brousseau sums Sum_{i=1..n} i^p*Fibonacci(i)</a>, arxiv.org:2206.00115 [math.NT], 2022.

%H Albert Frank, <a href="http://www.paulcooijmans.com/oth/intcont2003.html">International Contest Of Logical Sequences</a>, 2002 - 2003. Item 7

%H Albert Frank, <a href="http://www.paulcooijmans.com/oth/intcont2003ans.html">Solutions of International Contest Of Logical Sequences</a>, 2002 - 2003.

%H A. B. Vinokur, <a href="https://doi.org/10.1007/BF01068684">Huffman trees and Fibonacci numbers</a>, Cybernetics 21, Issue 6 (1986), 692-696; also at <a href="https://www.researchgate.net/publication/245015293_Huffman_trees_and_fibonacci_numbers">Research Gate</a>.

%H Alex Vinokur, <a href="https://arxiv.org/abs/cs/0410013">Fibonacci connection between Huffman codes and Wythoff array</a>, arXiv:cs/0410013 [cs.DM], 2004-2005.

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

%F a(n) = A000045(n) - A001477(n) = A000126(n-3) - 2 = A001924(n-4) - 1.

%F a(n) = a(n-1) + a(n-2) + n - 3 = a(n-1) + A000071(n-2).

%F G.f.: x^2*(2x-1)/((1-x-x^2)*(1-x)^2).

%F a(n) = Sum_{i=0..n} (i - 2)*F(n-i) for F(n) the Fibonacci sequence A000045. - _Greg Dresden_, Jun 01 2022

%p a[0]:=0:a[1]:=1:for n from 2 to 50 do a[n]:=a[n-1]+a[n-2] od: seq(a[n]-n, n=0..42); # _Zerinvary Lajos_, Mar 20 2008

%t lst={};Do[f=Fibonacci[n]-n;AppendTo[lst,f],{n,0,5!}];lst (* _Vladimir Joseph Stephan Orlovsky_, Mar 21 2009 *)

%t Table[Fibonacci[n]-n,{n,0,50}] (* or *) LinearRecurrence[{3,-2,-1,1},{0,0,-1,-1},50] (* _Harvey P. Dale_, May 29 2017 *)

%o (PARI) { for (n=0, 300, write("b065220.txt", n, " ", fibonacci(n) - n) ) } \\ _Harry J. Smith_, Oct 14 2009

%o (Haskell)

%o a065220 n = a065220_list !! n

%o a065220_list = zipWith (-) a000045_list [0..]

%o -- _Reinhard Zumkeller_, Nov 06 2012

%o (Magma) [Fibonacci(n) - n: n in [0..50]]; // _G. C. Greubel_, Jul 09 2019

%o (Sage) [fibonacci(n) - n for n in (0..50)] # _G. C. Greubel_, Jul 09 2019

%o (GAP) List([0..50], n-> Fibonacci(n) - n) # _G. C. Greubel_, Jul 09 2019

%Y Cf. A002062, A045925.

%K easy,sign

%O 0,7

%A _Henry Bottomley_, Oct 22 2001