Using generating function to solve non-homogenous recurrence relation

Question

The given recurrence relation is: $$ a_{n} + 2a_{n-2} = 2n + 3 $$ with initial conditions: $$ a_{0}=3$$ $$a_{1}=5$$

I know $$G(x) = a_0x^0 + a_1x^1 + \sum_{n=2}^{\infty} a_nx^n $$ and $$ a_{n} = -2a_{n-2} + 2n + 3$$

Therefore:

$$G(x) = 3 + 5x + \sum_{n=2}^{\infty} (-2a_{n-2} + 2n + 3).x^n $$ $$G(x) = 3 + 5x - 2.G(x).x^2 + \sum_{n=2}^{\infty} (2n + 3).x^n $$

I don't know how to go about solving $$\sum_{n=2}^{\infty} (2n + 3).x^n $$ And thus I can't calculate G(x) and the sequence a(n). Can someone please guide me how can I solve this?

EDIT 1: From what I have got to know:

$$G(x) (1 + 2.x^2) = 3 + 5x + 2x/(1-x)^2 + 3/(1-x) $$ $$G(x) = \frac{3 + 5x + 2x/(1-x)^2 + 3/(1-x)}{1 + 2.x^2} $$

How can I convert it into partial fractions?

Answer 1

Decompose it:

$$\sum_{n\ge 2}(2n+3)x^n=2\sum_{n\ge 2}nx^n+3\sum_{n\ge 2}x^n=2x\sum_{n\ge 2}nx^{n-1}+3\sum_{n\ge 2}x^n\;.$$

That last summation is just a geometric series, so you can easily get its closed form, and $\sum_{n\ge 2}nx^{n-1}$ is the derivative of a geometric series, so it also should not be a major problem.

Answer 2

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \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{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#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{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ $\ds{\bbox[10px,#ffd]{a_{n} + 2a_{n - 2} = 2n + 3\,\qquad a_{0} = 3,\quad a_{1} = 5}:\ {\Large ?}}$

---

With $\ds{\verts{z} < 1}$: \begin{align} \sum_{n = 2}^{\infty}\pars{a_{n} + 2a_{n - 2}}z^{n} & = 2\sum_{n = 2}^{\infty}nz^{n} + 3\sum_{n = 2}^{\infty}z^{n} \\[2mm] \pars{-a_{0} - a_{1}z + \sum_{n = 0}^{\infty}a_{n}z^{n}} + 2z^{2}\sum_{n = 0}^{\infty}a_{n}z^{n} & = 2z\,\partiald{}{z}\sum_{n = 2}^{\infty}z^{n} + 3\sum_{n = 2}^{\infty}z^{n} \\[2mm] -3 - 5z + \pars{2z^{2} + 1}\sum_{n = 0}^{\infty}a_{n}z^{n} & = 2z\,\partiald{}{z}\pars{z^{2} \over 1 - z} + 3\,{z^{2} \over 1 - z} \end{align} $$ \sum_{n = 0}^{\infty}a_{n}z^{n} = {3 - z \over \pars{1 - z}^{2}\pars{1 + 2z^{2}}} \implies a_{n} = \bracks{z^{n}}{3 - z \over \pars{1 - z}^{2}\pars{1 + 2z^{2}}} $$

---

\begin{align} a_{n} & = \braces{3\bracks{z^{n}} - \bracks{z^{n - 1}}} {1 \over \pars{1 - z}^{2}\pars{1 + 2z^{2}}} \\[5mm] & = \braces{3\bracks{z^{n}} - \bracks{z^{n - 1}}} \sum_{i = 0}^{\infty}\pars{i + 1}z^{i} \sum_{j = 0}^{\infty}\pars{-2z^{2}}^{j} \\[5mm] & = 3\sum_{i = 0}^{\infty}\sum_{j = 0}^{\infty} \pars{i + 1}\pars{-2}^{j}\bracks{i + 2j = n} \\[1mm] & - \sum_{i = 0}^{\infty}\sum_{j = 0}^{\infty}\pars{i + 1}\pars{-2}^{j} \bracks{i + 2j = n - 1} \\[5mm] & = 3\sum_{j = 0}^{\infty}\pars{n - 2j + 1}\pars{-2}^{j} \bracks{n - 2j \geq 0} \\[1mm] & - \sum_{j = 0}^{\infty}\pars{n - 2j}\pars{-2}^{j} \bracks{n - 1 - 2j \geq 0} \\[5mm] & = 3\sum_{j = 0}^{\left\lfloor n/2\right\rfloor} \pars{n + 1 - 2j}\pars{-2}^{j} - \sum_{j = 0}^{\left\lfloor\pars{n - 1}/2\right\rfloor} \pars{n - 2j}\pars{-2}^{j} \end{align} You just need to perform the sums.