This site is supported by donations to The OEIS Foundation.
Autosequence
This is the 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 such that
holds for all nonnegative n. [See also "Eigensequence" in Bernstein-Sloane (1995).]
Two kinds of autosequence
If 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
Mathematica scripts
firstKindQ[T_List] :=
Module[{ta, tb},
tb = Table[Sum[(-1)^(n-k)*Binomial[n, k]*Part[T,k+1],
{k, 0, Length[T] - 1}], {n, 0, Length[T]-1}];
ta = Table[(-1)^(n + 1) Part[T,n + 1], {n, 0, Length[T]-1}] ;
First[T] == 0 && ta == tb];
secondKindQ[T_List] :=
Module[{ta, tb},
tb = Table[Sum[(-1)^(n - k)*Binomial[n, k]*Part[T,k+1],
{k, 0, Length[T]-1}], {n, 0, Length[T]-1}];
ta = Table[(-1)^n Part[T,n+1], {n, 0, Length[T]-1}] ; ta == tb];
toSecondKind[T_?firstKindQ] :=
Table[2 Part[T,n+1] - Part[T,n], {n, 1, Length[T]-1}];
toFirstKind[T_?secondKindQ] :=
Table[1/2^n Sum[2^k Part[T,k+1], {k, 0, n-1}], {n, 0, Length[T]}];
autosequenceQ[T_List] := Which[
firstKindQ[T], Print["first kind, its second kind companion is ", toSecondKind[T]]; True,
secondKindQ[T], Print["second kind, its first kind companion is ", toFirstKind[T]]; True,
True, Print["not an autosequence"]; False];
Example:
autosequenceQ[Table[Fibonacci[n], {n, 0, 10}]]
first kind, its second kind companion is {2,1,3,4,7,11,18,29,47,76}
Notes and references
- Paul Barry, 2005, A Catalan Transform and Related Transformations on Integer Sequences
- M. Bernstein & N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210.
- OEIS, Transforms
- Helmut Prodinger, 1992, Some information about the Binomial transform
- E. W. Weisstein, Binomial Transform
- For more information, see
Autosuite de nombres(in French) — deleted
