It's true that if you have one such function then it generates a solution. -and well, in this case you can check that each is unique, once you you have found a function like that, you are done. But on a different problem -another recurrence- there might not be a function satisfying .
About the original equation, if you have 2 e.g.f s (exponential generating functions) and -generated by and respectively-, then . In your case pick - note that ...-