A168642 -id:A168642 - 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

A171477 a(n) = 6a(n-1) - 8a(n-2) + 1 for n > 1; a(0) = 1, a(1) = 7.

Original entry on oeis.org

1, 7, 35, 155, 651, 2667, 10795, 43435, 174251, 698027, 2794155, 11180715, 44731051, 178940587, 715795115, 2863245995, 11453115051, 45812722347, 183251413675, 733006703275, 2932028910251, 11728119835307, 46912487729835

Offset: 0

Klaus Brockhaus, Dec 09 2009

a(n) = A006095(n+2).
Second binomial transform of A168642.
Essentially partial sums of A006516.

Vincenzo Librandi, Table of n, a(n) for n = 0..500
Index entries for linear recurrences with constant coefficients, signature (7, -14, 8).

Cf. A006095 (Gaussian binomial coefficient [n, 2] for q=2), A168642 ((8*2^n+(-1)^n)/3, a(0)=1), A006516 (2^(n-1)*(2^n-1)), A171472, A171473.

[(8*4^n-6*2^n+1)/3: n in [0..30]]; // Vincenzo Librandi, Jul 18 2011

{m=23; v=concat([1, 7], vector(m-2)); for(n=3, m, v[n]=6*v[n-1]-8*v[n-2]+1); v}

a(n) = (8*4^n-6*2^n+1)/3.
G.f.: 1/((1-x)*(1-2*x)*(1-4*x)).
a(n) = A139250(2^(n+1) - 1). - Omar E. Pol, Dec 20 2012

A169969 Locations of row maxima in "crushed" version of Stern's diatomic array.

Original entry on oeis.org

1, 3, 5, 7, 11, 13, 21, 27, 43, 53, 85, 107, 171, 213, 341, 427, 683, 853, 1365, 1707, 2731, 3413, 5461, 6827, 10923, 13653, 21845, 27307, 43691, 54613, 87381, 109227, 174763, 218453, 349525, 436907, 699051, 873813, 1398101, 1747627, 2796203, 3495253, 5592405

Offset: 1

N. J. A. Sloane, Aug 08 2010

From Michel Marcus, Jan 22 2015: (Start)
The Stern's diatomic array begins (see A049456).
  1...............................1
  1...............2...............1
  1.......3.......2.......3.......1
  1...4...3...5...2...5...3...4...1
  1.5.4.7.3.8.5.7.2.7.5.8.3.7.4.5.1
  ...
The "crushed" version is obtained by removing the right column, and then squeezing everything to the left.
  1;
  1, 2;
  1, 3, 2, 3;
  1, 4, 3, 5, 2, 5, 3, 4;
  1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5;
  ...
This gives sequence 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, ... (cf. A002487).
The "crushed" array row maxima are: 1, 2, 3, 5, 8, ... (cf. A000045).
The indices of these values in A002487 are 1, 3, 5, 7, 11, ... : this sequence.
Note, for instance, that for 3rd row, the maximum which is 3, appears twice, at indices 5 and 7, giving 2 terms for this sequence.
(End)

			G.f. = x + 3*x^2 + 5*x^3 + 7*x^4 + 11*x^5 + 13*x^6 + 21*x^7 + 27*x^8 + 43*x^9 + ...

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 (0,1,0,2).

Cf. A000079, A026644, A048573, A049456, A084170, A168642.

a[n_] := a[n] = If[n <= 5, {1, 3, 5, 7, 11}[[n]], a[n-2] + 2a[n-4]]; Array[a, 42] (* Jean-François Alcover, Dec 11 2016 *)

fusc(n)=local(a=1, b=0); while(n>0, if(bitand(n, 1), b+=a, a+=b); n>>=1); b; \\ from A002487
lista(nn) = {nb = 2^(nn+1)-1; vall = vector(nb, n, fusc(n)); for (n=1, nn, vmax = 0; for (j=2^(n-1), 2^n-1, if (vall[j] > vmax, vmax = vall[j]);); for (j=2^(n-1), 2^n-1, if (vall[j] == vmax, print1(j, ", "));););} \\ Michel Marcus, Jan 22 2015

a(2n+1) + a(2n+2) = 3*2^(n+1), n>0 . - Yosu Yurramendi, Jun 29 2016
a(2n+3) = 3*2^(n+1) - a(n); a(2n+4) = 3*2^(n+1) + a(n), n>=0, a(0)=0 (new term), a(1)=1, a(2)=3 . - Yosu Yurramendi, Jun 29 2016
G.f.: x*(1 + 3*x + 4*x^2 + 4*x^3 + 4*x^4)/((1 + x^2)*(1 - 2*x^2)). - Ilya Gutkovskiy, Jun 29 2016
For n>1, a(n) = (2^(n/2 - 1)*(5 + 4*sqrt(2) + (-1)^n*(5 - 4*sqrt(2))) + cos(Pi*n/2) + sin(Pi*n/2))/3. - Vaclav Kotesovec, Jun 30 2016
a(2n) = a(2n-7) + 3*2^(n-1); a(2n-1) = a(2n-7) - 3*2^(n-1), n>=5 . - Yosu Yurramendi, Jul 06 2016
a(2n-1) = A168642(n), n>0; a(2n) = A048573(n), n>0; a(2n-1) = A026644(n) + 1, n>1; a(2n) = A084170(n) + 1, n>0 . - Yosu Yurramendi, Dec 11 2016

More terms from Michel Marcus, Jan 22 2015

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

A171477 a(n) = 6*a(n-1) - 8*a(n-2) + 1 for n > 1; a(0) = 1, a(1) = 7.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

PARI

Formula

A169969 Locations of row maxima in "crushed" version of Stern's diatomic array.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A171477 a(n) = 6a(n-1) - 8a(n-2) + 1 for n > 1; a(0) = 1, a(1) = 7.