Divide and conquer to multiply 2 n digit numbers.

Question

I am having trouble with finding a closed form to show that the divide and conquer algorithm for multiplying 2 numbers is $O(n^{log_2(3)})$ We are given the recurrence relation that $f(n)=3f(n/2)+cn$ for some c such that $f(1)=c$ and we are supposed to create a generating function from this. I have seen the solution without using the generating function but we are told specifically to use one. We are given the hint that $a_k=f(2^{k-1})$ and when I try this I can not get a closed form for the generating function. Any help is appreciated.

Answer 1

So, you want $$F=\sum _{n=0}^\infty a_nx^n=a_0+\sum _{n=1}^\infty (3a_{n-1}+c2^{n-1})x^n=c+(3x\sum _{n=0}^\infty a_{n}x^n)+(cx\sum _{n=0}^\infty 2^{n}x^{n})$$

Use the definition of $F$ and the geometric series. Solve for F.