Attach an example notebook showing ones that do and ones that do not?

Your example:

In[1]:= RSolve[{(2 n + 1) a[n] == a'[n + 1] - a'[n - 1]}, a[n], n]

RSolve::deqx: Supplied equations are not difference equations of the given functions.

a' is usually used for the derivative of a continuous function a.

Dropping the derivative mark gives,

In[1]:= RSolve[{(2 n + 1) a[n] == a[n + 1] - a[n - 1]}, a[n], n]

Out[1]= 
{{a[n] -> BesselI[1/2 + n, -1]*C[1] + BesselK[1/2 + n, 1]*C[2]}} 

where C[1] and C[2] depend on the initial conditions.