OFFSET
1,2
COMMENTS
a(n) is the sum of all nodes at height n-1 within a binary tree structure recursively built from the Hofstadter G-sequence (see comments for A005206).
LINKS
Colin Barker, Table of n, a(n) for n = 1..1000
Wikipedia, Hofstadter sequence.
Index entries for linear recurrences with constant coefficients, signature (3,1,-5,-1, 1).
FORMULA
a(1) = 1 and for n > 1, a(n) = (F(n+2)+1)*F(n-1)/2, where F(n) is the n-th Fibonacci number (A000045).
From Colin Barker, Mar 27 2018: (Start)
G.f.: x*(1 - x)*(1 - 4*x^2 - x^3 + x^4) / ((1 + x)*(1 - 3*x + x^2)*(1 - x - x^2)).
a(n) = 3*a(n-1) + a(n-2) - 5*a(n-3) - a(n-4) + a(n-5) for n>6.
(End)
EXAMPLE
a(7) = 14 + 15 + 16 + ... + 21 = (F(9)+1)*F(6)/2 = 140.
MATHEMATICA
a[n_] := If[n==1, 1, (Fibonacci[n+2]+1)Fibonacci[n-1]/2]; Array[a, 50]
Join[{1}, LinearRecurrence[{3, 1, -5, -1, 1}, {2, 3, 9, 21, 55}, 40]] (* Vincenzo Librandi, Apr 18 2018 *)
PROG
(Magma) [1] cat [(Fibonacci(n+2)+1)*Fibonacci(n-1) div 2 : n in [2..35] ]; // Vincenzo Librandi, Apr 18 2018
(PARI) a(n) = if (n==1, 1, (fibonacci(n+2)+1)*fibonacci(n-1)/2); \\ Michel Marcus, Apr 21 2018
(PARI) Vec(x*(1 - x)*(1 - 4*x^2 - x^3 + x^4) / ((1 + x)*(1 - 3*x + x^2)*(1 - x - x^2)) + O(x^60)) \\ Colin Barker, May 11 2018
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Frank M Jackson, Mar 27 2018
STATUS
approved