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

Author

Henry Bottomley, Oct 22 2001

Keywords

• easy
• sign

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).

Crossrefs

Cf. A002062, A045925.

Programs

GAP

List([0..50], n-> Fibonacci(n) - n); # G. C. Greubel, Jul 09 2019

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

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 *)

PARI

a(n) = { fibonacci(n) - n } \\ Harry J. Smith, Oct 14 2009

Sage

[fibonacci(n) - n for n in (0..50)] # G. C. Greubel, Jul 09 2019

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