login
Nearly-Fibonacci sequence.
2

%I #15 Dec 09 2021 17:07:39

%S 1,1,2,4,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,

%T 10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,

%U 1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155

%N Nearly-Fibonacci sequence.

%C Generate a tree T by these rules: 0 is in T, and if x is in T, then x+1 and -2x are in T, with duplicates deleted as they occur; see A264799. Let g(0) = {0}, g(1) = {1}, g(2) = {-2,2}, g(3) = {-4,-1,3,4}, etc. The number |g(n)| of numbers in the n-th generation of T is a Fibonacci number except for g(3).

%H Colin Barker, <a href="/A264800/b264800.txt">Table of n, a(n) for n = 1..1000</a>

%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (1,1).

%F a(n) = F(n) for 1 <= n <= 3 and n >= 5, and a(4) = 4; where F = A000045, the Fibonacci numbers.

%F From _Colin Barker_, Nov 25 2015: (Start)

%F a(n) = a(n-1) - a(n-2) for n>6.

%F G.f.: x*(x-1)*(x+1)*(x^3+x^2+1) / (x^2+x-1).

%F (End)

%t z = 10; t = Expand[NestList[DeleteDuplicates[Flatten[Map[{# + 1, -2*#} &, #], 1]] &, {0}, z]]; s[0] = t[[1]]; s[n_] := s[n] = Union[t[[n]], s[n - 1]];

%t g[n_] := Complement[s[n], s[n - 1]]; g[1] = {0};

%t Table[Length[g[k]], {k, 1, z}] (* A264800 *)

%t u = Table[g[k], {k, 1, z}]

%t Flatten[u] (* A264799 *)

%t LinearRecurrence[{1,1},{1,1,2,4,5,8},40] (* _Harvey P. Dale_, Dec 09 2021 *)

%o (PARI) Vec(x*(x-1)*(x+1)*(x^3+x^2+1)/(x^2+x-1) + O(x^100)) \\ _Colin Barker_, Nov 25 2015

%Y Cf. A264799, A000045.

%K nonn,easy

%O 1,3

%A _Clark Kimberling_, Nov 25 2015