A007679 -id:A007679 - cp's OEIS frontend

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

Michael Somos, Jun 17 1999

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

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

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

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.

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

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

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

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

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

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

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

A007910 Expansion of 1/((1-2x)(1+x^2)).

Original entry on oeis.org

1, 2, 3, 6, 13, 26, 51, 102, 205, 410, 819, 1638, 3277, 6554, 13107, 26214, 52429, 104858, 209715, 419430, 838861, 1677722, 3355443, 6710886, 13421773, 26843546, 53687091, 107374182, 214748365, 429496730, 858993459, 1717986918, 3435973837, 6871947674

Offset: 0

Mogens Esrom Larsen (mel(AT)math.ku.dk)

Also describes the location a(n) of the minimal scaling factor when rescaling an FFT of order 2^{n+2} in order to (currently) minimize the arithmetic operation count (Johnson & Frigo, 2007). - Steven G. Johnson (stevenj(AT)math.mit.edu), Dec 27 2006

M. E. Larsen, Summa Summarum, A. K. Peters, Wellesley, MA, 2007; see p. 38.

M. F. Hasler, Table of n, a(n) for n = 0..1000 (in replacement of a(0..999) indexed 1..1000 by Vincenzo Librandi)
M. H. Cilasun, An Analytical Approach to Exponent-Restricted Multiple Counting Sequences, arXiv preprint arXiv:1412.3265 [math.NT], 2014.
M. H. Cilasun, Generalized Multiple Counting Jacobsthal Sequences of Fermat Pseudoprimes, Journal of Integer Sequences, Vol. 19, 2016, #16.2.3.
I. Gessel, Problem 10424, Amer. Math. Monthly, 102 (1995), 70.
S. G. Johnson and M. Frigo, A modified split-radix FFT with fewer arithmetic operations, IEEE Trans. Signal Processing 55 (2007), 111-119.
Kyu-Hwan Lee, Se-jin Oh, Catalan triangle numbers and binomial coefficients, arXiv:1601.06685 [math.CO], 2016.
Index entries for linear recurrences with constant coefficients, signature (2,-1,2).

Cf. A007909, A007679.

[Round(2^(n+2)/5): n in [0..40]]; // Vincenzo Librandi, Jun 21 2011

A007910:=n->(1/5)*(2^(n-1)+2*cos(n*Pi/2)-sin(n*Pi/2)); [seq(V(n),n=0..12)];
seq(round(2^(n+2)/5),n=1..25) # Mircea Merca, Dec 27 2010

CoefficientList[Series[1/((1 - 2 x) (1 + x^2)), {x, 0, 50}], x] (* Vladimir Joseph Stephan Orlovsky, Jun 20 2011 *)
LinearRecurrence[{2,-1,2},{1,2,3},40] (* Harvey P. Dale, Feb 22 2016 *)

a(n)=2^(n+2)\/5 \\ Charles R Greathouse IV, Jun 21 2011

