%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