A140960 -id:A140960 - cp's OEIS frontend

A045883 a(n) = ((3n+1)2^n - (-1)^n)/9.

0, 1, 3, 9, 23, 57, 135, 313, 711, 1593, 3527, 7737, 16839, 36409, 78279, 167481, 356807, 757305, 1601991, 3378745, 7107015, 14913081, 31224263, 65244729, 136081863, 283348537, 589066695, 1222872633, 2535223751, 5249404473, 10856722887, 22429273657, 46290203079

Offset: 0

Edward Early

Without the initial zero, PSumSIGN transform of A001787. - Michael Somos, Jul 10 2003
Number of rises (drops) in the compositions of n+2 with parts in N.
From Michel Lagneau, Jan 13 2012: (Start)
This sequence is connected with the Collatz problem. We consider the array T(i,j) where the i-th row gives the parity trajectory of i, for example for i = 6, the infinite trajectory is 6 -> 3 -> 10 ->5 -> 16 ->8 -> 4 -> 2 -> 1 -> 4 -> 2 -> 1 -> 4->2-> 1 ... and T(6,j) = [0,1,0,1,0,0,0,0,1,0,0,1,...,1,0,0,1,...]. Now, we consider the sum of the digits 1 of each array T(i,j), where
a(1) = sum of the digits "1" of T(i,j), i = 1..2^1 and j = 1;
a(2) = sum of the digits "1" of T(i,j), i = 1..2^2 and j = 1..2;
a(3) = sum of the digits "1" of T(i,j), i = 1..2^3 and j = 1..3;
a(n) = Sum_{i=1..2^n}(Sum_{j=1..n} T(i,j)) = Sum_{i=1..n} A001045(n)*2^(n-i) = convolution of A001045 and A000079 (see the formula below).
The number of digits "0" equals A113861(n) = n*2^n - a(n) because n and 2^n are the dimensions of each array.
An important result is that the ratio r = A113861(n) / A045883(n) tends towards 2 when n tends towards infinity. In other words, when the array tends towards infinity, the ratio r = (number of divisions by 2) / (number of multiplications by 3) tends towards 2, even if there exists divergent trajectories. That is the problem! For each possible divergent infinite trajectory, r < 2 even though the global ratio r is 2.
Conclusion:
1. For each number n with a convergent trajectory T(n,k), k = 1..infinity, or for each row of the array T(i,j), the ratio r tends towards 2 (the proof is easy because the trajectory becomes periodic from a certain index 1001001001...).
2. For each array of dimension n X 2^n, the radio r tends towards 2.
3. If there exists a number n such that the trajectory is divergent, this trajectory is random and r tends towards a real x such that 1 < = r < = x < 2.
4. In order to establish a proof of the Collatz problem from this considerations (if that is possible), it is necessary to prove that a ratio < 2 for an infinite row (or several rows) of an infinite array T(i,j) is incompatible with r = 2, the exact ratio for this array. (End)
a(n) is the distance spectral radius of the dimension-regular generalized recursive circulant graph (commonly known as multiplicative circulant graph) of order 2^n. - John Rafael M. Antalan, Sep 25 2020
Total sum over all compositions of n of the absolute differences between consecutive parts, assuming an initial part 0. - Alois P. Heinz, Apr 30 2025

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
John Rafael M. Antalan and Francis Joseph H. Campeña, Distance eigenvalues and forwarding indices of dimension-regular generalized recursive circulant graph of order power of two and three, arXiv:2009.11608[math.CO], 2020.
M. Archibald, A. Blecher, A. Knopfmacher, and M. E. Mays, Inversions and Parity in Compositions of Integers, J. Int. Seq., Vol. 23 (2020), Article 20.4.1.
Roland Bacher, Chebyshev polynomials, quadratic surds and a variation of Pascal's triangle, arXiv:1509.09054 [math.CO], 2015.
Tomislav Došlić and Biserka Kolarec, On Log-Definite Tempered Combinatorial Sequences, Mathematics (2025) Vol. 13, Iss. 7, 1179.
Silvia Heubach and Toufik Mansour, Counting rises, levels and drops in compositions, arXiv:math/0310197 [math.CO], 2003.
F. K. Hwang, Three versions of a group testing game, SIAM J. Algebraic Discrete Methods 5 (1984), no. 2, 145--153. MR0745434(85d:90120). See p. 151, f(n) (but divide by 2). - _N. J. A. Sloane_, Apr 13 2014
Peter J. Larcombe and Eric J. Fennessey, On a Scaled Balanced-Power Product Recurrence, Fibonacci Quart. 54 (2016), no. 3, 242-246. See Remark 2.2 p. 244.
Peter J. Larcombe, Julius Fergy T. Rabago, and Eric J. Fennessey, On two derivative sequences from scaled geometric mean sequence terms, Palestine Journal of Mathematics (2018) Vol. 7(2), 397-405.
Index entries for linear recurrences with constant coefficients, signature (3,0,-4).