def A007910(n): return ((4<Chai Wah Wu, Apr 17 2025

a(0) = 1, a(2n+1) = 2*a(2n) and a(2n) = 2*a(2n-1) + (-1)^n. [Corrected by M. F. Hasler, Feb 22 2018]
a(n) = (4*2^n+cos(Pi*n/2)+2*sin(Pi*n/2))/5. - Paul Barry, Dec 17 2003
a(n) = 2a(n-1)-a(n-2)+2a(n-3). Sequence equals half its second differences with first term dropped. a(n) + a(n+2) = 2^(n+2). - Paul Curtz, Dec 17 2007
a(n) = round(2^(n+2)/5). - Mircea Merca, Dec 27 2010
a(n) = Sum_{k=0..floor(n/2)} (-1)^k*2^(n-2*k). - Gerry Martens, Oct 15 2022

Entry revised by N. J. A. Sloane, Feb 24 2004

Offset corrected and minor edits by M. F. Hasler, Feb 22 2018

A007909 Expansion of (1-x)/(1-2x+x^2-2x^3).

Original entry on oeis.org

1, 1, 1, 3, 7, 13, 25, 51, 103, 205, 409, 819, 1639, 3277, 6553, 13107, 26215, 52429, 104857, 209715, 419431, 838861, 1677721, 3355443, 6710887, 13421773, 26843545, 53687091, 107374183, 214748365, 429496729, 858993459, 1717986919, 3435973837, 6871947673

Offset: 0

Mogens Esrom Larsen (mel(AT)math.ku.dk)

Equals INVERT transform of (1, 0, 2, 2, 2, ...). - Gary W. Adamson, Apr 28 2009

a(n) is the number of compositions (ordered partitions) of n into parts 1 (one kind), and parts >= 3 of three kinds (no parts 2). - Joerg Arndt, Apr 22 2025

Kenneth Edwards, Michael A. Allen, A new combinatorial interpretation of the Fibonacci numbers squared, Part II, Fib. Q., 58:2 (2020), 169-177.
M. E. Larsen, Summa Summarum, A. K. Peters, Wellesley, MA, 2007; see p. 38.

M. F. Hasler, Table of n, a(n) for n = 0..1000 (in replacement of a(0..999) indexed 1..1000 from Vincenzo Librandi).
Charles K. Cook and Michael R. Bacon, Some identities for Jacobsthal and Jacobsthal-Lucas numbers satisfying higher order recurrence relations, Annales Mathematicae et Informaticae, 41 (2013) pp. 27-39.
Shanzhen Gao, Keh-Hsun Chen, Tackling Sequences From Prudent Self-Avoiding Walks, FCS'14, The 2014 International Conference on Foundations of Computer Science.
I. Gessel, Problem 10424, Amer. Math. Monthly, 102 (1995), 70.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 444
Yüksel Soykan, Properties of Generalized (r, s, t, u)-Numbers, Earthline J. of Math. Sci. (2021) Vol. 5, No. 2, 297-327.
Index entries for linear recurrences with constant coefficients, signature (2,-1,2).

Cf. A005251, A007679, A007910.

I:=[1, 1, 1]; [n le 3 select I[n] else 2*Self(n-1)-Self(n-2)+2*Self(n-3): n in [1..40]]; // Vincenzo Librandi, Jun 17 2012

U:=n->(1/5)*(2^(n+1)+3*cos(n*Pi/2)+sin(n*Pi/2)); [seq(U(n),n=0..50)];

CoefficientList[Series[(1-x)/(1-2*x+x^2-2*x^3),{x,0,40}],x] (* Vincenzo Librandi, Jun 17 2012 *)
LinearRecurrence[{2,-1,2},{1,1,1},40] (* Harvey P. Dale, Jul 26 2016 *)

a(n)=2^(n+1)\5+(n%4<2) \\ M. F. Hasler, Feb 22 2018

def A007909(n): return (2<Chai Wah Wu, Apr 22 2025

G.f.: (1-x)/(1-2*x+x^2-2*x^3).
a(n) = (1/5)*(2^(n+1)+3*cos(n*Pi/2)+sin(n*Pi/2)).
a(n) = Sum_{k=0..floor((n-1)/3)} binomial(n-k-1, 2*k)*2^k. - Paul Barry, Sep 16 2004
a(n) = (1/5)*(2^(n+1) + (-1)^[(n+1)/2] + 2*(-1)^[n/2]). - Ralf Stephan, Jun 09 2005
a(n) = 2*a(n-1)-a(n-2)+2*a(n-3). Sequence is identical to its half second differences from the second term; a(n)+a(n+2)=2^(n+1). - Paul Curtz, Dec 17 2007
a(n+1) = (2^n)*Sum_{k=1..n} (-1)^floor(k/2)/2^k. - Yalcin Aktar, Jul 20 2008

Offset corrected by M. F. Hasler, Feb 22 2018

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

Sage

Formula

Extensions

A007910 Expansion of 1/((1-2*x)*(1+x^2)).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python

Formula

Extensions

A007909 Expansion of (1-x)/(1-2*x+x^2-2*x^3).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python

Formula

Extensions

A007910 Expansion of 1/((1-2x)(1+x^2)).

A007909 Expansion of (1-x)/(1-2x+x^2-2x^3).