If $g(x)=\sum_{n} f_n x^n=\frac{2x^2+x^3}{1-x-x^2}$,then find the general expression for the coefficients,$f_n$.

Question

As evident $f_n=\frac{1}{n!}\frac{d^n}{dx^n}g(x)(at x=0)$.If I use Cauchy's integral formula to find the $nth$ derivative,then I'm stuck,because there also the derivative crops up while finding the residue.

Answer 1

Long division gives us that $$ \begin{align} \frac{2x^2 + x^3}{1-x-x^2} &= -(x+1)+\frac{1}{1-x-x^2}\\ &=-x-1+1+x+2x^2+3x^3+\dotsb \\ &=2x^2+3x^3+5x^4\dotsb \end{align}$$

Answer 2

Notice that the denominator cancels in $\frac {-1 \pm \sqrt 5} 2$, so we shall investigate analyticity only on the open ball centered in $0$ and of radius $\frac {-1 + \sqrt 5} 2$.

Multiplying by the denominator, one gets that $(1-x-x^2) \sum \limits_{n \ge 0} f_n x^n = 2x^2 + x^3$, which means that $\sum \limits_{n \ge 0} f_n x^n - \sum \limits_{n \ge 0} f_n x^{n+1} - \sum \limits_{n \ge 0} f_n x^{n+2} = 2x^2 + x^3$, or further that

$$f_0 + f_1 x - f_0 x + \sum \limits _{n \ge 2} (f_n - f_{n-1} - f_{n-2}) x^n = 2x^2 + x^3 ,$$

which means that:

$$\begin{align} &f_0 &=& 0 \\ &f_1 - f_0 &=& 0 \\ &f_2 - f_1 - f_0 &=& 2 \\ &f_3 - f_2 - f_1 &=& 1 \\ &f_n - f_{n-1} - f_{n-2} &=& 0 \ \forall n \ge 4 . \end{align}$$

This leads to $f_0 = 0, \quad f_1 = 0, \quad f_2 = 2, \quad f_3 = 3$ and then $f_n = f_{n-1} + f_{n-2} \ \forall n \ge 4$, the last formula being precisely the formula giving the Fibonacci sequence, but with different first terms ("initial conditions").

There is a general approach to solving this kind of recurrences: for example, to the one given above attach the equation $r^2 = r + 1$. This has the roots $\frac {-1 \pm \sqrt 5} 2$, which makes us posit that

$$f_n = a \left( \frac {-1 + \sqrt 5} 2 \right)^n + b \left( \frac {-1 - \sqrt 5} 2 \right)^n \ \forall n \ge 4 ,$$

with $a,b$ to be found.

Compute $f_4, f_5$ from the above recurrence: $f_4 = f_3 + f_2 = 5$ and $f_5 = f_4 + f_3 = 8$. Then solve the system

