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, 3579139413, 7158278827, 14316557653

Offset: 0

Author

Michael Somos, Jun 17 1999

Keywords

• nonn
• easy

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

For n >= 1, a(n) is the number of ways to tile a strip of length n+2 with blue squares and blue and red dominos, with the restriction that the first two tiles must be the same color. - Guanji Chen and Greg Dresden, Jul 15 2024

Examples

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

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

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.

Cf. A112387, A135318.

Programs

Magma

[(5*2^n+(-1)^n)/3: n in [0..35]]; // Vincenzo Librandi, Jul 05 2011

Mathematica

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

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)))};

Sage

[(5*2^n+(-1)^n)/3 for n in range(35)] # G. C. Greubel, Apr 10 2019

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

a(n) = A135318(2*n) + A135318(2*n+1) = A112387(2*n) + A112387(2*n+1). - Paul Curtz, Jun 26 2024

E.g.f.: (cosh(x) + 5*cosh(2*x) - sinh(x) + 5*sinh(2*x))/3. - Stefano Spezia, May 18 2025

Extensions

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