A166861 Euler transform of Fibonacci numbers.

1, 1, 2, 4, 8, 15, 30, 56, 108, 203, 384, 716, 1342, 2487, 4614, 8510, 15675, 28749, 52652, 96102, 175110, 318240, 577328, 1045068, 1888581, 3406455, 6134530, 11029036, 19799363, 35490823, 63531134, 113570988, 202767037, 361565865, 643970774, 1145636750

Offset

0,3

Comments

In general, the sequence with g.f. Product_{k>=1} 1/(1-x^k)^Fibonacci(k+z), where z is nonnegative integer, is asymptotic to phi^(n + z/4) / (2 * sqrt(Pi) * 5^(1/8) * n^(3/4)) * exp((phi/10 - 1/2) * Fibonacci(z) - Fibonacci(z+1)/10 + 2 * 5^(-1/4) * phi^(z/2) * sqrt(n) + s), where s = Sum_{k>=2} (Fibonacci(z) + Fibonacci(z+1) * phi^k) / ((phi^(2*k) - phi^k - 1)*k) and phi = A001622 = (1+sqrt(5))/2 is the golden ratio. - Vaclav Kotesovec, Aug 06 2015

Links

Vaclav Kotesovec, Table of n, a(n) for n = 0..4550

Loic Foissy, The Hopf algebra of Fliess operators and its dual pre-Lie algebra, 2013.

W. S. Gray, K. Ebrahimi-Fard, Affine SISO Feedback Transformation Group and Its Faa di Bruno Hopf Algebra, arXiv:1411.0222 [math.OC], 2014.

Vaclav Kotesovec, Asymptotics of the Euler transform of Fibonacci numbers, arXiv:1508.01796 [math.CO], Aug 07 2015

Vaclav Kotesovec, Asymptotics of sequence A034691

Formula

G.f.: Product_{k>0} 1/(1 - x^k)^Fibonacci(k).

a(n) ~ phi^n / (2 * sqrt(Pi) * 5^(1/8) * n^(3/4)) * exp(-1/10 + 2*5^(-1/4)*sqrt(n) + s), where s = Sum_{k>=2} phi^k / ((phi^(2*k) - phi^k - 1)*k) = 0.600476601392575912969719494850393576083765123939643511355547131467... and phi = A001622 = (1+sqrt(5))/2 is the golden ratio. - Vaclav Kotesovec, Aug 06 2015

G.f.: exp(Sum_{k>=1} x^k/(k*(1 - x^k - x^(2*k)))). - Ilya Gutkovskiy, May 29 2018

Example

G.f. = 1 + x + 2*x^2 + 4*x^3 + 8*x^4 + 15*x^5 + 30*x^6 + 56*x^7 + 108*x^8 + 203*x^9 + ...

Maple

F:= proc(n) option remember; (<<1|1>, <1|0>>^n)[1, 2] end:
a:= proc(n) option remember; `if`(n=0, 1, add(add(d*
      F(d), d=numtheory[divisors](j))*a(n-j), j=1..n)/n)
    end:
seq(a(n), n=0..40);  # Alois P. Heinz, Jan 12 2017

Mathematica

CoefficientList[Series[Product[1/(1-x^k)^Fibonacci[k], {k, 1, 40}], {x, 0, 40}], x] (* Vaclav Kotesovec, Aug 05 2015 *)

Prog

(PARI) ET(v)=Vec(prod(k=1, #v, 1/(1-x^k+x*O(x^#v))^v[k]))
ET(vector(40, n, fibonacci(n)))
(SageMath)
def EulerTransform(a):
    @cached_function
    def b(n):
        if n == 0: return 1
        s = sum(sum(d * a(d) for d in divisors(j)) * b(n-j) for j in (1..n))
        return s//n
    return b
a = BinaryRecurrenceSequence(1, 1)
b = EulerTransform(a)
print([b(n) for n in range(36)]) # Peter Luschny, Nov 11 2020

Crossrefs

Cf. A000045, A034691, A109509, A200544, A260787, A261031, A261050, A260916, row sums of A337009.

Sequence in context: A301480 A217777 A034338 * A026023 A077596 A091865

Adjacent sequences: A166858 A166859 A166860 * A166862 A166863 A166864

Keyword

nonn

Author

Franklin T. Adams-Watters, Oct 21 2009

Extensions

First formula corrected by Vaclav Kotesovec, Aug 05 2015

Status

approved