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

%I #126 Jul 22 2024 14:29:17

%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

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

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

%H Wieb 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, Vol. 13, No. 1 (2001), pp. 27-41.

%H Karl Dilcher and Larry Ericksen, <a href="https://doi.org/10.1007/s11139-016-9864-3">Continued fractions and Stern polynomials</a>, Ramanujan Journal 45.3 (2018): 659-681. See Table 2.

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

%H Petro Kosobutskyy, <a href="https://arxiv.org/abs/2306.14635">The Collatz problem as a reverse n->0 problem on a graph tree formed from theta*2^n Jacobsthal-type numbers</a>, arXiv:2306.14635 [math.GM], 2023.

%H Petro Kosobutskyy and Dariia Rebot, <a href="https://doi.org/10.23939/cds2023.01.137">Collatz conjecture 3n+/-1 as a Newton binomial problem</a>, Comp. Des. Sys. Theor. Prac., Lviv Nat'l Polytech. Univ. (Ukraine 2023) Vol. 5, No. 1, 137-145. See p. 140.

%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 Sam 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, Vol. 117, No. 7 (2010), pp. 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

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

%F From _Thomas Scheuerle_, Jul 14 2021: (Start)

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

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

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

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

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

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

%F From _Paul Curtz_, Jul 21 2021: (Start)

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

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

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

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

%F a(n+1) + a(n) = a(n+2) - a(n) = 5*2^n. - _Michael Somos_, Feb 22 2023

%F a(n) = A135318(2*n) + A135318(2*n+1) = A112387(2*n) + A112387(2*n+1). - _Paul Curtz_, Jun 26 2024

%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. A084214 (first differences).

%Y Cf. A001045, A014551, A024493, A062510.

%Y Cf. A007283, A007679, A078008, A081254.

%Y Cf. A083322, A083944, A083581, A084170.

%Y Cf. A102713, A127978, A130755, A139763.

%Y Cf. A140360, A140966, A166249, A168642.

%Y Cf. A280560, A290604, A340627.

%Y Cf. A112387, A135318.

%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