A045883 a(n) = ((3*n+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,3

Comments

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

Links

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

S. Heubach and T. 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, 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).

Formula

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)

Maple

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

Mathematica

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

Prog

(PARI) {a(n) = if( n<-1, 0, ((3*n + 1)*2^n - (-1)^n) / 9)};
(Magma) [((3*n+1)*2^n-(-1)^n)/9: n in [0..35]]; // Vincenzo Librandi, Jun 15 2017

Crossrefs

Partial sums of A059570, bisection: A014916.

Row sums of triangle A094953.

Cf. A059260, A127984.

Sequence in context: A147126 A147212 A341029 * A292329 A133654 A193695

Adjacent sequences: A045880 A045881 A045882 * A045884 A045885 A045886

Keyword

easy,nonn

Author

Edward Early

Extensions

Simpler description from Vladeta Jovovic, Jul 18 2002

Status

approved