# [seqfan] Re: Column Recurrences of Fibonacci Order

Neil Sloane njasloane at gmail.com
Tue Aug 20 02:04:20 CEST 2013

```Ron, I showed your message to Doron Zeilberger.

He can prove that the Fibonacci number is an upper
bound on the order of the recurrence for all k.
He also worked out - with a rigorous proof - the
generating functions for the first 11 columns,
and in each case the degree of the denominator is equal to the Fibonacci
number.

Can you submit the array (read by anti-diagonals) to the OEIS,
as well as columns 3,4,5,6 (say)? Then I will add his
analysis to the entry for the array. It is much too long to show here, but
I will give the start of his message.

Could you also add the sequence for the main diagonal of the array?
Here is the extension to 11 terms that Doron computed:
[1, 1, 13, 133, 3631, 172082, 16566199, 3057290265, 1105411581741,
776531523355217, 1063228770141145384]
Let me know the A-numbers!

Here is the start of Doron's message

Rigorously derived generating functions for
enumerating k by n Hardin matrices for k from 1 to 11

Definition: A Hardin matrix has entries from {0,1}
with no adjacent 1's horizontally, vertically, or
in the NE-SW direction, and whose top-left entry is 1

Definition: For a fixed k, Let f(k)(x) be the
generating function
whose coefficient of x^n is the number of n by k
We have the following (rigorously-derived) facts
followed by the first, 20, terms of the enumerating
sequence (for  the sake of Sloane)

f[1](x) = -x/(x^2+x-1)

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

f[2](x) = -x/(x^3+2*x^2+x-1)

[1, 1, 3, 6, 13, 28, 60, 129, 277, 595, 1278, 2745, 5896, 12664, 27201,
58425,

125491, 269542, 578949, 1243524]

f[3](x) = -x*(x^3-x-2)/(x^5-4*x^3-5*x^2-x+1)

[2, 3, 13, 35, 112, 337, 1034, 3154, 9637, 29431, 89895, 274564, 838609,

2561372, 7823242, 23894643, 72981777, 222909351, 680835436, 2079486057]

f[4](x) =
x*(2*x^4-7*x^3-x^2+3*x+3)/(x^8-3*x^7+x^6+6*x^5-4*x^4-15*x^3-10*x^2-x+
1)

[3, 6, 35, 133, 587, 2448, 10414, 44024, 186414, 789100, 3340345, 14140347,

59858152, 253389483, 1072638232, 4540650778, 19221306410, 81366888278,

344439152622, 1458066449898]

I will send you his full message in a separate email. I will be happy to
send it to anyone else who is interested.
Neil

On Sun, Aug 18, 2013 at 1:48 PM, Ron Hardin <rhhardin at att.net> wrote:

> The orders of the column (or row) linear recurrences of this seem to form
> the Fibonacci series.
>
>
> /tmp/diu
> T(n,k)=Number of nXk binary arrays with top left value 1 and no two ones
> adjacent horizontally, vertically or nw-se diagonally
>
> Table starts
>
> ..1...1.....2......3........5.........8..........13...........21.............34
>
> ..1...1.....3......6.......13........28..........60..........129............277
>
> ..2...3....13.....35......112.......337........1034.........3154...........9637
>
> ..3...6....35....133......587......2448.......10414........44024.........186414
>
> ..5..13...112....587.....3631.....21166......126119.......745178........4416695
>
> ..8..28...337...2448....21166....172082.....1428523.....11771298.......97268701
>
> .13..60..1034..10414...126119...1428523....16566199....190540884.....2197847780
>
> .21.129..3154..44024...745178..11771298...190540884...3057290265....49208639399
>
> .34.277..9637.186414..4416695..97268701..2197847780..49208639399..1105411581741
>
> .55.595.29431.789100.26150120.802886174.25325358687.791176762937.24801939723742
>
> Column 1 is A000045
> Column 2 is A002478(n-1)
>
> Empirical for column k:
> k=1: a(n)=a(n-1)+a(n-2)
> k=2: a(n)=a(n-1)+2*a(n-2)+a(n-3)
> k=3: a(n)=a(n-1)+5*a(n-2)+4*a(n-3)-a(n-5)
> k=4:
> a(n)=a(n-1)+10*a(n-2)+15*a(n-3)+4*a(n-4)-6*a(n-5)-a(n-6)+3*a(n-7)-a(n-8)
> k=5: [order 13]
> k=6: [order 21]
> k=7: [order 34]
> k=8: [order 55]
> k=9: [order 89]
>
>
> rhhardin at mindspring.com
> rhhardin at att.net (either)
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>

--
Dear Friends, I have now retired from AT&T. New coordinates:

Neil J. A. Sloane, President, OEIS Foundation
11 South Adelaide Avenue, Highland Park, NJ 08904, USA