axiom-developer
[Top][All Lists]

Re: [Axiom-developer] The Gosper algorithm for sum of hypergeometric fun

 From: Martin Rubey Subject: Re: [Axiom-developer] The Gosper algorithm for sum of hypergeometric functions. Date: 28 Nov 2006 08:48:11 +0100 User-agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.4

Dear Francois,

unfortunately, I currently don't have the time to answer all your
questions. I'll try to answer at least the quickies:

Francois Maltey <address@hidden> writes:

> Are they all hypergeometrics ?
> this means that u(n+1) / u(n) is an algébraic fraction

No. If we are talking about

sum(u(n), n = 1.. m),

it means that u(n+1) / u(n) is rational (i.e., a fraction of two polynomials)
in n.

> Then can I recognize << with my eyes >> the hypergeometric series ?

You "only" need to check whether u(n+1) / u(n) is rational. As Waldek pointed
out, this is not always possible. You have to stay in "computable" domains,
i.e., domains where you can test for zero. For example, the domain of
arithmetic expressions is not computable: there cannot be an algorithm that
decides whether some expression is zero. Algebraic numbers, Polynomials over a
computable domain, polynomially recursive sequences over a computable domain
are examples of computable domains.

> Martin, I'm sorry but I don't understand what your package do,

It "guesses" an expression / recurrence for the n-th term of a sequence, given
the first few terms. For example,

guess([0,1,2,3,4,5]) will answer "n".

If you happen to know that your sequence is generated by a polynomial, and you
have a bound for the degree, you are done: just plug in the first degree+1
values and you'll get it. In principle we can mimick Zeilbergers algorithm
(although not very efficiently) this way: compute a bound for order and degree
of your recurrence and supply enough values to guess the sequence.

> And I don't find your package on my silver axiom.

No, you have to download the packages as indicated on
MathAction/GuessingFormulas and compile them. You'll get documentation in
HyperDoc then.

> My aim is to force axiom to compute theses exercices about series.
>
> Thanks a lot if you accept to drive me inside theses algorithms.
>
> sum (n^2 * x^n,                         n=0..%plusInfinity) -- YES

at least my Axiom doesn't know to sum to infinity. I have to say

(4) -> sum (n^2 * x^n,n=0..m)

2 3        2           2     2             m    2
(m x  + (- 2m  - 2m + 1)x  + (m  + 2m + 1)x)x  - x  - x
(4)  -------------------------------------------------------
3     2
x  - 3x  + 3x - 1
Type: Expression Integer

and then I would like to say limit(%, m=%plusInfinity). Axiom responds with
"failed", of course, since it doesn't know that x < 1...

> sum (x^n / (n+1) / (n+3),               n=0..%plusInfinity) -- no

(28) -> l := [sum (x^n / (n+1) / (n+3), n=0..m)::FRAC POLY INT for m in 0..15];

Type: List Fraction Polynomial Integer
(29) -> guessPRec l

(29)
[
[
function =
BRACKET
f(n):
2
(n  + 8n + 15)f(n + 2)
+
2               2                        2
((- n  - 6n - 8)x - n  - 8n - 15)f(n + 1) + (n  + 6n + 8)x f(n)
=
0
,
1       3x + 8
f(0)= -,f(1)= ------
3         24
,
order= 0]
]

You can now, of course, "automatically" check whether this recurrence is
correct: just replacs f(n) with sum (x^n / (n+1) / (n+3), n=0..m) and do the
calculation. However, Axiom cannot do the necessary simplifications yet:

(31) -> g m == sum (x^n / (n+1) / (n+3), n=0..m)
Type: Void
(32) -> (n^2+8*n+15)*g(n+2) +
((-n^2-6*n-8)*x-n^2-8*n-15)*g(n+1)+(n^2+6*n+8)*x*g(n)

(32)
n          n
2           --+        x
(n  + 6n + 8)x>     -----------
--+    2
n= 0  n  + 4n + 3
+
n + 1        n
2               2            --+        x
((- n  - 6n - 8)x - n  - 8n - 15) >     -----------
--+    2
n= 0   n  + 4n + 3
+
n + 2        n
2            --+        x
(n  + 8n + 15) >     -----------
--+    2
n= 0   n  + 4n + 3
Type: Expression Integer

Martin

reply via email to