A023548 Convolution of natural numbers >= 2 and Fibonacci numbers.

2, 5, 11, 21, 38, 66, 112, 187, 309, 507, 828, 1348, 2190, 3553, 5759, 9329, 15106, 24454, 39580, 64055, 103657, 167735, 271416, 439176, 710618, 1149821, 1860467, 3010317, 4870814, 7881162, 12752008, 20633203, 33385245, 54018483, 87403764, 141422284

Offset: 1

Author

Clark Kimberling

Keywords

• nonn
• easy

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

Record-positions for A107910: A107910(a(n+2)) = A005578(n), A107910(m) < A005578(n) for m < a(n+2). - Reinhard Zumkeller, May 28 2005

From Jianing Song, Apr 28 2025: (Start)

For n >= 4, a(n-3) is the number of subsets of {1,2,...,n} with at least 2 elements that contain no consecutive elements modulo n. Note that:

- the number of subsets of {1,2,...,n} with k elements such that the difference of successive elements is at least 2 is binomial(n+1-k,k);

- the number of such subsets of {1,2,...,n} with k elements that contain both 1 and n is equal to the number of such subsets of {3,...,n-2} with k-2 elements, which is binomial(n-3-(k-2),k-2),

hence a(n) = Sum_{k=2..floor((n+1)/2)} binomial(n+1-k,k) - Sum_{k=0..floor((n-3)/2)} binomial(n-3-k,k) = (F(n+2) - binomial(n+1,0) - binomial(n,1)) - F(n-2) = F(n+1) + F(n-1) - (n+1).

If subsets of {1,2,...,n} are only required to contain no consecutive elements, then the result is A001924(n-2). (End)

Links

• Colin Barker, Table of n, a(n) for n = 1..1000
• N.-N. Cao and 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).

Crossrefs

Cf. A000032, A000045, A001924, A006327.

Antidiagonal sums of A292030.

Programs

GAP

List([1..40], n-> Lucas(1,-1,n+3)[2] -n-4); # G. C. Greubel, Jul 08 2019

Magma

[4*(Fibonacci(n+1)-1)+3*Fibonacci(n)-n: n in [1..40]]; // Vincenzo Librandi, Sep 16 2017

Mathematica

Table[4(Fibonacci[n+1] -1) +3Fibonacci[n] -n, {n, 40}] (* Vincenzo Librandi, Sep 16 2017 *)

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

Sage

[lucas_number2(n+3,1,-1) -n-4 for n in (1..40)] # G. C. Greubel, Jul 08 2019

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) = F(n+4) + F(n+2) - (n+4) for n >= 1. - Alex Vinokur (alexvn(AT)barak-online.net), Oct 26 2004 [Offset corrected by Jianing Song, Apr 28 2025]

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

E.g.f.: 2*exp(x/2)*(2*cosh((sqrt(5)*x)/2) + sqrt(5)*sinh((sqrt(5)*x)/2)) - exp(x)*(4 + x). - Stefano Spezia, May 21 2025