A127984 a(n) = (n/3 + 7/9)*2^(n - 1) + (-1)^n/9.

1, 3, 7, 17, 39, 89, 199, 441, 967, 2105, 4551, 9785, 20935, 44601, 94663, 200249, 422343, 888377, 1864135, 3903033, 8155591, 17010233, 35418567, 73633337, 152859079, 316902969, 656175559, 1357090361, 2803659207, 5786275385, 11930464711, 24576757305

Offset: 1

Author

Artur Jasinski, Feb 09 2007

Keywords

• nonn
• easy

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

Crossrefs

Cf. A059570, A073371, A127976, A127978, A127979, A127980, A127981, A127982, A127983, A073371, A000337, A172481.

Programs

Magma

[(n/3+7/9)*2^(n-1)+(-1)^n/9: n in [1..35]]; // Vincenzo Librandi, Jun 15 2017

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

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