%I #32 Jun 21 2021 06:04:06
%S 0,0,1,3,8,17,34,63,113,196,334,560,930,1532,2511,4099,6674,10845,
%T 17600,28535,46235,74880,121236,196248,317628,514032,831829,1346043,
%U 2178068,3524321,5702614,9227175,14930045,24157492,39087826,63245624,102333774,165579740
%N Number of ordered subsequences of {1,...,n} containing at least three elements and such that the first differences contain only odd numbers.
%D Chu, Hung Viet. "Various Sequences from Counting Subsets." Fib. Quart., 59:2 (May 2021), 150-157.
%H Alois P. Heinz, <a href="/A344004/b344004.txt">Table of n, a(n) for n = 1..2000</a>
%H Hung Viet Chu, <a href="https://arxiv.org/abs/2005.10081">Various sequences from counting subsets</a>, arXiv:2005.10081 [math.CO], 2020-2021.
%H <a href="/index/Rec#order_06">Index entries for linear recurrences with constant coefficients</a>, signature (3,-1,-4,3,1,-1).
%F G.f.: x^3/((x-1)^3*(x+1)*(x^2+x-1)). - _Alois P. Heinz_, Jun 02 2021
%F Comment from _N. J. A. Sloane_, Jun 03 2021. (Start)
%F Theorem: This sequence has g.f. G_1(x) = x^3/((1-x)^3*(1+x)*(1-x-x^2)) = x^3/(1-2*x-x^2+3*x^3-x^5), which implies a linear recurrence with constant coefficients and signature (3,-1,-4,3,1,-1).
%F Proof: We will not give a complete proof, but we will do enough, we hope, to convince the reader.
%F Let b(n) be the number of ordered subsequences S of {1,...,n} containing at least three elements, such that the first differences contain only odd numbers, and in which the largest term is n.
%F Then the a(n) are the partial sums of the b(n), and we claim that b(n) has generating function (1-x)*G_1(x).
%F We obtain a recurrence for b(n) as follows.
%F If we remove n from the subsequence S, there are two possibilities. Either we obtain a subsequence of {1,...,n-i} with largest term n-r (r odd) containing at least three elements, or we obtain a pair j, n-r with r and n-r-j odd. In this case j can be chosen in floor((n-r)/2) ways.
%F So, setting r = 2*i+1, we have shown that b(n) satisfies the recurrence
%F b(n) = Sum_{i = 0..floor(n/2)-1)} (b(n-(2*i+1)) + floor((n-(2*i+1))/2)),
%F with initial conditions b(1)=b(2)=0, b(3)=1.
%F It turns out that b(n) is a fairly well-known sequence, A129696, whose generating function is known to equal (1-x)*G_1(x), and whose first differences (A052952) are essentially the Fibonacci numbers F_k with 1 subtracted if k is even. (End)
%F a(n) = Fibonacci(n+3) - (1/8)(15 + 8*n + 2*n^2 + (-1)^n). - _Greg Dresden_, Jun 20 2021
%e For n = 3 there is just one subset, {1,2,3}, whose first differences, {1,1}, contain only odd numbers.
%e a(4) = 3 from {1,2,3}, {2,3,4}, {1,2,3,4}.
%p a:= n-> (<<0|1|0|0|0|0>, <0|0|1|0|0|0>, <0|0|0|1|0|0>,
%p <0|0|0|0|1|0>, <0|0|0|0|0|1>, <-1|1|3|-4|-1|3>>^n)[3, 6]:
%p seq(a(n), n=1..38); # _Alois P. Heinz_, Jun 02 2021
%Y Cf. A000045, A052952, A129696.
%Y Column k=3 of A345123.
%K nonn,easy
%O 1,4
%A _N. J. A. Sloane_, Jun 02 2021
%E a(13)-a(38) from _Alois P. Heinz_, Jun 02 2021