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

%I #62 Sep 08 2022 08:45:29

%S 1,3,7,17,39,89,199,441,967,2105,4551,9785,20935,44601,94663,200249,

%T 422343,888377,1864135,3903033,8155591,17010233,35418567,73633337,

%U 152859079,316902969,656175559,1357090361,2803659207,5786275385,11930464711,24576757305

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

%C 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

%C From _Hugo Pfoertner_, Feb 19 2020: (Start)

%C 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.

%C 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, ...

%C Target 1 needs an expected number of 2 flips and would require a(0) = 1/2.

%C n=1, target n+1 = 2: 1 / 2^(1-2) = 2;

%C n=2, target n+1 = 3: 3 / 2^(2-2) = 3;

%C n=3, target n+1 = 4: 7 / 2^(3-2) = 7/2.

%C (End)

%H Vincenzo Librandi, <a href="/A127984/b127984.txt">Table of n, a(n) for n = 1..1000</a>

%H W. Bosma, <a href="http://www.numdam.org/item/JTNB_2001__13_1_27_0/">Signed bits and fast exponentiation</a>, J. Th. des Nombres de Bordeaux Vol.13, Fasc. 1, 2001.

%H Aruna Gabhe, <a href="http://www.jstor.org/stable/10.4169/amer.math.monthly.119.02.161">Problem 11623</a>, Am. Math. Monthly 119 (2012) 161.

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3,0,-4).

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

%F From _R. J. Mathar_, Apr 04 2008: (Start)

%F O.g.f.: -x*(-1+2x^2)/((-1+2x)^2*(1+x)).

%F a(n) = 3*a(n-1) - 4*a(n-3). (End)

%F a(n) + a(n+1) = A087447(n+1). - _R. J. Mathar_, Feb 21 2009

%F A172481(n) = a(n) + 2^(n-1). Application: Problem 11623, AMM 119 (2012) 161. - _Stephen J. Herschkorn_, Feb 11 2012

%F From _Wolfdieter Lang_, Jun 14 2017: (Start)

%F 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.

%F a(n) = a(n-1) + a(n-2) + 2^(n-2), n >= 1, with inputs a(-1) = 0, a(0) = 1/2.

%F (End)

%F E.g.f.: (2*exp(-x) + exp(2*x)*(7 + 6*x) - 9)/18. - _Stefano Spezia_, Feb 19 2020

%p A127984:=n->(n/3 + 7/9)*2^(n - 1) + (-1)^n/9; seq(A127984(n), n=1..50); # _Wesley Ivan Hurt_, Mar 14 2014

%t Table[(n/3 + 7/9)2^(n - 1) + (-1)^n/9, {n, 50}] (* _Artur Jasinski_ *)

%t CoefficientList[Series[(1 - 2 x^2) / ((-1 + 2 x)^2 (1 + x)), {x, 0, 40}], x] (* _Vincenzo Librandi_, Jun 15 2017 *)

%o (Magma) [(n/3+7/9)*2^(n-1)+(-1)^n/9: n in [1..35]]; // _Vincenzo Librandi_, Jun 15 2017

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

%K nonn,easy

%O 1,2

%A _Artur Jasinski_, Feb 09 2007