Partial sums of A059570, bisection: A014916.
Row sums of triangle A094953.
Cf. A059260, A127984.
Cf. A000079, A001045, A001787, A045883, A049260, A113861, A140960, A188545.
Cf. A238343, A238344.

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

A045883:=n->((3*n+1)*2^n-(-1)^n)/9; seq(A045883(n), n=0..30); # Wesley Ivan Hurt, Mar 21 2014

nn=31;a=x^2(1-x)/(1-x-2x^2)/(1-2x);b=x^2/(1-2x)^2;Drop[CoefficientList[Series[(b-a)/2,{x,0,nn}],x],2] (* Geoffrey Critzer, Mar 21 2014 *)
CoefficientList[Series[x / ((1 + x) (1 - 2 x)^2), {x, 0, 33}], x] (* Vincenzo Librandi, Jun 15 2017 *)
LinearRecurrence[{3, 0, -4}, {0, 1, 3}, 33] (* Jean-François Alcover, Sep 27 2017 *)

{a(n) = if( n<-1, 0, ((3*n + 1)*2^n - (-1)^n) / 9)};

G.f.: x/((1+x)*(1-2*x)^2).
a(n) = 3*a(n-1) - 4*a(n-3).
Convolution of A001045 and A000079. G.f.: x/((1-2*x)(1-x-2*x^2)). - Paul Barry, May 21 2004
Starting with "1" = triangle A049260 * the odd integers as a vector. - Gary W. Adamson, Mar 06 2012
a(n) = A140960(n)/2. - J. M. Bergot, May 21 2013
From Wolfdieter Lang, Jun 14 2017: (Start)
a(n) = f(n)*2^n, 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/2 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 with f(n) = (3*n+1 - (-1)^n/2^n)/9, n >= 0, by induction.
a(n) = a(n-1) + 2*a(n-2) + 2^(n-1), n >= 0, with input a(-2) = 1/4 and a(-1) = 0. See also A127984. (End)
E.g.f.: (exp(2*x)*(1 + 6*x) - cosh(x) + sinh(x))/9. - Stefano Spezia, Apr 09 2025
a(n) = Sum_{k=0..n+2} k * A238343(n+2,k). - Alois P. Heinz, Apr 30 2025

Simpler description from Vladeta Jovovic, Jul 18 2002

A232600 a(n) = Sum_{k=0..n} k^p*q^k, where p=1, q=-2.

Original entry on oeis.org

0, -2, 6, -18, 46, -114, 270, -626, 1422, -3186, 7054, -15474, 33678, -72818, 156558, -334962, 713614, -1514610, 3203982, -6757490, 14214030, -29826162, 62448526, -130489458, 272163726, -566697074, 1178133390, -2445745266, 5070447502, -10498808946, 21713445774

Offset: 0

Stanislav Sykora, Nov 27 2013

			a(3) = 0^1*2^0 - 1^1*2^1 + 2^1*2^2 - 3^1*2^3 = -18.

Stanislav Sykora, Table of n, a(n) for n = 0..1000
S. Sykora, Finite and Infinite Sums of the Power Series (k^p)(x^k), DOI 10.3247/SL1Math06.002, Section V.
Index entries for linear recurrences with constant coefficients, signature (-3,0,4).

Cf. A045883, A140960 (absolute values), A059841 (p=0, q=-1), A130472 (p=1 ,q=-1), A089594 (p=2, q=-1), A232599 (p=3, q=-1), A126646 (p=0, q=2), A036799 (p=1, q=2), A036800 (p=q=2), A036827 (p=3, q=2), A077925 (p=0, q=-2), A232601 (p=2, q=-2), A232602 (p=3, q=-2), A232603 (p=2, q=-1/2), A232604 (p=3, q=-1/2).

