# [seqfan] Few INVERT transforms requested. A000045 --> A000129, how ?

Antti Karttunen Antti.Karttunen at iki.fi
Mon Dec 8 10:49:08 CET 2003

```Dear Maple-users!

If any of you have Maple and Neil's transform-package easily at hand
(see http://www.research.att.com/~njas/sequences/transforms.txt )
could you compute for me the following transforms:

INVERT([1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]);

Here the sequence in brackets is A019590, and the result SHOULD BE A000045,
the Fibonacci Numbers, which is obvious when one thinks about
the combinatorial interpretation of INVERT, as explained in:
http://www.research.att.com/~njas/doc/eigen.ps
or:
http://www.research.att.com/~njas/doc/eigen.pdf

(but I'm not sure about by my thoughts until I see the experimental data!)

and also this:

INVERT([1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946]);
(i.e. our Dear  Fibonaccis)

and with different offsets:

INVERT([0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946]);

INVERT([1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946]);

Should some of these result A000129?
And if you can prove it with g.f.ology or with some combinatorial identity,
then even better.

http://www.research.att.com/projects/OEIS?Anum=A000129
Sequence <http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/showtabl.cgi?A=A000129&format=4&height=0&seq=,0,1,2,5,12,29,70,169,408,985,2378,5741,13860,33461,80782,195025,470832,1136689,2744210,6625109,15994428,38613965,93222358,225058681,543339720,1311738121,3166815962,7645370045,18457556052,44560482149>:  0,1,2,5,12,29,70,169,408,985,2378,5741,13860,33461,80782,
195025,470832,1136689,2744210,6625109,15994428,38613965,
93222358,225058681,543339720,1311738121,3166815962,
7645370045,18457556052,44560482149
Name:      Pell numbers: a(0) = 0, a(1) = 1; for n > 1, a(n) = 2*a(n-1) + a(n-2).
Also denominators of continued fraction convergents to sqrt(2).
Comments:  Number of lattice paths from (0,0) to the line x=n-1 consisting of
U=(1,1), D=(1,-1), and H=(2,0) steps (i.e. left factors of Grand
Schroder paths); for example, a(3)=5, counting the paths H, UD, UU, DU,
and DD. - Emeric Deutsch (deutsch(AT)duke.poly.edu), Oct 27 2002
a(2*n+1) with b(2*n+1):= A001333 <http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001333>(2*n+1), n>=0, give all
(positive integer) solutions to Pell equation b^2 - 2*a^2 = -1.
a(2*n) with b(2*n):= A001333 <http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001333>(2*n), n>=1, give all (positive
integer) solutions to Pell equation b^2 - 2*a^2 = +1 (see Emerson
reference).
Bisection: a(2*n+1)= T(2*n+1,sqrt(2))/sqrt(2)= A001653 <http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001653>(n),
n>=0, and a(2*n)= 2*S(n-1,6)= 2*A001109 <http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001109>(n),n>=0, with
T(n,x), resp. S(n,x), Chebyshev's polynomials of the first,resp.
second kind. S(-1,x)=0. See A053120 <http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A053120>, resp. A049310 <http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A049310>. - W. Lang
(wolfdieter.lang(AT)physik.uni-karlsruhe.de), Jan 10 2003
etc....

If I try to check it "empirically" with superseeker, I get very strange results,
like, if I seek with
lookup 0 1 2 5 12 29 70 169 408 985 2378 5741 13860 33461 80782 195025 470832 1136689 2744210

Transformation T109 gave a match with:
%I A034008
%S A034008 1,0,1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,
%T A034008 65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,
%U A034008 33554432,67108864,134217728,268435456,536870912,1073741824,2147483648
%N A034008 [2^|n-1|/2].
%C A034008 Powers of 2 with additional first two terms.
%F A034008 a(n) = 2^(n-2), n >= 2; a(0)=1, a(1)=0; G.f.: (1-x)^2/(1-2*x).
%o A034008 (PARI) a(n)=if(n<2,n==0,2^(n-2))
%Y A034008 First differences of 2^(n-1) (A011782). Cf. A011782.
%Y A034008 Adjacent sequences: A034005 A034006 A034007 this_sequence A034009 A034010 A034011
%Y A034008 Sequence in context: A056767 A008863 A011782 this_sequence A084633 A000079 A050732
%K A034008 easy,nonn
%O A034008 0,4
%A A034008 Wolfdieter Lang (wolfdieter.lang(AT)physik.uni-karlsruhe.de)
%E A034008 Additional comments from Barry E. Williams, May 27 2000 and from Michael Somos, Jun 18, 2002

Transformation T108 gave a match with:
%I A080953
%S A080953 0,1,2,6,16,44,120,328,896,2448,6688,18272,49920,136384,372608,1017984,
%T A080953 2781184,7598336,20759040,56714752,154947584,423324672,1156544512,
%U A080953 3159738368,8632565760,23584608256,64434348032,176037912576
%N A080953 a(n)=2a(n-1)+2a(n), a(0)=0, a(1)=1.
%C A080953 First differences are given by A026150.
%F A080953 a(n)=((1 + sqrt(3))^n - (1 - sqrt(3))^n)/(2*sqrt(3)) a(n)=Sum{k=0..n,Binomial(n,2k+1)3^k} G.f.: x/(1-2x-2x^2)
%F A080953 Binomial transform of expansion of sinh(sqrt(3)x)/sqrt(3) (0,1,0,3,0,9,...). E.g.f.: exp(x)sinh(sqrt(3)x)/sqrt(3). - Paul Barry (pbarry(AT)wit.ie), May 09 2003
%Y A080953 Cf. A002605, A028859.
%Y A080953 Adjacent sequences: A080950 A080951 A080952 this_sequence A080954 A080955 A080956
%Y A080953 Sequence in context: A027994 A027068 A002605 this_sequence A026134 A074413 A055544
%K A080953 easy,nonn
%O A080953 0,3
%A A080953 Paul Barry (pbarry(AT)wit.ie), Feb 26 2003

but if with
lookup 1 1 2 5 12 29 70 169 408 985 2378 5741 13860 33461 80782 195025 470832 1136689 2744210

then only:

Transformation T108 gave a match with:
%I A052963
%S A052963 1,2,5,14,40,115,331,953,2744,7901,22750,65506,188617,543101,1563797,
%T A052963 4502774,12965221,37331866,107492824,309513251,891207887,2566130837,
%U A052963 7388879260,21275429893,61260158842,176391597266,507899361905
%N A052963 A simple regular expression.
%H A052963 INRIA Algorithms Project, <a href="http://algo.inria.fr/bin/encyclopedia?Search=ECSnb&argsearch=1034">Encyclopedia of Combinatorial Structures 1034</a>
%F A052963 G.f.: -(-1+x+x^2)/(1-3*x+x^3)
%F A052963 Recurrence: {a(0)=1,a(1)=2,a(2)=5,a(n)-3*a(n+2)+a(n+3)}
%F A052963 Sum(1/9*(1+2*_alpha+_alpha^2)*_alpha^(-1-n),_alpha=RootOf(1-3*_Z+_Z^3))
%p A052963 spec:= [S,{S=Sequence(Union(Prod(Sequence(Union(Prod(Z,Z),Z)),Z),Z))},unlabeled ]: seq(combstruct[count ](spec,size=n), n=0..20);
%Y A052963 Adjacent sequences: A052960 A052961 A052962 this_sequence A052964 A052965 A052966
%Y A052963 Sequence in context: A003054 A081908 A059505 this_sequence A036908 A075496 A076866
%K A052963 easy,nonn
%O A052963 0,2
%A A052963 encyclopedia(AT)pommard.inria.fr, Jan 25 2000
%E A052963 More terms from James A. Sellers (sellersj(AT)math.psu.edu), Jun 05 2000

List of transformations used:
T108  invert: define b by 1+SUM b(n)x^n = 1/(1 - SUM a(n)x^n)
T109  invert: define b by 1+SUM a(n)x^n = 1/(1 - SUM b(n)x^n)
...

Desperately seeking the truth,

Antti

```

More information about the SeqFan mailing list