## Integer Sequences Related To PI

```For any given integers s[0] and s[1] we can construct the infinite
sequence s[n], n=0,1,2,...  generated by the recurrence

s[k+2]  =  (2k+3) s[k+1]  +  (k+1)^2 s[k]               (1)

For example, with the initial values s[0]=0, s[1]=1 we produce the
sequence

0, 1, 3, 19, 160, 1744, 23184, 364176, 6598656, 135484416, ...

On the other hand, if we take the initial values s[0]=1, s[1]=0
we produce the sequence

1, 0, 1, 5, 44, 476, 6336, 99504, 1803024, 37019664, ...

For convenience, let [m,n;k] denote s[k] based on the initial values
s[0]=m and s[1]=n.  The two sequences listed above can serve as the
"basis" for all sequences of this form, according to the relation

[m,n;k]  =  (m)[1,0;k] + (n)[0,1;k]

The ratios of corresponding terms in these sequences approach some
interesting values.  For example, we can show that for any integers
m,n (positive or negative)

[m,n;k]         n - m
lim     ---------   =   ------- PI  +  m                (2)
k->inf    [1,1;k]           4

Simply dividing two general expressions of this form, we get the more
general relation for any w,x,y,z

[x,y;k]         (y - x)PI + 4x
lim     ---------   =   ----------------              (3)
k->inf    [w,z;k]         (z - w)PI + 4w

To illustrate, note that the sequence [1,1;k] has the values

1, 1, 4, 24, 204, 2220, 29520, 463680, 8401680, 172504080, ...

and with m=-2, n=+1 the sequence [m,n;k] has the values

-2, 1, 1, 9, 72, 792, 10512, 165168, 2992608, 61445088, ...

The ratio of the 9th terms of these sequences is

61445088                           3
---------  =  0.356194984...   ~  --- PI  -  2
172504080                          4

If we add 2 to this ratio and multiply by 4/3 we get 3.141593...
Another interesting observation concerns the growth rate of the
individual sequences.  It appears that the difference in consecutive
ratios of consecutive values approaches 1 + sqrt(2).  In other
words
[m,n;k+2]      [m,n;k+1]          __
lim      -----------  -  ---------  =  1 + /2             (4)
k -> inf    [m,n;k+1]       [m,n;k]

I suppose these results apply to any real values of m,n, not just
integers, so equation (3) gives the limit of ratios of terms of any
sequence [x,y;k] to terms of the sequence [w,z;k].  I'd be interested
if anyone could supply an explicit solution of the recurrence (1),
which is a simple homogeneous linear 2nd-order recurrence, but with
non-constant coefficients.

By the way, since (3) shows that all the sequences are easily related,
it's enough to consider just the ratio of two sequences.  Define the
integer sequences D[k] and N[k] such that both satisfy the same recurrence
relation, namely

N[k+2]  =  (2k+3) N[k+1]  +  (k+1)^2  N[k]
and
D[k+2]  =  (2k+3) D[k+1]  +  (k+1)^2  D[k]

with the initial values

N[0] = 0           D[0] = 1
N[1] = 1           D[1] = 1

Thus the values of N and D are

N = {0, 1, 3, 19, 160, 1744, 23184, 364176, 6598656,...}
D = {1, 1, 4, 24, 204, 2220, 29520, 463680, 8401680,...}

It can be shown that the ratio N[k]/D[k] equals the kth convergent
of the continued fraction for the arctangent of 1:

1
PI/4   =  -----------------
1
1 +  -------------
4
3 + ------------
9
5 + ----------
16
7 + ---------
25
9 + -------

etc.

Incidentally, this continued fraction can also be inferred from the
fact that
/ i - 1 \
PI  =  -2i ln( ------- )
\ i + 1 /

The continued fraction can be converted into the following infinite series

PI       3    5     7     9      11      13      15       17
-- = 1 + - - --- + --- - ---- + ----- - ----- + ----- - ------- + ...
2       4    24   204   1408   10455   71484   478429  3148884

where the kth term c_k is just the difference between the (k-1)th and
the (k+1)th convergent of the continued fraction.  In other words

N[k+1]     N[k-1]
c_k   =   -------- - -------
D[k+1]     D[k-1]

As a result, the partial sums of the series are just the sums of two
consecutive convergents of the continued fraction.  It's nice that the
sequence of numerators is just the odd numbers.  It would be even nicer
to have an explicit expression for the denominators.  In that direction,
notice that if we let g denote the greatest common divisor of

D[k-1] D[k+1]        and         D[k+1] N[k-1] - D[k-1] N[k+1]

it follows that

D[k+1] N[k-1] - D[k-1] N[k+1]  =  (2k+1) g
and
D[k-1] D[k+1]  =   d_k g

where d_k is the denominator of the kth term in the above series for
PI/2.  Now it appears that

D[k+1] N[k-1] - D[k-1] N[k+1]   =   (2k+1) [(k-1)!]^2         (5)

so g = [(k+1)!]^2, which implies that

D[k-1] D[k+1]
d_k  =  ---------------
[(k-1)!]^2

Equation (5) is sort of a convolution of the terms of the two sequences,
which is in some way a more natural definition of their relation than
the original linear 2nd order recurrence.

Actually (5) is just one of a set of formulas relating the "cross-
products" of these two series.  In general we have

N[k] D[k+j]  -  N[k+j] D[k]   =  [k!]^2  P(k)

where P(k) is a polynomial in k of degree j-1.  The first few such
polynomials are listed below

j                         P(k)
---   ----------------------------------------------------
1       1
2       3 +     2 k
3      19 +    20 k +     5 k^2
4     160 +   214 k +    90 k^2 +   12 k^3
5    1744 +  2718 k +  1497 k^2 +  348 k^3 +   29 k^4
6   23184 + 40336 k + 26453 k^2 + 8236 k^3 + 1225 k^4 +  70 k^5

The constant coefficients are just the values of the N[] sequence,
whereas the leading coefficients 1, 2, 5, 12, 29, 70, ... are the
"Pell numbers" that satisfy the recurrence s[n]=2s[n-1]+s[n-2].
Also, notice that the sums of the coefficients for the jth polynomial
are 1, 5, 44, 476, 6336, 99504, ...  which are the values of the
other "basis sequence" mentioned previously.  In other words, these
values satsify the same recurrence as do N[] and D[], but with the
initial values 1,0,..., which is the sequence [1,0;k].

By the way, A.P.Magnus comments that

D[k+1] = 2 (k+1)! P_k(i) /i^k   ,     k=1,2,...

where P_k is the k-th degree Legendre polynomial, and N[k] is an
associated Legendre polynomial.

One last observation.  Using the original sequence notation, we have
the extremely interesting result:
_                    _
|   [0,1;k]            |
|  ---------  , 1 , k  |  =  0
|_  [-1,0;k]          _|

```