A277220 Exponential convolution of Fibonacci (A000045) and Catalan (A000108) numbers.
0, 1, 3, 11, 43, 180, 790, 3590, 16745, 79705, 385615, 1890747, 9375216, 46931897, 236873261, 1204089630, 6159064015, 31678706490, 163739008070, 850051218980, 4430529313065, 23175017046351, 121617754070653, 640122809255716, 3378402106118508, 17875011275340275
Offset: 0
Keywords
Links
- G. C. Greubel, Table of n, a(n) for n = 0..1000
Programs
-
Magma
[(&+[Binomial(n,k)*Fibonacci(k)*Catalan(n-k): k in [0..n]]): n in [0..30]]; // G. C. Greubel, Oct 22 2018
-
Mathematica
Table[Sum[Binomial[n, k] Fibonacci[k] CatalanNumber[n - k], {k, 0, n}], {n, 0, 30}] (* or *) Round@Table[(GoldenRatio^n Hypergeometric2F1[1/2, -n, 2, -4/GoldenRatio] - (-GoldenRatio)^(-n) Hypergeometric2F1[1/2, -n, 2, 4 GoldenRatio])/Sqrt[5], {n, 0, 30}] (* Round is equivalent to FullSimplify here, but is much faster *) -
PARI
for(n=0, 30, print1(sum(k=0,n, binomial(n,k)*fibonacci(k)* binomial(2*n-2*k,n-k)/(n-k+1)), ", ")) \\ G. C. Greubel, Oct 22 2018
Formula
a(n) = (phi^n * hypergeom([1/2, -n], [2], -4/phi) - (-phi)^(-n) * hypergeom([1/2, -n], [2], 4*phi))/sqrt(5), where phi = (1+sqrt(5))/2 = A001622.
Recurrence: 19*(n+1)*(n+2)*(11*n+13)*a(n) + 2*(55*n^3+208*n^2+311*n+230)*a(n+1) + 2*(55*n^3+373*n^2+674*n+206)*a(n+3) = (n+2)*(297*n^2+1022*n+617)*a(n+2) + (n+3)*(n+5)*(11*n+2)*a(n+4).
E.g.f.: 2*exp(5*x/2)*sinh(x*sqrt(5)/2)*(BesselI_0(2*x) - BesselI_1(2*x))/sqrt(5) (the product of e.g.f. for Fibonacci and Catalan numbers).
a(n) ~ (phi + 4)^(n + 3/2) / (8 * sqrt(5*Pi) * n^(3/2)), where phi = A001622 = (1 + sqrt(5))/2 is the golden ratio. - Vaclav Kotesovec, Mar 10 2018