Kılıç, Yalçın Can (2020) Algorithmic identity proving and inverse problems. [Thesis]
![[thumbnail of 10352091_Kilic_Yalcin_Can.pdf]](https://research.sabanciuniv.edu/style/images/fileicons/application_pdf.png)
10352091_Kilic_Yalcin_Can.pdf
Download (804kB)
Abstract
In their book ‘A=B’ Marko Petkovsek, Herbert Wilf and Doron Zeilberger talked about computer generated proofs of identities which contains hypergeometric functions and four fundamental algorithms about them: Sister Celine’s Algorithm, Gosper’s Algorithm, Zeilberger’s Algorithm and Algorithm Hyper. Sister Celine’s algorithm, given a definite sum with proper hypergeometric summand finds a linear recurrence operator with polynomial coefficients which annihilates the given sum. Gosper’s algorithm, given an indefinite sum with hypergeometric summand decides whether this sum can be written as a sum of hypergeometric function and a constant. Zeilberger’s algorithm does the exact same job as Sister Celine’s algorithm. However, it is much faster. Algorithm Hyper, given a linear recurrence equation with polynomial coefficients checks whether this recurrence has hypergeometric solutions or not. In addition, Petkovsek wrote an article ‘Definite Sums as Solutions of Linear Recurrences With Polynomial Coefficients’ which tries to solve, so called Inverse Zeilberger Problem: Given a linear recurrence operator with polynomial coefficients, find a sum which is annihilated by the given linear recurrence operator. In this thesis, these four algorithms are examined in detail, and numerous examples are given. Then, an inverse problem is described, and Petkovsek’s recent paper on an instance of this particular problem is explicated. Finally, the algorithms are briefly analyzed in many aspects such as generality, time and space complexity, etc.
Item Type: | Thesis |
---|---|
Uncontrolled Keywords: | Hypergeometric Summation. -- Sister Celine Algorithm. --Gosper’s Algorithm. -- Creative Telescoping Algorithm. -- Algorithm Hyper. -- Inverse Zeilberger Problem. -- Hipergeometrik Toplama. -- Rahibe Celine Algoritması. -- Gosper Algoritması. -- Yaratıcı Sadeleştirme Algorithması. -- Algorithm Hiper. -- Ters Zeilberger Problemi. |
Subjects: | Q Science > QA Mathematics |
Divisions: | Faculty of Engineering and Natural Sciences > Basic Sciences > Mathematics Faculty of Engineering and Natural Sciences |
Depositing User: | IC-Cataloging |
Date Deposited: | 03 Nov 2020 10:03 |
Last Modified: | 26 Apr 2022 10:35 |
URI: | https://research.sabanciuniv.edu/id/eprint/41213 |