A048573 a(n) = a(n-1) + 2*a(n-2), a(0)=2, a(1)=3.

2, 3, 7, 13, 27, 53, 107, 213, 427, 853, 1707, 3413, 6827, 13653, 27307, 54613, 109227, 218453, 436907, 873813, 1747627, 3495253, 6990507, 13981013, 27962027, 55924053, 111848107, 223696213, 447392427, 894784853, 1789569707

Offset

0,1

Comments

Number of positive integers requiring exactly n signed bits in the modified non-adjacent form representation. - Ralf Stephan, Aug 02 2003

The n-th entry (n>1) of the sequence is equal to the 1,1-entry of the n-th power of the unnormalized 4 X 4 Haar matrix: [1 1 1 0 / 1 1 -1 0 / 1 1 0 1 / 1 1 0 -1]. - Simone Severini, Oct 27 2004

Pisano period lengths: 1, 1, 6, 2, 2, 6, 6, 2, 18, 2, 10, 6, 12, 6, 6, 2, 8, 18, 18, 2, ... - R. J. Mathar, Aug 10 2012

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

Wieb Bosma, Signed bits and fast exponentiation, Journal de théorie des nombres de Bordeaux, Vol. 13, No. 1 (2001), pp. 27-41.

Karl Dilcher and Larry Ericksen, Continued fractions and Stern polynomials, Ramanujan Journal 45.3 (2018): 659-681. See Table 2.

Karl Dilcher and Hayley Tomkins, Square classes and divisibility properties of Stern polynomials, Integers, Vol. 18 (2018), Article #A29.

Petro Kosobutskyy, The Collatz problem as a reverse n->0 problem on a graph tree formed from theta*2^n Jacobsthal-type numbers, arXiv:2306.14635 [math.GM], 2023.

Petro Kosobutskyy and Dariia Rebot, Collatz conjecture 3n+/-1 as a Newton binomial problem, Comp. Des. Sys. Theor. Prac., Lviv Nat'l Polytech. Univ. (Ukraine 2023) Vol. 5, No. 1, 137-145. See p. 140.

Saad Mneimneh, Simple Variations on the Tower of Hanoi to Guide the Study of Recurrences and Proofs by Induction, Department of Computer Science, Hunter College, CUNY, 2019.

Sam Northshield, Stern's diatomic sequence 0, 1, 1, 2, 1, 3, 2, 3, 1, 4, ..., Amer. Math. Monthly, Vol. 117, No. 7 (2010), pp. 581-598.

Index entries for linear recurrences with constant coefficients, signature (1,2).

Formula

G.f.: (2 + x) / (1 - x - 2*x^2).

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

a(n) = 2^(n+1) - A001045(n).

a(n) = A084170(n)+1 = abs(A083581(n)-3) = A081254(n+1) - A081254(n) = A084214(n+2)/2.

a(n) = 2*A001045(n+1) + A001045(n) (note that 2 is the limit of A001045(n+1)/A001045(n)). - Paul Barry, Sep 14 2009

Let A be the Hessenberg matrix of order n, defined by: A[1,j]=1, A[i,i]:=-3, A[i,i-1]=-1, and A[i,j]=0 otherwise. Then, for n>=1, a(n-1)=-charpoly(A,-1). - Milan Janjic, Jan 27 2010

Equivalently, with different offset, a(n) = b(n+1) with b(0)=1 and b(n) = Sum_{i=0..n-1} (-1)^i (1 + (-1)^i b(i)). - Olivier Gérard, Jul 30 2012

a(n) = A000975(n-2)*10 + 5 + 2*(-1)^(n-2), a(0)=2, a(1)=3. - Yuchun Ji, Mar 18 2019

a(n+1) = Sum_{i=0..n} a(i) + 1 + (1-(-1)^n)/2, a(0)=2. - Yuchun Ji, Apr 10 2019

a(n) = 2^n + J(n+1) = J(n+2) + J(n+1) - J(n), where J is A001045. - Yuchun Ji, Apr 10 2019

a(n) = A001045(n+2) + A078008(n) = A062510(n+1) - A078008(n+1) = (A001045(n+2) + A062510(n+1))/2 = A014551(n) + 2*A001045(n). - Paul Curtz, Jul 14 2021

From Thomas Scheuerle, Jul 14 2021: (Start)

a(n) = A083322(n) + A024493(n).

a(n) = A127978(n) - A102713(n).

a(n) = A130755(n) - A166249(n).

a(n) = A007679(n) + A139763(n).

a(n) = A168642(n) XOR A007283(n).

a(n) = A290604(n) + A083944(n). (End)

From Paul Curtz, Jul 21 2021: (Start)

a(n) = 5*A001045(n) - A280560(n+1) = abs(A140360(n+1)) - A280560(n+1).

a(n) = 2^n + A001045(n+1) = A001045(n+3) - A000079(n).

a(n) = A001045(n+4) - A340627(n). (End)

a(n) = A001045(n+5) - A005010(n).

a(n+1) + a(n) = a(n+2) - a(n) = 5*2^n. - Michael Somos, Feb 22 2023

Example

G.f. = 2 + 3*x + 7*x^2 + 13*x^3 + 27*x^4 + 53*x^5 + 107*x^6 + 213*x^7 + 427*x^8 + ...

Mathematica

LinearRecurrence[{1, 2}, {2, 3}, 40] (* Harvey P. Dale, Dec 11 2017 *)

Prog

(PARI) {a(n) = if( n<0, 0, (5*2^n + (-1)^n) / 3)};
(PARI) {a(n) = if (n<0 , 0, if( n<2, n+2, a(n-1) + 2*a(n-2)))};
(Magma) [(5*2^n+(-1)^n)/3: n in [0..35]]; // Vincenzo Librandi, Jul 05 2011
(Sage) [(5*2^n+(-1)^n)/3 for n in range(35)] # G. C. Greubel, Apr 10 2019

Crossrefs

Cf. A084214 (first differences).

Cf. A001045, A014551, A024493, A062510.

Cf. A007283, A007679, A078008, A081254.

Cf. A083322, A083944, A083581, A084170.

Cf. A102713, A127978, A130755, A139763.

Cf. A140360, A140966, A166249, A168642.

Cf. A280560, A290604, A340627.

Sequence in context: A256494 A344432 A088172 * A221834 A006946 A074129

Adjacent sequences: A048570 A048571 A048572 * A048574 A048575 A048576

Keyword

nonn,easy

Author

Michael Somos, Jun 17 1999

Extensions

Formula of Milan Janjic moved here from wrong sequence by Paul D. Hanna, May 29 2010

Status

approved