Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #79 Jun 21 2024 16:04:59
%S 1,3,12,39,131,426,1389,4503,14596,47259,152991,495162,1602521,
%T 5186067,16782828,54310911,175754731,568755690,1840534485,5956098495,
%U 19274345876,62373103443,201843619047,653179698234,2113733947681,6840186809691,22135309606524,71631366769623
%N a(n) = sum of all numbers whose binary expansion is n bits long, starts and ends with a 1 bit, and contains no 00 bit pairs.
%C The numbers that are summed are the terms t of A247648 in the range 2^(n-1) <= t < 2^n.
%C There are Fibonacci(n) of these numbers (per Grimaldi's exercise, in which closed walks on the u-v graph there are a 1 bit at a visit to u and a 0 bit at a visit to v), and this allows recurrences etc. for a(n).
%D R. Grimaldi, (2012). Fibonacci and Catalan Numbers: An Introduction, page 80, Example 12.1.
%H Paolo Xausa, <a href="/A373629/b373629.txt">Table of n, a(n) for n = 1..1000</a>
%H Iskender Ozturk, <a href="/A373629/a373629_2.pdf">Walking paths</a>.
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (3,3,-6,-4).
%F a(n) = Sum_{i=F(n+1)..F(n+2)-1} A247648(i) where F(n) = A000045(n) is the n-th Fibonacci number.
%F a(n) = a(n-1) + a(n-2) + F(n)*2^(n-1).
%F a(n) = 3*a(n-1) + 3*a(n-2) - 6*a(n-3) - 4*a(n-4).
%F a(n) = F(n)*(2^n-1) - Sum_{i=1..n-1} F(i)*F(n-i-1)*2^(n-i-1).
%F G.f.: x/((1 - x - x^2)*(1 - 2*x - 4*x^2)).
%F E.g.f.: 2*(exp(x)*(sqrt(5)*cosh(sqrt(5)*x) + 7*sinh(sqrt(5)*x)) - exp(x/2)*(sqrt(5)*cosh(sqrt(5)*x/2) + 4*sinh(sqrt(5)*x/2)))/(11*sqrt(5)). - _Stefano Spezia_, Jun 19 2024
%e For n=5, the terms of A247648 that are in the interval [16, 31] are 21, 23, 27, 29, and 31, so a(5) = 21+23+27+29+31 = 131.
%t LinearRecurrence[{3, 3, -6, -4}, {1, 3, 12, 39}, 30] (* _Paolo Xausa_, Jun 19 2024 *)
%o (PARI) Vec(x/((1 - x - x^2)*(1 - 2*x - 4*x^2)) + O(x^40)) \\ _Michel Marcus_, Jun 16 2024
%Y Cf. A000045 (Fibonacci numbers), A247648.
%K nonn,easy
%O 1,2
%A _Iskender Ozturk_, _Melike Caliskan_, _Betül Küçükgök_, _Ecem Yanik_, Irem Türker, Rüya Kılıçarslan, Jun 11 2024