A373629 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.

1, 3, 12, 39, 131, 426, 1389, 4503, 14596, 47259, 152991, 495162, 1602521, 5186067, 16782828, 54310911, 175754731, 568755690, 1840534485, 5956098495, 19274345876, 62373103443, 201843619047, 653179698234, 2113733947681, 6840186809691, 22135309606524, 71631366769623

Offset: 1

Author

Iskender Ozturk, Melike Caliskan, Betül Küçükgök, Ecem Yanik, Irem Türker, Rüya Kılıçarslan, Jun 11 2024

Keywords

• nonn
• easy

Comments

The numbers that are summed are the terms t of A247648 in the range 2^(n-1) <= t < 2^n.

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).

Examples

			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.
		

References

• R. Grimaldi, (2012). Fibonacci and Catalan Numbers: An Introduction, page 80, Example 12.1.

Links

• Paolo Xausa, Table of n, a(n) for n = 1..1000
• Iskender Ozturk, Walking paths.
• Index entries for linear recurrences with constant coefficients, signature (3,3,-6,-4).

Crossrefs

Cf. A000045 (Fibonacci numbers), A247648.

Programs

Mathematica

LinearRecurrence[{3, 3, -6, -4}, {1, 3, 12, 39}, 30] (* Paolo Xausa, Jun 19 2024 *)

PARI

Vec(x/((1 - x - x^2)*(1 - 2*x - 4*x^2)) + O(x^40)) \\ Michel Marcus, Jun 16 2024

Formula

a(n) = Sum_{i=F(n+1)..F(n+2)-1} A247648(i) where F(n) = A000045(n) is the n-th Fibonacci number.

a(n) = a(n-1) + a(n-2) + F(n)*2^(n-1).

a(n) = 3*a(n-1) + 3*a(n-2) - 6*a(n-3) - 4*a(n-4).

a(n) = F(n)*(2^n-1) - Sum_{i=1..n-1} F(i)*F(n-i-1)*2^(n-i-1).

G.f.: x/((1 - x - x^2)*(1 - 2*x - 4*x^2)).

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