Ben Chuanlong Du's Blog

And let it direct your passion with reason.

The Power of Generating Functions

Generating functions is a very powerful way to find closed formula for sequences defined iteratively. I was so bored during the final week, so I went on internet for fun. Finally I found someone from Sydney University was asking for help on this question:

(a) If Ln=Ln-1+Ln-2 for n>1 and Lo=2 and L1=1, please Find a closed formula for Ln.

(b) Sn=Ln+ Ln-1 + … + Lo, please find an closed formula for Sn.

(c) An=Ln-1So + Ln-2S1 + … + LoSn-1, please find a closed formula for An.

I gave a solution using generating functions. See sequence.

If you're from math department, you might question that do these series defined converge, if so what are the domains of convergence? Dating back to some day when I was still a sophomore, I read a book about generating functions and talked with my friend Hao Ying about how powerful it is. I cited the author's words:" We don't even have to check the domain of convergence of the series…". Hao bugged up and said:" What? You don't need to check the domain of converge? It's not important what others said. What really matters is what you think. Do you really think that's valid?…". Well, I still have to say that really we don't need check the converge domain of the series we used. It's trifle and might too be hard. As is known too all, it's easy to use mathematical induction method to prove or disprove a closed formula for a sequence define iteratively. If the formula can be proved, the generating method works, vise versa. So far I haven't come across a situation that generating functions method fails to work.

Comments