Here are a few things to consider.
(1) Actually your formula had a sign error (which i found by comparing HermiteH[4,x] behavior with HermiteH[n,x] and then substituting n->4).
http://functions.wolfram.com/Polynomials/HermiteH/17/01/01/
So the corrected version of my replacement rule code would be
rul = (x_^p_.* HermiteH[n_, x_] /; IntegerQ[p] && p >= 1) :>
x^(p - 1)*HermiteH[n + 1, x]/2 + n *x^(p - 1)*HermiteH[n - 1, x];
(2) I do not know how to set up and solve an appropriate partial difference equation to obtain a general form. I suspect there is no closed form since it would involve a sum that likely has no closed form.
(3) An alternative to rule replacement is as follows (works for specific p
but general n
).
Clear[f]
f[0, n_] := HermiteH[n, x]
f[p_, n_] := f[p, n] = Expand[f[p - 1, n + 1]/2 + n*f[p - 1, n - 1]]
Example:
f[3, n]
(* Out[48]= 2 n HermiteH[-3 + n, x] - 3 n^2 HermiteH[-3 + n, x] +
n^3 HermiteH[-3 + n, x] + 3/2 n^2 HermiteH[-1 + n, x] +
3/4 HermiteH[1 + n, x] + 3/4 n HermiteH[1 + n, x] +
1/8 HermiteH[3 + n, x] *)