$$\left\{ \begin{eqnarray} 5 = f_4 = a \left( \frac {-1 + \sqrt 5} 2 \right)^4 + b \left( \frac {-1 - \sqrt 5} 2 \right)^4 \\ 8 = f_5 = a \left( \frac {-1 + \sqrt 5} 2 \right)^5 + b \left( \frac {-1 - \sqrt 5} 2 \right)^5 \end{eqnarray} \right.$$

to get

$$a = \frac {49} 2 + \frac {111} {10} \sqrt 5, \quad \frac {49} 2 - \frac {111} {10} \sqrt 5 .$$

Finally, then,

$$f_n = \left( \frac {49} 2 + \frac {111} {10} \sqrt 5 \right) \left( \frac {-1 + \sqrt 5} 2 \right)^n + \left( \frac {49} 2 - \frac {111} {10} \sqrt 5 \right) \left( \frac {-1 - \sqrt 5} 2 \right)^n \ \forall n \ge 4 .$$

(In fact, the sequence $(f_n) _{n \ge 2}$ is just the usual Fibonacci sequence without the first terms $0, 1, 1$.)

Answer 3

You may check that $$ \frac{x}{1-x-x^2} = \sum_{n\geq 0} F_n x^n \tag{1} $$ holds just by multiplying both sides by $1-x-x^2$ and recalling that $F_{n+2}=F_{n+1}+F_n$.
It follows that: $$\begin{eqnarray*} \frac{2x^2+x^3}{1-x-x^2} = 2\sum_{n\geq 0}F_n x^{n+1}+\sum_{n\geq 0}F_n x^{n+3}=2x^2+3x^3+\sum_{n\geq 4}F_n x^n.\tag{2}\end{eqnarray*} $$

Answer 4

$\newcommand{\angles}[1]{\left\langle\,{#1}\,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{\mathrm{i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\Li}[1]{\,\mathrm{Li}_{#1}} \newcommand{\mc}[1]{\,\mathcal{#1}} \newcommand{\mrm}[1]{\,\mathrm{#1}} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

Other answers pointed out the relation to the Fibonacci Numbers. However, it's desirable to have numerical expressions for the coefficients.

---

Note that the roots of $\ds{1 - x - x^{2} = 0}$ are $\ds{-\varphi}$ and $\ds{1 \over \varphi}$ where $\ds{\varphi = {1 + \root{5} \over 2}}$ is the Golden Ratio: \begin{align} \color{#f00}{2x^{2} + x^{3} \over 1 - x - x^{2}} & = -\,{2x^{2} + x^{3} \over \pars{x + \varphi}\pars{x - \varphi^{-1}}} = -\pars{2x^{2} + x^{3}}\pars{{1 \over x + \varphi} - {1 \over x - \varphi^{-1}}} {1 \over -\varphi^{-1} - \varphi} \\[5mm] & = {\root{5} \over 5}\pars{2x^{2} + x^{3}} \pars{{\varphi^{-1} \over 1 + \varphi^{-1}x} + {\varphi \over 1 - \varphi x}} \end{align}

---

With $\ds{\varphi\verts{x} < 1}$: \begin{align} \color{#f00}{2x^{2} + x^{3} \over 1 - x - x^{2}} & = {\root{5} \over 5}\pars{2x^{2} + x^{3}}\sum_{n = 0}^{\infty} \bracks{\varphi^{-n - 1} + \pars{-1}^{n}\varphi^{n + 1}}x^{n} \\[5mm] & = {\root{5} \over 5}\braces{\sum_{n = 0}^{\infty} 2\bracks{\varphi^{-n - 1} + \pars{-1}^{n}\varphi^{n + 1}}x^{n + 2} + \bracks{\varphi^{-n - 1} + \pars{-1}^{n}\varphi^{n + 1}}x^{n + 3}} \\[5mm] & = {\root{5} \over 5}\braces{\sum_{n = 2}^{\infty} 2\bracks{\varphi^{-n + 1} + \pars{-1}^{n}\varphi^{n - 1}}x^{n} + \sum_{n = 3}^{\infty} \bracks{\varphi^{-n + 2} - \pars{-1}^{n}\varphi^{n - 2}}x^{n}} \\[1cm] & = {\root{5} \over 5}\,\bracks{2\pars{\varphi^{-1} + \varphi}} \\[5mm] & + {\root{5} \over 5}\sum_{n = 3}^{\infty}\bracks{% 2\varphi^{-n + 1} + 2\pars{-1}^{n}\varphi^{n - 1} + \varphi^{-n + 2} - \pars{-1}^{n}\varphi^{n - 2}}x^{n} \end{align}

---

\begin{align} &\color{#f00}{\bracks{x^{n}}\pars{2x^{2} + x^{3} \over 1 - x - x^{2}}} \\[5mm] & = \left\lbrace\begin{array}{lcrcl} \ds{2} & \mbox{if} & \ds{n} & \ds{=} & \ds{2} \\[3mm] \ds{{\root{5} \over 5}\bracks{\vphantom{\Large A}% 2\,\varphi^{-n + 1}\ +\ 2\,\pars{-1}^{n}\,\varphi^{n - 1}\ +\ \varphi^{-n + 2}\ -\ \pars{-1}^{n}\,\varphi^{n - 2}}} & \mbox{if} & \ds{n} & \ds{=} & \ds{3,4,5,\ldots} \\[3mm] \ds{0}&&&&\mbox{otherwise} \end{array}\right. \end{align}

Answer 5

Suppose $$ \frac{a+bx}{1-x-x^2}=\sum_{k=0}^\infty c_kx^k $$ then $$ \begin{align} a+bx &=\left(1-x-x^2\right)\sum_{k=0}^\infty c_kx^k\\ &=\sum_{k=0}^\infty c_k\left(x^k-x^{k+1}-x^{k+2}\right)\\ &=\underbrace{\ \ \ \ \ c_0\ \ \ \ \ \vphantom{()}}_{a}+\underbrace{\left(c_1-c_0\right)}_b\,x+\sum_{k=2}^\infty\left(c_k-c_{k-1}-c_{k-2}\right)x^k \end{align} $$ Since the coefficient of $x^k$ is $0$ for $k\ge2$, we must have $c_k-c_{k-1}-c_{k-2}=0$; that is, $$ c_0=a\quad c_1=a+b\quad c_k=c_{k-1}+c_{k-2} $$

---

$$ \begin{align} \frac{2x^2+x^3}{1-x-x^2} &=-1-x+\frac1{1-x-x^2}\\ &=-1-x+\underbrace{1+x+2x^2+3x^3+5x^4+\dots}_{\sum\limits_{k=0}^\infty F_{k+1}x^k}\\ &=\sum_{k=2}^\infty F_{k+1}x^k \end{align} $$