New transforms

[N. J. A. Sloane]

Dear SeqFans

In lieu of new year's greetings, this message describes
four transformations of sequences that have come up recently.


1. Any linear recurrence can be run backwards. For example the Padovan sequence
A000931
                       1 0 0  1 0 1 1 1 2 2 3 4 5 7 9 ...
                       -> -> -> ->

when run backwards gives

...  1  -2 2 -1 0 1 -1 1 0 0
                 <- <- <- <-

which is (apart from negating every other term) the recently arrived A050935.



2. Take the sum of 2 or more consecutive terms of a sequence. For example
the primes (A000040) give another new arrival:
%I A050936
%S A050936 5,8,10,12,15,17,18
%N A050936 Sum of two or more consecutive prime numbers.
%Y A050936 Cf. A000040.
%O A050936 1,1
%K A050936 more,nonn,easy
%A A050936 G. L. Honaker, Jr. (sci-tchr at 3wave.com), Dec 31 1999

One may also simply take the sum of /any/ number of comsecutive terms.
(Of course if 0 is in the sequence that makes no difference.)
Then the primes give A034707 and its complement A050940.

Similarly the Fibonacci numbers (A000045) lead to A007298
and its complement A050939:
%S A050939 9,14,15,17,22,23,24,25,27,28,30,35,36,37,38,39,40,41,43,44,45,
%T A050939 46,48,49,51,56,57,58,59,60,61,62,63,64,65,66,67,69,70,71,72,73,
%U A050939 74,75,77,78,79,80,82,83,85,90,91,92,93,94,95,96,97,98,99,100,101
%N A050939 Not the sum of consecutive Fibonacci numbers.

I was too lazy to program those two transforms in Maple. However,
the next two will be described in Maple.



3.
# BIN1 was introduced by Don Zagier (see M. Kaneko,
# "A recurrence formula for the Bernoulli numbers",
# Proc. Japan Acad., 71 A (1995), 192-193). 

# It is an involution on the class of sequences a = [a_0, a_1, a_2, ...],
# sending a to b where b_n = (-1)^n Sum_{i=0..n} binomial(n+1,i+1) a_i.

BIN1:=proc(a)  local b,i,j,k:
if whattype(a) <> list then RETURN([]); fi:
b:=[]:
for i to nops(a) do j:=i-1; b:=[op(b), (-1)^j*add( binomial(j+1,k+1)*a[k+1] ,
        k=0..j)]: od:
RETURN(b);
end:

(The signs could be omitted, but Zagier needed them for his application, so
i have left them in.)

For example, the Catalan numbers produce A050511 under this transform:
%I A050511
%S A050511 1,3,8,23,74,262,993,3943,16178,68000,291191,1265618,5568263,24749363,
%T A050511 110961248,501209303,2278704938,10419244888,47882934663,221047167628,
%U A050511 1024586641973,4766517165713,22248226873538,104160733650738,489007907489239
%V A050511 1,-3,8,-23,74,-262,993,-3943,16178,-68000,291191,-1265618,5568263,-24749363,
%W A050511 110961248,-501209303,2278704938,-10419244888,47882934663,-221047167628,
%X A050511 1024586641973,-4766517165713,22248226873538,-104160733650738,489007907489239
%N A050511 a(n) = (-1)^n * Sum_{i=0..n} binomial(n+1,i+1)*Catalan(i).
%O A050511 0,2
%K A050511 sign,done
%A A050511 njas, Dec 28 1999



4.
# The "Stirling-Bernoulli transform" maps a sequence b_0, b_1, b_2, ...
# to a sequence c_0, c_1, c_2, ..., where if B has o.g.f. B(x), c has
# e.g.f. exp(x)*B(1-exp(x)).  [Yes, the ogf becomes an egf.]
# More explicitly,
# c_n = Sum_{m=0..n} (-1)^m*m!*Stirling2(n+1,m+1)*b_m.

STIRB:=proc(a)  local b,j,k,n:
if whattype(a) <> list then RETURN([]); fi:
n:=nops(a):
b:=[]:
for j from 0 to n-1 do
b:=[op(b), add( (-1)^k*k!*combinat[stirling2](j+1,k+1)*a[k+1], k=0..j)]:
od:
RETURN(b);
end:


I learned about this from a very nice preprint,
"Akiyama-Tanigawa's Algorithm for Bernoulli numbers",
by Masanobu Kaneko (mkaneko at math.kyushu-u.ac.jp).

The chief example is the following wonderful discovery of 
Akiyama and Tanigawa. Namely, the "Stirling-Bernoulli transform"
of the sequence
[1, 1/2, 1/3, 1/4, 1/5, ...]
gives the Bernoulli numbers.

The transform can be calculated by a kind of Pascal triangle:

Write the initial sequence as the 0-th row, say

1, 1/2, 1/3, 1/4, 1/5, ...

Given a row

    t0 t1 t2 t3 t4 ...

the next row is

       t0-t1  2(t1-t2)  3(t2-t3)  4(t3-t4) ...

Repeat!

Then the sequence formed by the /initial terms/ of the rows
is the transformed sequence.

This give a very elegant way to calculate the Bernoulli numbers!

I have also run this transform on the Catalan and Fibonacci numbers (giving
A051782, A050946).



SeqFans are invited to supply further examples of all four transforms.

Of course many examples of the first type will already be in
the database, but it will be nice to link up the forward
and backward versions.

NJAS