<<RISC`Dependencies`

Package FindRelations version 0.29
written by Manuel Kauers and Burkhard Zimmermann
Copyright 2000-2010, Research Institute for Symbolic Computation (RISC),
Johannes Kepler University, Linz, Austria

Package Dependencies version 0.30
written by Manuel Kauers and Burkhard Zimmermann
Copyright 2000-2010, Research Institute for Symbolic Computation (RISC),
Johannes Kepler University, Linz, Austria

Purpose

This package provides a command for computing the ideal of algebraic relations among C-finite sequences and multi-sequences.

Let k be a field and (Subscript[f, 1]),(Subscript[f, 2]),…,(Subscript[f, r]):(ℤ^m)-> k be such that each (Subscript[f, i]) (i=1,…,r) is annihilated by a maximal system of annihilating operators with constant coefficients. A multivariate polynomial p∈k[(Subscript[x, 1]),…,(Subscript[x, r])] with p((Subscript[f, 1])(n),(Subscript[f, 2])(n),…,(Subscript[f, r])(n))=0 for all n∈ℤ is called an algebraic relation  of the sequences (Subscript[f, i]). The set of all algebraic relations of a fixed tuple of sequences forms an ideal 𝔞⊴k[(Subscript[x, 1]),…,(Subscript[x, r])]. With this package, it is possible to obtain a basis for that ideal.

Usage

Commands

The principal command privided by the package is the Dependencies command. It takes a list of sequence expressions, a symbol x, and a variable declaration, and returns generators for the ideal of algebraic relations between the given sequences, as in the following example:

Dependencies[{Fibonacci[n],Fibonacci[n+1],(-1)^n},x,Variables->{n}]

The resulting polynomials correspond to the relations ((Subscript[F, n])^2)+(Subscript[F, n])(Subscript[F, n+1])-((Subscript[F, n+1])^2)+(((-1))^n)=0 and ((((((-1))^n)))^2)-1=0, i.e., the variable x[i] refers to the ith sequence given in the input list. All other polynomial relations between (Subscript[F, n]),(Subscript[F, n+1]) and (((-1))^n) belong to the ideal generated by the two polynomials returned above.

The argument x can also be dropped. In this case, the original expressions are used in place of the x[i]:

Dependencies[{Fibonacci[n],Fibonacci[n+1],(-1)^n},Variables->{n}]

This is less clean and may lead to faulty results owing to the default simplification carried out by Mathematica on the output:

Dependencies[{n^2,n^4},x,Variables->{n}]

Dependencies[{n^2,n^4},Variables->{n}]

The Express command is a simple wrapper of the Dependencies command for finding representations of a given expression "in terms of" other given expressions:

Express[SUM[SUM[Fibonacci[i],{i,0,k}],{k,0,n}],{n,Fibonacci[n],Lucas[n]},Variables->{n}]

Declaration of Variables

The variable symbols used in the specification of the sequences are declared via the Variable option. Symbols not appearing in this list are assumed as constants.

Dependencies[{n-a,n},x,Variables->{}]

Dependencies[{n-a,n},x,Variables->{n}]

Dependencies[{n-a,n},x,Variables->{n,a}]

Sequence Specification

Expressions

As sequence specifications in the first argument of the Dependencies command, the package accepts expressions that are formed according to the following rules.

E->E/E | (Subscript[E, 0])
(Subscript[E, 0])->(Subscript[E, 0])+(Subscript[E, 0]) | (Subscript[E, 0])-(Subscript[E, 0 ])| (Subscript[E, 0])(Subscript[E, 0]) | ((Subscript[E, 0])^int) | B
B->(const^arg) | fun[arg] | arg | xfun[arg, const]| SUM[(Subscript[E, 0]),{sym,int,arg}]
fun->Fibonacci | Lucas | Pell | PellLucas | Perrin | sym
xfun-> ChebyshevU | ChebyshevT
const-> any expression free of the specified variables
arg-> any integer linear combination of the given variables
int-> any integer
sym -> any symbol

Remarks: 
(1) In the summand expression (Subscript[E, 0]) of a SUM construct, the summation index sym is treated as an additional variable. 
(2) The symbol sym in the fun rule must correspond to a user defined sequence. See the following section for how to define sequences.

Definitions

In addition to built-in sequences, the user can specify sequences whose relations to compute by giving a defining recurrence and initial values, as in the following example.

Dependencies[{f[n],f[n+1]},x,Variables->{n},Where->{f[n+2]==f[n+1]+f[n],f[0]==0,f[1]==1}]

The equations are specified by a set of recurrence equations and initial values. Each recurrence equation must be of the form f[n+r_Integer]=linear combination of f[n+i] (i=0,…,r-1), possibly plus an inhomogeneous part. Each initial value specification must be of the form f[_Integer]=const. The initial values must be given for a consecutive range of points, gaps will be padded with symbolic initial values. It is, however, not necessary to specify initial values at all:

Dependencies[{f[n],f[n+1]},x,Variables->{n},Where->{f[n+2]==f[n+1]+f[n]}]

The inhomogeneous part may be any expression corresponding to the nonterminal symbol (Subscript[E, 0]) in the grammar above. In particular, user defined sequences are allowed to appear in the inhomogeneous part of a recurrence. However, mutual dependencies are forbidden:

Dependencies[{f[n],g[n]},x,Variables->{n},Where->{f[n+1]==f[n]+g[n]^2,g[n+1]==g[n]+f[n]^2}]

Dependencies[{f[n],g[n]},x,Variables->{n},Where->{f[n+1]==f[n]+g[n]^2,g[n+1]==g[n]+Fibonacci[n]}]

Some Further Examples

Example 1: Cassini

Dependencies[{Fibonacci[n],Fibonacci[n+1]},x,Variables->{n}]

This solves Exercise 6.81 in Graham/Knuth/Patashnik.

Example 2: Multivariate sequences

Dependencies[{Fibonacci[n+m],Fibonacci[n],Fibonacci[n+1],Fibonacci[m],Fibonacci[m+1],(-1)^n,(-1)^m},x,Variables->{n,m}]

Example 3: User-defined sequences

Dependencies[{f[n],Fibonacci[n],Fibonacci[n+1],n},x,Variables->{n},Where->{f[n]==f[n-1]+f[n-2]+Fibonacci[n],f[0]==0,f[1]==1}]

This solves Exercises 7.26 in Graham/Knuth/Patashnik.

Example 4: Parameters

Dependencies[{ChebyshevU[n,x],ChebyshevT[n,x]},x,Variables->{n}]

Dependencies[{ChebyshevU[n,x],ChebyshevU[n+1,x]},u,Variables->{n}]

Dependencies[{ChebyshevT[2n,x],ChebyshevT[n,x]},t,Variables->{n}]

% /.{t[1]->ChebyshevT[2n,x],t[2]->ChebyshevT[n,x]}

Example 5: Sums

Dependencies[{SUM[SUM[Fibonacci[i],{i,0,2k}],{k,1,n+2}],Fibonacci[n],Fibonacci[n+1],n},x,Variables->{n}]

Dependencies[{SUM[Fibonacci[k]^2,{k,0,n}],SUM[Lucas[i],{i,0,n}],Fibonacci[n]},x,Variables->{n}]