On Sat, Oct 29, 2011 at 9:54 PM, Robert Dodier <robert.dodier at gmail.com> wrote:
> On 10/27/11, Aleksas Domarkas <aleksasd873 at gmail.com> wrote:
>
>> (%i6) solve_rec(d(n)=n*d(n-1)-d(n-2),d(n),d(1)=1,d(2)=1);
>> (%o6) false
>
> Unfortunately I really don't know about recurrence equations
> so I can't be very helpful here. Actually I have some questions
> of my own.
>
> What is the general realm of solvable recurrences?
> Can we tell by inspecting the equation that it is solvable or not?
>
> I am guessing that the solve_rec function reduces the recurrence
> to some related equation and then tries to solve that.
> Does anyone know what is the form of that equation?
> If so, we could figure out that solvability from that.
The solve_rec package implements the hyper algorithm for solving
homogeneous recurrences with polynomial coefficients (such recurrences
are returned by the Zeilberger package). It finds hypergeometric
solutions to the recurrence. It is not possible to know in advance if
the recurrence has a hypergeometric solution, but if solve_rec does
not return them, then this is a proof that there are none.
It also solves standard recurrences with constant coefficients, but
the main purpose for solve_rec is to solve the recurrences returned by
Zeilberger. Zeilberger and solve_rec are used in the simplify_sum
function.
Andrej