A136252 a(n) = a(n-1) + 2*a(n-2) - 2*a(n-3).

1, 3, 5, 9, 13, 21, 29, 45, 61, 93, 125, 189, 253, 381, 509, 765, 1021, 1533, 2045, 3069, 4093, 6141, 8189, 12285, 16381, 24573, 32765, 49149, 65533, 98301, 131069, 196605, 262141, 393213, 524285, 786429, 1048573, 1572861, 2097149, 3145725, 4194301, 6291453, 8388605

Offset: 0

Author

Paul Curtz, Mar 17 2008

Keywords

• nonn
• easy

Comments

For n >= 2, number of n X n arrays with values that are squares of integers, having all 2 X 2 subblocks summing to 4. - R. H. Hardin, Apr 03 2009

Number of moves required in 4-peg Tower of Hanoi solution using a (suboptimal) recursive algorithm: Move (n-2) disks, move bottom 2 disks, move (n-2) disks. Cf. A007664. - Toby Gottfried, Nov 29 2010

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000
• Index entries for linear recurrences with constant coefficients, signature (1,2,-2).

Crossrefs

Same recurrence as in A135530.

Partial sums of A163403.

A060482 without the term 2.

Cf. A007664 (Optimal 4-peg Tower of Hanoi).

The following sequences are all essentially the same, in the sense that they are simple transformations of each other, with A029744 = {s(n), n>=1}, the numbers 2^k and 3*2^k, as the parent: A029744 (s(n)); A052955 (s(n)-1), A027383 (s(n)-2), A354788 (s(n)-3), A347789 (s(n)-4), A209721 (s(n)+1), A209722 (s(n)+2), A343177 (s(n)+3), A209723 (s(n)+4); A060482, A136252 (minor differences from A354788 at the start); A354785 (3*s(n)), A354789 (3*s(n)-7). The first differences of A029744 are 1,1,1,2,2,4,4,8,8,... which essentially matches eight sequences: A016116, A060546, A117575, A131572, A152166, A158780, A163403, A320770. The bisections of A029744 are A000079 and A007283. - N. J. A. Sloane, Jul 14 2022

Programs

Maple

a:=proc(n) options operator,arrow: 2^((1/2)*n-1)*(4+4*(-1)^n+3*sqrt(2)*(1-(-1)^n))-3 end proc: seq(a(n),n=0..40); # Emeric Deutsch, Mar 31 2008

Mathematica

LinearRecurrence[{1, 2, -2}, {1, 3, 5}, 100] (* G. C. Greubel, Feb 18 2017 *)

PARI

x='x+O('x^50); Vec((1+2*x)/((1-x)*(1-2*x^2))) \\ G. C. Greubel, Feb 18 2017

Formula

a(n) = 2^((1/2)*n-1)*(4 + 4(-1)^n + 3*sqrt(2)*(1-(-1)^n)) - 3. - Emeric Deutsch, Mar 31 2008

G.f.: (1+2*x)/((1-x)*(1-2*x^2)). - Jaume Oliver Lafont, Aug 30 2009

a(n) = 2*a(n-2) + 3; first differences are powers of 2, occurring in pairs. - Toby Gottfried, Nov 29 2010

a(n) = A027383(n+1) - 1. - Jason Kimberley, Nov 01 2011

a(2n+1) = (a(2n) + a(2n+2))/2. - Richard R. Forberg, Nov 30 2013

E.g.f.: 4*cosh(sqrt(2)*x) + 3*sqrt(2)*sinh(sqrt(2)*x) - 3*cosh(x) - 3*sinh(x). - Stefano Spezia, May 13 2023

Extensions

Edited by N. J. A. Sloane, Apr 18 2008

More terms from Emeric Deutsch, Mar 31 2008