Generating function of a recurrent relation Problem: Find the generating function for the recurrent relation:
$$f_n=2f_{n-1}+\frac 12 f_{n-2},$$
where
$$f_0=f_1=1.$$
My idea was to first find a few of the beginning values and then try to make into some sum of an infinite series, but  I had no luck. Any ideas?
 A: 
We denote with $F(x)=\sum_{k=0}^\infty f_n x^n$ a generating function for the recurrence relation
  \begin{align*}
f_n&=2f_{n-1}+\frac{1}{2}f_{n-2}\qquad\qquad  n\geq 2\tag{1}\\
f_0&=1\\
f_1&=1
\end{align*}

It is convenient to use the coefficient of operator $[x^n]$ to denote  the coefficient of $x^n$ of a series.

We obtain according to (1) for $n\geq 2$
  \begin{align*}
[x^n]F(x)&=2[x^{n-1}]F(x)+\frac{1}{2}[x^{n-2}]F(x)\\
&=2[x^n]xF(x)+\frac{1}{2}[x^{n}]x^2F(x)\tag{2}\\
\end{align*}
From which
  \begin{align*}
[x^n]F(x)\left(1-2x-\frac{1}{2}x^2\right)&=0\qquad\qquad n\geq 2
\end{align*}
  follows.

In (2) we use the rule $[x^{p-q}]A(x)=[x^p]x^qA(x)$.

We therefore get for $n\geq 0$
  \begin{align*}
F(x)\left(1-2x-\frac{1}{2}x^2\right)=a+bx\tag{3}\\
\end{align*}
  with $a,b \in \mathbb{R}$.

We can calculate $a$ and $b$ by using $f_0=f_1=1$ and noting that only coefficients of $x^0$ and $x^1$ from the left-hand side of (3) contribute anything to $a+bx$ at the right-hand side of (3).

We obtain from (3)
  \begin{align*}
a&=[x^0]F(x)\left(1-2x-\frac{1}{2}x^2\right)\\
&=[x^0](1+\sum_{k=1}^\infty f_nx^n)\left(1-2x-\frac{1}{2}x^2\right)\\
&=1\\
b&=[x^1]F(x)\left(1-2x-\frac{1}{2}x^2\right)\\
&=[x^1](1+x+\sum_{k=2}^\infty f_nx^n)\left(1-2x-\frac{1}{2}x^2\right)\\
&=[x^1](1+x)(1-2x)\\
&=-1
\end{align*}
We conclude
  \begin{align*}
\color{blue}{F(x)}&\color{blue}{=\frac{1-x}{1-2x-\frac{1}{2}x^2}}\\
&\color{blue}{=1+x+\frac{5}{2}x^2+\frac{11}{2}x^3+\frac{49}{4}x^4+\cdots}
\end{align*}

A: $$g(x)=f_0+f_1x+\sum_{n=2}^\infty f_nx^n
=1+x+2\sum_{n=2}^\infty f_{n-1}x^n+\frac12\sum_{n=2}^\infty f_{n-2}x^n\\
=1+x+2x\sum_{n=2}^\infty f_{n-1}x^{n-1}+\frac{x^2}2\sum_{n=2}^\infty f_{n-2}x^{n-2}\\
=1+x+2x(g(x)-1)+\frac{x^2}2g(x)$$
and you solve this linear equation in $g(x)$.
