Needs["SpecialFunctions`"]

HolonomicRE[k!, a[k]]

(Subscript[RE, 1]) = HolonomicRE[Binomial[n, k], a[k]]

FunctionExpand[Binomial[n, k + 1]/Binomial[n, k]]

FunctionExpand[Binomial[n + 1, k]/Binomial[n, k]]

(Subscript[RE, 2]) = HolonomicRE[Binomial[k, n], a[k]]

SumRE[(Subscript[RE, 1]), (Subscript[RE, 2]), a[k]]

HolonomicRE[Binomial[n, k] + Binomial[k, n], a[k]]

HolonomicRE[(1 - k!)*Binomial[n, k], a[k]]