login
a(n) = binomial(2*n,n) + Sum_{k=1..n} binomial(2*n-k,n-k)*Fibonacci(k).
1

%I #25 Jun 05 2017 22:10:25

%S 1,3,10,36,133,499,1891,7217,27690,106680,412368,1598358,6209542,

%T 24171004,94246202,368022472,1438965885,5632870627,22072920103,

%U 86575738469,339860843589,1335186464195,5249164967309,20650056413491,81285516680103

%N a(n) = binomial(2*n,n) + Sum_{k=1..n} binomial(2*n-k,n-k)*Fibonacci(k).

%H G. C. Greubel, <a href="/A277287/b277287.txt">Table of n, a(n) for n = 0..1000</a>

%F G.f.: (2*x+sqrt(1-4*x)+1)/(2*sqrt(1-4*x)*x-8*x+2).

%F a(n) = A000984(n) + A257838(n).

%F a(n) ~ 3 * 2^(2*n) / sqrt(Pi*n). - _Vaclav Kotesovec_, Oct 09 2016

%F From _Vladimir Reshetnikov_, Oct 11 2016: (Start)

%F a(n) = binomial(2*n-1, n-1)*((hypergeom([1, 1-n], [1-2*n], 1-phi)/phi + hypergeom([1, 1-n], [1-2*n], phi)*phi)/sqrt(5) + 2), where phi=(1+sqrt(5))/2.

%F Recurrence: (n+1)*(n^2-2)*a(n+1) + 2*(2*n^3+n^2-8*n+3)*a(n-2) + (15*n^3+7*n^2-62*n+26)*a(n-1) = 2*(4*n^3+3*n^2-12*n-1)*a(n). (End)

%p fib := n -> `if`(n=0, 1, combinat:-fibonacci(n)):

%p a := n -> add(binomial(2*n-k, n-k)*fib(k), k=0..n):

%p seq(a(n), n=0..24); # _Peter Luschny_, Oct 10 2016

%t Table[Sum[Binomial[2*n-k, n-k]*Fibonacci[k], {k, 1, n}] + Binomial[2*n, n], {n, 0, 20}] (* _Vaclav Kotesovec_, Oct 09 2016 *)

%t Round@Table[Binomial[2 n - 1, n - 1] ((Hypergeometric2F1[1, 1 - n, 1 - 2 n, 1 - GoldenRatio]/GoldenRatio + Hypergeometric2F1[1, 1 - n, 1 - 2 n, GoldenRatio] GoldenRatio)/Sqrt[5] + 2), {n, 0, 20}] (* Round is equivalent to FullSimplify here, but is much faster - _Vladimir Reshetnikov_, Oct 11 2016 *)

%o (Maxima) makelist(sum(binomial(2*n-k,n-k)*fib(k),k,1,n)+binomial(2*n,n),n,0,25);

%o (PARI) a(n) = binomial(2*n,n) + sum(k=1, n, binomial(2*n-k,n-k)*fibonacci(k)); \\ _Michel Marcus_, Oct 11 2016

%Y Cf. A000045, A000984, A257838.

%K nonn

%O 0,2

%A _Vladimir Kruchinin_, Oct 09 2016