How does FindGeneratingFunction work?

How might one implement similar functionality from scratch in Mathematica? I am looking for a description of a reasonable algorithm, not necessarily code. I am more interested in any computer algebra methods to solve this problem than in the specifics of the particular implementation Mathematica uses.

In Mathematica,some function is classified as kernel function,such as Sin,UnitStep or Abs and so on.We can use SystemPrivateHasAnyCodesQ to judge it is kernel function or not,I have metioned it in this post this answer recently.If the function is not a kernel function.Since they all are not,we can use GeneralUtilitiesPrintDefinitions to get some some information of what you want.
<<GeneralUtilities;GeneralUtilitiesPrintDefinitions[FindGeneratingFunction]

We can see the work fuction is call a name of findGeneratingFunctionParser,click on it.You will get its page of definition,then you will see findGeneratingFunctionDispatcher,findGeneratingFunctionPoints and iFunctionSpace.We can know it find generation function in 5 case: http://o8aucf9ny.bkt.clouddn.com/2016-12-13-07-09-55.png
You can use same method to find some information for FindSequenceFunction`.Those information is more useful to you maybe.It's very clear.