  In this paper we show how to find a closed form solution for third order
difference operators in terms of solutions of second order operators. This work
is an extension of previous results on finding closed form solutions of
recurrence equations and a counterpart to existing results on differential
equations. As motivation and application for this work, we discuss the problem
of proving positivity of sequences given merely in terms of their defining
recurrence relation. The main advantage of the present approach to earlier
methods attacking the same problem is that our algorithm provides
human-readable and verifiable, i.e., certified proofs.
