

A036799


a(n) = 2 + 2^(n+1)*(n1).


20



0, 2, 10, 34, 98, 258, 642, 1538, 3586, 8194, 18434, 40962, 90114, 196610, 425986, 917506, 1966082, 4194306, 8912898, 18874370, 39845890, 83886082, 176160770, 369098754, 771751938, 1610612738, 3355443202, 6979321858, 14495514626, 30064771074, 62277025794
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

This sequence is a part of a class of sequences of the type: a(n) = Sum_{i=0..n} (C^i)*(i^k). This sequence has C=2, k=1. Sequence A036800 has C=2, k=2. Suppose C >= 2, k >= 1 are integers. What is the general closed form for a(n)?  Ctibor O. Zizka, Feb 07 2008
a(n) is the number of swaps needed in the worst case, when successively inserting 2^(n+1)  1 keys into an initially empty binary heap (thus creating a tree with n+1 full levels).  Rudy van Vliet, Nov 09 2015
a(n) is also the total path length of the complete binary tree of height n, with nodes at depths 0,...,n. Total path length is defined to be the sum of depths over all nodes.  F. Skerman, Jul 02 2017
For n >= 1, every number greater than or equal to a(n1) can be written as a sum of (not necessarily distinct) numbers of the form 2^n  2^k with 0 <= k < n. However, a(n1)  1 cannot be written in this way. See problem N1 from the 2014 International Mathematics Olympiad Shortlist.  Dylan Nelson, Jun 02 2023


REFERENCES

M. Petkovsek et al., A=B, Peters, 1996, p. 97.


LINKS



FORMULA

a(n) = (n1) * 2^(n+1) + 2.
a(n) = 5*a(n1)  8*a(n2) + 4*a(n3) for n > 2.  Wesley Ivan Hurt, Nov 12 2015
a(n) = Sum_{k=0..n} Sum_{i=0..n} k * binomial(k,i).  Wesley Ivan Hurt, Sep 21 2017
E.g.f.: 2*exp(x)  2*(12*x)*exp(2*x).  G. C. Greubel, Mar 29 2021


MAPLE



MATHEMATICA



PROG

(PARI) concat(0, Vec(2*x/((1x)*(12*x)^2) + O(x^40))) \\ Altug Alkan, Nov 09 2015
(Sage) [2^(n+1)*(n1) +2 for n in (0..40)] # G. C. Greubel, Mar 29 2021


CROSSREFS



KEYWORD

nonn,easy


AUTHOR



STATUS

approved



