login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons 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

%I

%S 2,3,7,13,27,53,107,213,427,853,1707,3413,6827,13653,27307,54613,

%T 109227,218453,436907,873813,1747627,3495253,6990507,13981013,

%U 27962027,55924053,111848107,223696213,447392427,894784853,1789569707

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

%C Number of positive integers requiring exactly n signed bits in the modified non-adjacent form representation. - _Ralf Stephan_, Aug 02 2003

%C 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

%C 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

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

%H Vincenzo Librandi, <a href="/A048573/b048573.txt">Table of n, a(n) for n = 0..1000</a>

%H W. Bosma, <a href="http://dx.doi.org/10.5802/jtnb.301">Signed bits and fast exponentiation</a>, Journal de théorie des nombres de Bordeaux, 13 no. 1 (2001), p. 27-41,

%H Karl Dilcher, Hayley Tomkins, <a href="http://math.colgate.edu/~integers/s29/s29.mail.html">Square classes and divisibility properties of Stern polynomials</a>, Integers (2018) 18, Article #A29.

%H Saad Mneimneh, <a href="http://www.cs.hunter.cuny.edu/~saad/teaching/ToH.pdf">Simple Variations on the Tower of Hanoi to Guide the Study of Recurrences and Proofs by Induction</a>, Department of Computer Science, Hunter College, CUNY, 2019.

%H S. Northshield, <a href="http://dx.doi.org/10.4169/000298910X496714">Stern's diatomic sequence 0, 1, 1, 2, 1, 3, 2, 3, 1, 4, ...</a>, Amer. Math. Monthly, 117 (2010), 581-598.

%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (1,2).

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

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

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

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

%F 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

%F 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

%F 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

%F a(n) = A000975(n-2)*10 + 5 + 2*(-1)^(n-2), a(0)=2, a(1)=3. - _Yuchun Ji_, Mar 18 2019

%F a(n+1) = Sum_{i=0..n} a(i) + 1 + (1-(-1)^n)/2, a(0)=2. - _Yuchun Ji_, Apr 10 2019

%F a(n) = 2^n + J(n+1) = J(n+2) + J(n+1) - J(n), where J is A001045. - _Yuchun Ji_, Apr 10 2019

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

%t LinearRecurrence[{1,2},{2,3},40] (* _Harvey P. Dale_, Dec 11 2017 *)

%o (PARI) {a(n) = if( n<0, 0, (5*2^n + (-1)^n) / 3)}

%o (PARI) {a(n) = if (n<0 ,0, if( n<2, n+2, a(n-1) + 2*a(n-2)))}

%o (MAGMA) [(5*2^n+(-1)^n)/3: n in [0..35]]; // _Vincenzo Librandi_, Jul 05 2011

%o (Sage) [(5*2^n+(-1)^n)/3 for n in range(35)] # _G. C. Greubel_, Apr 10 2019

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

%K nonn,easy

%O 0,1

%A _Michael Somos_, Jun 17 1999

%E Formula of _Milan Janjic_ moved here from wrong sequence by _Paul D. Hanna_, May 29 2010

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 July 8 04:16 EDT 2020. Contains 335504 sequences. (Running on oeis4.)