A065220 a(n) = Fibonacci(n) - n.

0, 0, -1, -1, -1, 0, 2, 6, 13, 25, 45, 78, 132, 220, 363, 595, 971, 1580, 2566, 4162, 6745, 10925, 17689, 28634, 46344, 75000, 121367, 196391, 317783, 514200, 832010, 1346238, 2178277, 3524545, 5702853, 9227430, 14930316, 24157780, 39088131, 63245947, 102334115, 165580100, 267914254

Offset

0,7

Comments

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

References

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.

Links

Harry J. Smith, Table of n, a(n) for n = 0..300

Gregory Dresden, On the Brousseau sums Sum_{i=1..n} i^p*Fibonacci(i), arxiv.org:2206.00115 [math.NT], 2022.

Albert Frank, International Contest Of Logical Sequences, 2002 - 2003. Item 7

Albert Frank, Solutions of International Contest Of Logical Sequences, 2002 - 2003.

A. B. Vinokur, Huffman trees and Fibonacci numbers, Cybernetics 21, Issue 6 (1986), 692-696; also at Research Gate.

Alex Vinokur, Fibonacci connection between Huffman codes and Wythoff array, arXiv:cs/0410013 [cs.DM], 2004-2005.

Index entries for linear recurrences with constant coefficients, signature (3,-2,-1,1).

Formula

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

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

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

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

Maple

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

Mathematica

lst={}; Do[f=Fibonacci[n]-n; AppendTo[lst, f], {n, 0, 5!}]; lst (* Vladimir Joseph Stephan Orlovsky, Mar 21 2009 *)
Table[Fibonacci[n]-n, {n, 0, 50}] (* or *) LinearRecurrence[{3, -2, -1, 1}, {0, 0, -1, -1}, 50] (* Harvey P. Dale, May 29 2017 *)

Prog

(PARI) a(n) = { fibonacci(n) - n } \\ Harry J. Smith, Oct 14 2009
(Haskell)
a065220 n = a065220_list !! n
a065220_list = zipWith (-) a000045_list [0..]
-- Reinhard Zumkeller, Nov 06 2012
(Magma) [Fibonacci(n) - n: n in [0..50]]; // G. C. Greubel, Jul 09 2019
(Sage) [fibonacci(n) - n for n in (0..50)] # G. C. Greubel, Jul 09 2019
(GAP) List([0..50], n-> Fibonacci(n) - n); # G. C. Greubel, Jul 09 2019

Crossrefs

Cf. A002062, A045925.

Sequence in context: A000135 A281865 A267698 * A048094 A335439 A181522

Adjacent sequences: A065217 A065218 A065219 * A065221 A065222 A065223

Keyword

easy,sign

Author

Henry Bottomley, Oct 22 2001

Status

approved