It looks like you are already memoizing the function. That's good. This means having the function g remembers what previous values it already computed instead of recomputing them. http://reference.wolfram.com/mathematica/tutorial/FunctionsThatRememberValuesTheyHaveFound.html

Another common thing to do is to Compile the function so that it runs faster in general. http://reference.wolfram.com/mathematica/tutorial/CompilingMathematicaExpressions.html

Finally, you should know that there is a big speed difference between symbolic computing and numeric computing. You are doing symbolic computations with symbolic numbers instead of working with flaoting point values. Sum is not meant to be a fast function, it instead tries to reason about what it is given to create a symbolic value. If you want things to be added together efficiently, trying using Total. Total requires that you give it a list of numbers to add together. Ideally these are floating point numbers or Integers if you want any speed. For example:
The real way to optimize this is to see that this function is really a big recurrence relation. It's probably a solvable one too. Mathematica provides RSolve which is usually pretty good at finding closed form solutions for these. If you plan on building up an entire table of values, you might try using ReccurenceTable although I'm not sure it'd be useful in this case.