OFFSET
1,1
COMMENTS
Minimal cost of maximum height Huffman tree of size n for strictly "worst case height" sequences. (A strictly "worst case height" sequence generates only maximum height Huffman trees; a non-strictly "worst case height" sequence can generate also non-maximum height Huffman trees.) - Alex Vinokur (alexvn(AT)barak-online.net), Oct 26 2004
LINKS
Colin Barker, Table of n, a(n) for n = 1..1000
N.-N. Cao, F.-Z. Zhao, Some Properties of Hyperfibonacci and Hyperlucas Numbers, J. Int. Seq. 13 (2010) # 10.8.8
Ligia L. Cristea, Ivica Martinjak, and Igor Urbiha, Hyperfibonacci Sequences and Polytopic Numbers, Journal of Integer Sequences, Volume 19, 2016, Issue 7, #16.7.6.
A. B. Vinokur, Huffman trees and Fibonacci numbers, Kibernetika Issue 6 (1986) 9-12 (in Russian); English translation in Cybernetics 21, Issue 6 (1986), 692-696.
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
From Wolfdieter Lang: (Start)
Convolution of natural numbers n >= 1 with Lucas numbers (A000032).
a(n) = 4*(F(n+1) - 1) + 3*F(n) - n, F(n)=A000045 (Fibonacci).
G.f.: x*(2-x)/((1-x-x^2)*(1-x)^2). (End)
For n >= 1, a(n) = L(n+3) - (n+4), where L(n) are Lucas numbers. - Mario Catalani (mario.catalani(AT)unito.it), Jul 22 2004
a(n) = Fib(n+3) + F(n+1) - (n+3) for n > 1. - Alex Vinokur (alexvn(AT)barak-online.net), Oct 26 2004
a(n) = (-4 + (2^(-n)*((1-sqrt(5))^n*(-5+2*sqrt(5)) + (1+sqrt(5))^n*(5+2*sqrt(5)))) / sqrt(5) - n). - Colin Barker, Mar 11 2017
a(n) = Sum_{i=1..n} C(n-i+2,i+1) + C(n-i+1,i). - Wesley Ivan Hurt, Sep 13 2017
MATHEMATICA
Table[4(Fibonacci[n+1] -1) +3Fibonacci[n] -n, {n, 40}] (* Vincenzo Librandi, Sep 16 2017 *)
PROG
(PARI) a(n) = 4*fibonacci(n+1) + 3*fibonacci(n) - n - 4; \\ Michel Marcus, Sep 08 2016
(PARI) Vec(x*(2-x) / ((1-x-x^2)*(1-x)^2) + O(x^40)) \\ Colin Barker, Mar 11 2017
(Magma) [4*(Fibonacci(n+1)-1)+3*Fibonacci(n)-n: n in [1..40]]; // Vincenzo Librandi, Sep 16 2017
(Sage) [lucas_number2(n+3, 1, -1) -n-4 for n in (1..40)] # G. C. Greubel, Jul 08 2019
(GAP) List([1..40], n-> Lucas(1, -1, n+3)[2] -n-4) # G. C. Greubel, Jul 08 2019
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
STATUS
approved