cp's OEIS Frontend

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

%I A023548 #61 May 21 2025 08:55:38
%S A023548 2,5,11,21,38,66,112,187,309,507,828,1348,2190,3553,5759,9329,15106,
%T A023548 24454,39580,64055,103657,167735,271416,439176,710618,1149821,1860467,
%U A023548 3010317,4870814,7881162,12752008,20633203,33385245,54018483,87403764,141422284
%N A023548 Convolution of natural numbers >= 2 and Fibonacci numbers.
%C A023548 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
%C A023548 Record-positions for A107910: A107910(a(n+2)) = A005578(n), A107910(m) < A005578(n) for m < a(n+2). - _Reinhard Zumkeller_, May 28 2005
%C A023548 From _Jianing Song_, Apr 28 2025: (Start)
%C A023548 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:
%C A023548  - 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);
%C A023548  - 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),
%C A023548 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).
%C A023548 If subsets of {1,2,...,n} are only required to contain no consecutive elements, then the result is A001924(n-2). (End)
%H A023548 Colin Barker, <a href="/A023548/b023548.txt">Table of n, a(n) for n = 1..1000</a>
%H A023548 N.-N. Cao and F.-Z. Zhao, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Cao2/cao5r.html">Some Properties of Hyperfibonacci and Hyperlucas Numbers</a>, J. Int. Seq. 13 (2010) # 10.8.8
%H A023548 Ligia L. Cristea, Ivica Martinjak, and Igor Urbiha, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Urbiha/urbiha4.html">Hyperfibonacci Sequences and Polytopic Numbers</a>, Journal of Integer Sequences, Volume 19, 2016, Issue 7, #16.7.6.
%H A023548 A. B. Vinokur, <a href="http://dx.doi.org/10.1007/BF01068684">Huffman trees and Fibonacci numbers</a>, Kibernetika Issue 6 (1986) 9-12 (in Russian); English translation in Cybernetics 21, Issue 6 (1986), 692-696.
%H A023548 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 A023548 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (3,-2,-1,1).
%F A023548 From _Wolfdieter Lang_: (Start)
%F A023548 Convolution of natural numbers n >= 1 with Lucas numbers (A000032).
%F A023548 a(n) = 4*(F(n+1) - 1) + 3*F(n) - n, F(n)=A000045 (Fibonacci).
%F A023548 G.f.: x*(2-x)/((1-x-x^2)*(1-x)^2). (End)
%F A023548 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
%F A023548 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]
%F A023548 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
%F A023548 a(n) = Sum_{i=1..n} C(n-i+2,i+1) + C(n-i+1,i). - _Wesley Ivan Hurt_, Sep 13 2017
%F A023548 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
%t A023548 Table[4(Fibonacci[n+1] -1) +3Fibonacci[n] -n, {n, 40}] (* _Vincenzo Librandi_, Sep 16 2017 *)
%o A023548 (PARI) a(n) = 4*fibonacci(n+1) + 3*fibonacci(n) - n - 4; \\ _Michel Marcus_, Sep 08 2016
%o A023548 (PARI) Vec(x*(2-x) / ((1-x-x^2)*(1-x)^2) + O(x^40)) \\ _Colin Barker_, Mar 11 2017
%o A023548 (Magma) [4*(Fibonacci(n+1)-1)+3*Fibonacci(n)-n: n in [1..40]]; // _Vincenzo Librandi_, Sep 16 2017
%o A023548 (Sage) [lucas_number2(n+3,1,-1) -n-4 for n in (1..40)] # _G. C. Greubel_, Jul 08 2019
%o A023548 (GAP) List([1..40], n-> Lucas(1,-1,n+3)[2] -n-4); # _G. C. Greubel_, Jul 08 2019
%Y A023548 Cf. A000032, A000045, A001924, A006327.
%Y A023548 Antidiagonal sums of A292030.
%K A023548 nonn,easy
%O A023548 1,1
%A A023548 _Clark Kimberling_