# categorizing some sequences defined by third order recurrences and related to the fibonacci numbers etc.

Ross La Haye rlahaye at new.rr.com
Sat Nov 6 18:30:13 CET 2004

```Seqfans,

Looking for a broader understanding of the nature of A098703 recently, I
found that the sequence seemed to fit nicely into the following table --

a[i,j]		0		1		2		3   ...

0              A000045(n)	     A000045(n)        A000045(n)
A000045(n)
1
A098703(n)
2                                       A001911(n)

3              A000285(n)
A094688(n)
4
5
6
...

Where a[i,j](n) denotes the the nth term of the a[i,j] sequence, the
structure of the sequences in the table can be defined using the following
third order linear recurrence --

a[i,j](0) = 0, a[i,j](1) = 1, a[i,j](2) = i + 1; for n > 2, a[i,j](n) = (j +
1)a[i,j](n - 1) - (j - 1)a[i,j](n - 2) - ja[i,j](n - 3)

The charateristic polynomial, then, is x^3 - (j + 1)x^2 - (j - 1)x - j.

The table above is sparsely populated; the following table, which includes
"fitting" *and* "almost fitting" sequences, fills it in quite a bit more --

a[i,j]		0		1		2		3   ...

0              A000045(n)	     A000045(n)        A000045(n)
A000045(n)
1           A000045(n + 1)*  A000071(n + 2)   A027934(n - 1)    A098703(n)
2              A000032(n)*       A001911(n)      A008466(n + 1)

3              A000285(n)        A027961(n)
A094688(n)
4           A022095(n - 1)    A053311(n - 1)    A027974(n - 1)
5           A022096(n - 1)
6           A022097(n - 1)
...

* for n > 0

For all the sequences I've examined, the following relations hold --

a[i,j](n) = Convolution of a[0,i] with i^n, for i = j and i > 0, i.e. the
entries of the main diagonal after a[0,0](n) consist of the convolution of
the Fibonacci numbers with 1^n, 2^n, 3^n etc...
a[i,j](n) = Sum [a[i - 1,j](k), {k=0...n}], for i = j and i > 0
a[i,j](n) = a[i - 1,j](n) + a[j,j](n - 1), for i > 0
a[i,1](n) = Sum[a[i - 1,0](k) {k=0...n}], for i > 0

a[0,3](n) = ((Phi^(n-1) + (-Phi)^(1-n) + Phi^(n+1) + (-Phi)^(-1-n)) / 5
a[1,3](n) = (3^n + Phi^(n-1) + (-Phi)^(1-n)) / 5
a[2,3](n) = (2(3^n) + Phi^(n-1) + (-Phi)^(1-n) - Phi^(n+1) - (-Phi)^(-1-n))
/ 5
a[3,3](n) = (3^(n+1) - Phi^(n+2) - (-Phi)^(-2-n)) / 5

(where Phi denotes the golden mean)

...and...

a[1,3](n) = (3^1)(a[1,3](n-1) - a[0,0](n-3)
a[1,3](n) = (3^2)(a[1,3](n-2) - a[3,0](n-4)

a[2,0](n) = a[2,1](n) - a[2,1](n-3)
a[2,3](n) = a[1,3](n) + a[3,3](n-1)
a[2,3](n) = a[0,3](n) + 2a[3,3](n-1)

I imagine many other relations can be derived.  At any rate, I just thought
I'd note the foregoing in case it turned out to be of interest.  Please let
me know if there are any errors that I've missed etc.

Ross

-------------- next part --------------
A non-text attachment was scrubbed...
Name: winmail.dat
Type: application/ms-tnef
Size: 2792 bytes
Desc: not available
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20041106/8df26166/attachment.bin>
```