Generating function of a recurrent relation

Question

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?

Answer 1

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*}

Answer 2

$$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)$.