A002535 a(n) = 2*a(n-1) + 9*a(n-2), with a(0)=a(1)=1.

1, 1, 11, 31, 161, 601, 2651, 10711, 45281, 186961, 781451, 3245551, 13524161, 56258281, 234234011, 974792551, 4057691201, 16888515361, 70296251531, 292589141311, 1217844546401, 5068991364601, 21098583646811, 87818089575031, 365523431971361, 1521409670118001, 6332530227978251

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy

Comments

Binomial transform of [1, 0, 10, 0, 100, 0, 1000, 0, 10000, 0, ...]=: powers of 10 (A011557) with interpolated zeros. Inverse binomial transform of A084132. - Philippe Deléham, Dec 02 2008

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

References

• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
• A. Tarn, Approximations to certain square roots and the series of numbers connected therewith, Mathematical Questions and Solutions from the Educational Times, 1 (1916), 8-12.

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
• Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
• Albert Tarn, Approximations to certain square roots and the series of numbers connected therewith [Annotated scanned copy]
• Index entries for linear recurrences with constant coefficients, signature (2,9).

Crossrefs

Cf. A002534 (partial sums), A111015 (primes).

Cf. A011557, A084132, A098158.

Programs

GAP

a:=[1,1];; for n in [3..30] do a[n]:=2*a[n-1]+9*a[n-2]; od; a; # G. C. Greubel, Aug 02 2019

Magma

[Ceiling((1+Sqrt(10))^n/2+(1-Sqrt(10))^n/2): n in [0..30]]; // Vincenzo Librandi, Aug 15 2011

Magma

I:=[1,1]; [n le 2 select I[n] else 2*Self(n-1)+9*Self(n-2): n in [1..30]]; // G. C. Greubel, Aug 02 2019

Maple

A002535:=(-1+z)/(-1+2*z+9*z**2); # conjectured by Simon Plouffe in his 1992 dissertation

Mathematica

Table[ MatrixPower[{{1, 2}, {5, 1}}, n][[1,1]],{n, 0, 30}] (* Vladimir Joseph Stephan Orlovsky, Feb 20 2010 *)
a[n_] := Simplify[((1 + Sqrt[10])^n + (1 - Sqrt[10])^n)/2]; Array[a, 30, 0] (* Or *)
CoefficientList[Series[(1+9x)/(1-2x-9x^2), {x,0,30}], x] (* Or *)
LinearRecurrence[{2, 9}, {1, 1}, 30] (* Robert G. Wilson v, Sep 18 2013 *)

PARI

my(x='x+O('x^30)); Vec((1-x)/(1-2*x-9*x^2)) \\ G. C. Greubel, Aug 02 2019

PARI

my(p=Mod('x,'x^2-2*'x-9)); a(n) = vecsum(Vec(lift((p^n)))); \\ Kevin Ryde, Jan 28 2023

Sage

((1-x)/(1-2*x-9*x^2)).series(x, 30).coefficients(x, sparse=False) # G. C. Greubel, Aug 02 2019

Formula

From Paul Barry, May 16 2003: (Start)

a(n) = ((1+sqrt(10))^n + (1-sqrt(10))^n)/2.

G.f.: (1-x)/(1-2*x-9*x^2).

E.g.f.: exp(x)*cosh(sqrt(10)*x). (End)

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

If p[1]=1, and p[i]=10,(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