This site is supported by donations to The OEIS Foundation.

Autosequence

From OeisWiki

Jump to: navigation, search

Contents

Definition

"Autosequence" is a neologism coined by Paul Curtz, a contributor to the OEIS, for a sequence {a(n)} which is identical to its Inverse Binomial transform (see Transforms), up to alternating signs. This means that there is some \scriptstyle m \in \{-1,1\} such that

a(n) = m\sum_{k=0}^n(-1)^k{n\choose k}a(k)

holds for all nonnegative n. [See also "Eigensequence" in Bernstein-Sloane (1995).]

Two kinds of autosequence

If \scriptstyle m=-1 the sequence is called an autosequence of the first kind, otherwise an autosequence of the second kind. Equivalently, the two kinds of autosequences may be distinguished according to the nature of the diagonal of the array of successive differences.

Autosequence of the first kind

An autosequence belongs to the first kind if and only if the main diagonal terms of its array of successive differences are all zeroes.

In this case, the second term of the first row is the same as the second term of the first column.

Example

Fibonacci(n) n>=0 (Cf. A000045) is an autosequence of the first kind, its successive differences being:

0,   1,   1,   2,   3,   5,   8,  ...

1,   0,   1,   1,   2,   3,   5,  ...

-1,  1,   0,   1,   1,   2,   3,  ...

2,  -1,   1,   0,   1,   1,   2,  ...

-3,  2,  -1,   1,   0,   1,   1,  ...

5,  -3,   2,  -1,   1,   0,   1,  ...

-8,  5,  -3,   2,  -1,   1,   0,  ...

...

Autosequence of the second kind

An autosequence belongs to the second kind if and only if the main diagonal of its array of successive differences is twice the first upper subdiagonal.

In this case, unlike an autosequence of the first kind, the second term of the first row and the second term of the first column are opposite.

Example

Lucas(n) n>=0 (Cf. A000032) is an autosequence of the second kind, its successive differences being:

2,   1,   3,   4    7,  11,  18, ...

-1,  2,   1,   3,   4,   7,  11, ...

3,  -1,   2,   1,   3,   4,   7, ...

-4,  3,  -1,   2,   1,   3,   4, ...

7,  -4,   3,  -1,   2,   1,   3, ...

-11, 7,   4,   3,  -1,   2,   1, ...

18, -11,  7,  -4,   3,  -1,   2, ...

...

There is a one-to-one correspondence between autosequences of the first kind and autosequences of the second kind.

Let 'a' be of the first kind, then its second kind mate 'b' is given by the formula:

b(n) = 2 a(n+1) - a(n).

Conversely, 'a' from 'b' is given by the recursive formula:

a(0) = 0
a(n) = (a(n-1) + b(n-1))/2

that is:

a(n) = 1/2^n sum_{k = 0 .. n-1} 2^k b(k).  

Considering again Fibonacci(n), one can see that its mate of the second kind is:

b(n) = 2 Fibonacci(n+1) - Fibonacci(n) = Lucas(n). 

Of course, 1/2^n sum_{k = 0 .. n-1} 2^k Lucas(k) gives back the Fibonacci numbers.

Examples of pairs of autosequences

1st kind <---> 2nd kind

A000045 <---> A000032

A001045 <---> A014551

A015441 <---> A087451

A057427 <---> A054977

A113405 <---> A242563

A226158 <---> A230324

Notes and references

Personal tools