Cf. A045883.

[2*((-2)^n*(3*n+1) -1)/9: n in [0..30]]; // G. C. Greubel, Mar 31 2021

A232600:= n-> 2*((-2)^n*(3*n+1) -1)/9; seq(A232600(n), n=0..30); # G. C. Greubel, Mar 31 2021

Table[2((3n+1)(-2)^n -1)/9, {n, 0, 30}] (* Bruno Berselli, Nov 28 2013 *)

PARI
```
a(n)=-((3*n+1)*(-2)^(n+1)+2)/9;
```

[2*((-2)^n*(3*n+1) -1)/9 for n in (0..30)] # G. C. Greubel, Mar 31 2021

a(n) = 2*( (3*n+1)*(-2)^n - 1 )/9.
abs(a(n)) = 2*A045883(n) = A140960(n).
From Bruno Berselli, Nov 28 2013: (Start)
G.f.: -2*x / ((1 - x)*(1 + 2*x)^2). [corrected by Georg Fischer, May 11 2019]
a(n) = -3*a(n-1) +4*a(n-3). (End)
From G. C. Greubel, Mar 31 2021: (Start)
E.g.f.: (2/9)*(-exp(x) + (1-6*x)*exp(-2*x)).
a(n) = 2*(-1)^n*A045883(n). (End)

A172481 a(n) = (3n2^n+2^(n+4)+2*(-1)^n)/18.

Original entry on oeis.org

1, 2, 5, 11, 25, 55, 121, 263, 569, 1223, 2617, 5575, 11833, 25031, 52793, 111047, 233017, 487879, 1019449, 2126279, 4427321, 9204167, 19107385, 39612871, 82021945, 169636295, 350457401, 723284423, 1491308089, 3072094663, 6323146297, 13004206535, 26724240953

Offset: 0

Paul Curtz, Feb 04 2010

The binomial transform is in A126184.
An elephant sequence, see A175654 and A175655. There are 24 A[5] vectors, with decimal values between 7 and 448, that lead for the corner squares to this sequence. Its companion sequence for the central square is A175656. Furthermore there are 36 A[5] vectors, with decimal values between 15 and 480, that lead for the central square to four times this sequence for n >= -1. Its companion sequence for the corner squares is A059570. - Johannes W. Meijer, Aug 15 2010
a(n) is also the number of runs of weakly increasing parts in all compositions of n+1. a(2) = 5: (111), (12), (2)(1), (3). - Alois P. Heinz, Apr 30 2017

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (3,0,-4)

Cf. A059570, A151529, A127984.

[(3*n*2^n+2^(n+4)+2*(-1)^n)/18: n in [0..40]]; // Vincenzo Librandi, Aug 04 2011

Table[(3n 2^n+2^(n+4)+2(-1)^n)/18,{n,0,40}]  (* or *)
CoefficientList[Series[(1-x-x^2)/((1+x)(1-2x)^2), {x,0,40}], x]  (* Harvey P. Dale, Mar 28 2011 *)

a(n)=(3*n*2^n+2^(n+4)+2*(-1)^n)/18 \\ Charles R Greathouse IV, Oct 07 2015

G.f.: (1-x-x^2)/((1+x)*(1-2*x)^2).
a(n) = A001045(n-1)+2*a(n-1), n>0.
a(n)+A139790(n) = 2^(n+1) = A000079(n+1).
a(n) = A139790(n)+A140960(n).
a(n) = A001045(n)+(-1)^n*A084219(n).
a(n) = A127984(n) + 2^(n-1).  Application:  Problem 11623, AMM 119 (2012) 161. - Stephen J. Herschkorn, Feb 11 2012

Definition replaced by explicit formula by R. J. Mathar, Feb 11 2010

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

Extensions

A232600 a(n) = Sum_{k=0..n} k^p*q^k, where p=1, q=-2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

A172481 a(n) = (3*n*2^n+2^(n+4)+2*(-1)^n)/18.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

A045883 a(n) = ((3n+1)2^n - (-1)^n)/9.

A172481 a(n) = (3n2^n+2^(n+4)+2*(-1)^n)/18.