A003665 a(n) = 2^(n-1)*( 2^n + (-1)^n ).

1, 1, 10, 28, 136, 496, 2080, 8128, 32896, 130816, 524800, 2096128, 8390656, 33550336, 134225920, 536854528, 2147516416, 8589869056, 34359869440, 137438691328, 549756338176, 2199022206976, 8796095119360, 35184367894528, 140737496743936, 562949936644096, 2251799847239680

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy

Comments

Binomial transform of expansion of cosh(3*x), the aerated version of A001019, 1,0,9,0,81,0,729,... - Paul Barry, Apr 05 2003

Alternatively: start with the fraction 1/1, take the numerators of fractions built according to the rule: add top and bottom to get the new bottom, add top and 9 times the bottom to get the new top. The limit of the sequence of fractions used to generate this sequence is sqrt(9). - Cino Hilliard, Sep 25 2005

This sequence also gives the number of ordered pairs of subsets (A, B) of {1, 2, ..., n} such that |A u B| is even. (Here "u" stands for the set-theoretic union.) The special case n = 13 can be found as in CRUX Problem 3257. - Walther Janous (walther.janous(AT)tirol.com), Mar 01 2008

For n > 0, a(n) is term (1,1) in the n-th power of the 2 X 2 matrix [1,3; 3,1]. - Gary W. Adamson, Aug 06 2010

a(n) is the number of compositions of n when there are 1 type of 1 and 9 types of other natural numbers. - Milan Janjic, Aug 13 2010

a(n) = ((1+3)^n+(1-3)^n)/2. In general, if b(0),b(1),... is the k-th binomial transform of the sequence ((3^n+(-3)^n)/2), then b(n) = ((k+3)^n+(k-3)^n)/2. More generally, if b(0),b(1),... is the k-th binomial transform of the sequence ((m^n+(-m)^n)/2), then b(n) = ((k+m)^n+(k-m)^n)/2. See A034494, A081340-A081342, A034659. - Charlie Marion, Jun 25 2011

Pisano period lengths: 1, 1, 1, 1, 4, 1, 6, 1, 1, 4, 5, 1, 12, 6, 4, 1, 8, 1, 9, 4, ... - R. J. Mathar, Aug 10 2012

Starting with offset 1 the sequence is the INVERT transform of (1, 9, 9, 9, ...). - Gary W. Adamson, Aug 06 2016

References

• John Derbyshire, Prime Obsession, Joseph Henry Press, April 2004, p. 16.
• M. Gardner, Riddles of Sphinx, M.A.A., 1987, p. 145.

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• R. K. Guy, s-Additive sequences, Preprint, 1994. (Annotated scanned copy)
• Bill Sands, Problem 3257, Crux Math. 33 (2007), No.5, p. 298.
• Index entries for linear recurrences with constant coefficients, signature (2,8).

Crossrefs

Cf. A001019, A001045, A014551, A078008, A098158.

Cf. A034494, A081340-A081342, A034659.

Programs

GAP

List([0..30], n-> 2^(n-1)*(2^n +(-1)^n)); # G. C. Greubel, Aug 02 2019

Magma

[2^(n-1)*( 2^n + (-1)^n ): n in [0..30]]; // Vincenzo Librandi, Aug 19 2011

Maple

A003665:=n->2^(n-1)*( 2^n + (-1)^n ): seq(A003665(n), n=0..30); # Wesley Ivan Hurt, Apr 28 2017

Mathematica

CoefficientList[Series[(1+8x)/(1-2x-8x^2), {x,0,30}], x] (* or *)
LinearRecurrence[{2,8}, {1,1}, 30] (* Robert G. Wilson v, Sep 18 2013 *)

PARI

a(n)=2^(n-1)*( 2^n + (-1)^n );

Sage

[2^(n-1)*(2^n +(-1)^n) for n in (0..30)] # G. C. Greubel, Aug 02 2019

Formula

From Paul Barry, Mar 01 2003: (Start)

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

a(n) = (4^n + (-2)^n)/2.

G.f.: (1-x)/((1+2*x)*(1-4*x)). (End)

From Paul Barry, Apr 05 2003: (Start)

a(n) = Sum_{k=0..floor(n/2)} binomial(n, 2*k)*9^k.

E.g.f. exp(x)*cosh(3*x). (End)

a(n) = (A078008(n) + A001045(n+1))*2^(n-1) = A014551(n)*2^(n-1). - Paul Barry, Feb 12 2004

Given a(0)=1, b(0)=1 then for i=1, 2, ..., a(i)/b(i) = (a(i-1) + 9*b(i-1)) / (a(i-1) + b(i-1)). - Cino Hilliard, Sep 25 2005

a(n) = Sum_{k=0..n} A098158(n,k)*9^(n-k). - Philippe Deléham, Dec 26 2007

a(n) = ((1+sqrt(9))^n + (1-sqrt(9))^n)/2. - Al Hakanson (hawkuu(AT)gmail.com), Dec 08 2008

If p[1]=1, and p[i]=9, (i>1), and if A is Hessenberg matrix of order n defined by: A[i,j]=p[j-i+1], (i<=j), A[i,j]=-1, (i=j+1), and A[i,j]=0 otherwise. Then, for n>=1, a(n)=det(A). - Milan Janjic, Apr 29 2010

G.f.: G(0)/2, where G(k) = 1 + 1/(1 - x*(9*k-1)/(x*(9*k+8) - 1/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 28 2013

Extensions

Entry revised by N. J. A. Sloane, Nov 22 2006