Sum of Fibonacci Coefficient Power Series I am working on algorithm to count $g(x,n)$, where
\begin{align*}
g(x, n)&=\sum_{i=1}^nf(i).x^i\\
f(i)&=f(i-1)+f(i-2)\\
f(1)&=1,f(2)=1
\end{align*}
I need to compute $g(x,n)$ in logarithmic time. I've tried to change it into matrix exponentiation form, but turns out it didn't work for me. Is there any other way i can solve this problem?
 A: Hint: Noting
$$ f(i)=\frac1{\sqrt 5}\left(\frac{1+\sqrt 5}{2}\right)^i-\frac1{\sqrt 5}\left(\frac{1-\sqrt 5}{2}\right)^i$$
so one has
\begin{eqnarray}
g(x,n)&=&\frac1{\sqrt 5}\sum_{i=1}^n\left(\frac{1+\sqrt 5}{2}\right)^ix^i-\frac1{\sqrt 5}\sum_{i=1}^n\left(\frac{1-\sqrt 5}{2}\right)^ix^i.
\end{eqnarray}
You can do the rest.
A: You can derive a closed formula from starting with $g(x,n)+xg(x,n)$ and then by using the Fibonacci property and some index shifts you get $g(x,n)$ again as well as some simple additional expressions. Solving the equation for $g(x,n)$ should give you
$$g(x,n) = \frac{x(f(1)-f(2))-f(1)+x^nf(n+1)+x^{n+1}f(n)}{1+x-\frac{1}{x}}$$
at last. The most expensive part is the computation of $f(n)$ and $f(n+1)$ but this can be done in logarithmic time with matrix exponentiation. 
A: The $g(x, n)$ is the first $n$ terms  of generating function of the Fibonacci sequence that is in the following form:
$$
g(x, n)=Series(\frac{x}{1-x-x^2},n)=x+{x}^{2}+2\,{x}^{3}+\cdots + f_n\,x^n
$$
that means, you need to divide $x$ over $1-x-x^2$ polynomial for $n$ times and after that the quotient is your solution. I hope, you find it useful.
