OFFSET
1,2
COMMENTS
a(n) is the number of runs of strictly increasing parts in all compositions of n. a(3) = 7: (1)(1)(1), (12), (2)(1), (3). - Alois P. Heinz, Apr 30 2017
From Hugo Pfoertner, Feb 19 2020: (Start)
a(n)/2^(n-2) apparently is the expected number of flips of a fair coin to completion of a game where the player advances by 1 for heads and by 2 for tails, starting at position 0 and repeating to flip until the target n+1 is exactly reached. If the position n (1 below the target) is reached, the player stays at this position and continues to flip the coin and count the flips until he can advance by 1.
The expected number of flips for targets 1, 2, 3,... , found by inversion of the corresponding Markov matrices, is 2, 2, 3, 7/2, 17/4, 39/8, 89/16, 199/32, 441/64, ...
Target 1 needs an expected number of 2 flips and would require a(0) = 1/2.
n=1, target n+1 = 2: 1 / 2^(1-2) = 2;
n=2, target n+1 = 3: 3 / 2^(2-2) = 3;
n=3, target n+1 = 4: 7 / 2^(3-2) = 7/2.
(End)
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 1..1000
W. Bosma, Signed bits and fast exponentiation, J. Th. des Nombres de Bordeaux Vol.13, Fasc. 1, 2001.
Aruna Gabhe, Problem 11623, Am. Math. Monthly 119 (2012) 161.
Index entries for linear recurrences with constant coefficients, signature (3,0,-4).
FORMULA
a(n) = (n/3 + 7/9)*2^(n - 1) + (-1)^n/9.
From R. J. Mathar, Apr 04 2008: (Start)
O.g.f.: -x*(-1+2x^2)/((-1+2x)^2*(1+x)).
a(n) = 3*a(n-1) - 4*a(n-3). (End)
a(n) + a(n+1) = A087447(n+1). - R. J. Mathar, Feb 21 2009
A172481(n) = a(n) + 2^(n-1). Application: Problem 11623, AMM 119 (2012) 161. - Stephen J. Herschkorn, Feb 11 2012
From Wolfdieter Lang, Jun 14 2017: (Start)
a(n) = f(n+1)*2^(n-1), where f(n) is a rational Fibonacci type sequence based on fuse(a,b) = (a+b+1)/2 with f(0) = 0, f(1) = 1 and f(n) = fuse(f(n-1),f(n-2)), for n >= 2. For fuse(a,b) see the Jeff Erickson link under A188545. Proof: f(n) = (3*n+4 - (-1)^n/2^(n-2))/9, n >= 0, by induction.
a(n) = a(n-1) + a(n-2) + 2^(n-2), n >= 1, with inputs a(-1) = 0, a(0) = 1/2.
(End)
E.g.f.: (2*exp(-x) + exp(2*x)*(7 + 6*x) - 9)/18. - Stefano Spezia, Feb 19 2020
MAPLE
A127984:=n->(n/3 + 7/9)*2^(n - 1) + (-1)^n/9; seq(A127984(n), n=1..50); # Wesley Ivan Hurt, Mar 14 2014
MATHEMATICA
Table[(n/3 + 7/9)2^(n - 1) + (-1)^n/9, {n, 50}] (* Artur Jasinski *)
CoefficientList[Series[(1 - 2 x^2) / ((-1 + 2 x)^2 (1 + x)), {x, 0, 40}], x] (* Vincenzo Librandi, Jun 15 2017 *)
PROG
(Magma) [(n/3+7/9)*2^(n-1)+(-1)^n/9: n in [1..35]]; // Vincenzo Librandi, Jun 15 2017
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Artur Jasinski, Feb 09 2007
STATUS
approved