Proof of two conjectures of Petkovšek and Wilf on Gessel walks

Let F(m;n1,n2) be the number of Gessel walks with exactly m steps ending at the point (n1,n2). In this paper a probabilistic model of Gessel walks is established and F(m;n1,n2) is shown to be the number of pairs of non-crossing Dyck paths and free Dyck paths. Two formulas for F(2n+2k;0,n) and F(n+2k;n,0) conjectured by Petkovšek and Wilf are proved.