login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A048573 a(n) = a(n-1) + 2*a(n-2), a(0)=2, a(1)=3. 9
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 (list; graph; refs; listen; history; text; internal format)
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

W. Bosma, Signed bits and fast exponentiation, Journal de théorie des nombres de Bordeaux, 13 no. 1 (2001), p. 27-41,

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

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.

S. Northshield, Stern's diatomic sequence 0, 1, 1, 2, 1, 3, 2, 3, 1, 4, ..., Amer. Math. Monthly, 117 (2010), 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

EXAMPLE

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

f1[n_]:=2*n+1; f2[n_]:=2*n-1; a=2; lst={a}; Do[AppendTo[lst, a=f2[a]]; AppendTo[lst, a=f1[a]], {n, 30}]; lst (* Vladimir Joseph Stephan Orlovsky, Feb 07 2010 *)

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

CROSSREFS

Cf. A001045, A081254, A083581, A084170, A084214.

Sequence in context: A024504 A256494 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 16 08:26 EST 2019. Contains 320159 sequences. (Running on oeis4.)