the sequence A006743

[Alec Mihailovs]

From: "Max" <relf at unn.ac.ru>
Sent: Monday, October 17, 2005 5:54 PM


> It is possible to find recurrences based on a given generating function 
> rather than elements of a sequence.
> Since g.f. completely defines the sequence, it would be possible to 
> produce a proof for the recurrences.
> Is there any package for such computations?
>
> As of gfun, if it uses only a limited amount of sequence's elements (as 
> you said), it cannot give us any proof.

listtorec determines a recurrence from a given list of elements. However, 
gfun has many other useful functions.

If a generating function is known, it is not usually a problem to find a 
recurrence. Here is an example of doing that in Maple,

f:=(1-2*x+x^2-x^4-x^2*sqrt(1-4*x^2))/(1+x)^2/(1-2*x)^2:

gfun[algfuntoalgeq](f,y(x));
                2       3    4       5      6       7       8   2
  (1 - 4 x - 2 x  + 20 x  + x  - 40 x  - 8 x  + 32 x  + 16 x ) y  +

                  2       4      5      8          7       3       6
        (8 x - 4 x  + 16 x  + 4 x  + 8 x  - 2 + 8 x  - 16 x  - 14 x )

                   2      4            6      3    8      5
        y + 1 + 6 x  - 2 x  - 4 x + 2 x  - 4 x  + x  + 4 x

gfun[algeqtodiffeq](%,y(x));
      6       2      4       3
  {4 x  + 12 x  + 2 x  - 16 x  - 2 + 2 x

                6      4       3       2
         + (16 x  + 4 x  + 12 x  - 12 x  - 2 x + 2) y(x) +

             7       6       5       4      3      2      /d      \
        (16 x  + 16 x  - 16 x  - 12 x  + 7 x  + 2 x  - x) |-- y(x)|,
                                                          \dx     /

                            2
        y(0) = RootOf(1 + _Z  - 2 _Z),

                     2                        2
        RootOf(1 + _Z  - 2 _Z) = RootOf(1 + _Z  - 2 _Z)}

gfun[diffeqtorec](%[1],y(x),a(n));
  {(16 n + 16) a(n) + (16 n + 16) a(n + 1) + (-28 - 16 n) a(n + 2)

         + (-24 - 12 n) a(n + 3) + (16 + 7 n) a(4 + n)

         + (8 + 2 n) a(n + 5) + (-4 - n) a(n + 6), a(0) = 1, a(1) = 0,

        a(2) = _C[0], a(3) = -4 + 2 _C[0], a(4) = -5 + 5 _C[0],

        a(5) = 12 _C[0] - 22, a(6) = -35 + 25 _C[0]}

eval(%,_C[0]=3);
  {(16 n + 16) a(n) + (16 n + 16) a(n + 1) + (-28 - 16 n) a(n + 2)

         + (-24 - 12 n) a(n + 3) + (16 + 7 n) a(4 + n)

         + (8 + 2 n) a(n + 5) + (-4 - n) a(n + 6), a(2) = 3, a(3) = 2,

        a(4) = 10, a(5) = 14, a(6) = 40, a(0) = 1, a(1) = 0}

This recurrence can be considered "proven" (assuming that the generating 
function and Maple calculations are correct).

By the way, the recurrence is using one more initial term than it seems to 
be necessary - and there is a reason for that. The initial tems 
a(1),...,a(6) determine the sequence and a(0)=1 is an exception - calculated 
from a(1),...,a(6) value of a(0) is 5/4.

Alec Mihailovs
http://math.tntech.edu/alec/