Runge-Kutta methods, trees, and maple on a Simple Proof of Butcher's Theorem and the automatic generation of order condition

Abstract

This paper presents a simple and elementary proof of Butcher's theorem on the order conditions of Runge-Kutta methods. It is based on a recursive definition of rooted trees and avoids combinatorial tools such as labelings and Fadi Bruno's formula. This strictly recursive approach can easily and elegantly be implemented using modern computer algebra systems like Maple for automatically generating the order conditions. The full, but short source code is presented and applied to some instructive examples.