Solving recurrence equation with generating indices of positive indices

Question

I don't know how to solve recurrence equation with positive indices like $$a_{n+2} + 4a_{n+1}+ 4a_n = 7$$ by generating functions. How to solve such kind of problems.

Answer 1

Hint. You may just multiply both sides of the following relation by $x^{n+2}$ and summing it: $$ a_{n+2} + 4a_{n+1}+4a_n = 7 \tag1 $$ to get $$ \sum_{n=0}^{\infty}a_{n+2}x^{n+2} + 4x\sum_{n=0}^{\infty}a_{n+1}x^{n+1}+4x^2\sum_{n=0}^{\infty}a_n x^n= 7x^2\sum_{n=0}^{\infty}x^n $$ or $$ \sum_{n=2}^{\infty}a_{n}x^{n} + 4x\sum_{n=1}^{\infty}a_{n}x^{n}+4x^2\sum_{n=0}^{\infty}a_n x^n= 7x^2\sum_{n=0}^{\infty}x^n \tag2 $$ equivalently, setting $\displaystyle f(x):=\sum_{n=0}^{\infty}a_{n}x^{n} $, you formally get $$ f(x)-a_0-a_1x+4x(f(x)-a_0)+4x^2f(x)=7x^2\frac{1}{1-x} $$ that is $$ (2x+1)^2f(x)=\frac{7x^2}{1-x}+(4a_0+a_1)x+a_0 $$ $$ f(x)=\frac{7x^2}{(1-x)(2x+1)^2}+\frac{(4a_0+a_1)x+a_0}{(2x+1)^2} \tag3 $$ Then by partial fraction decomposition and power series expansion, you are able to identify coefficients of both sides of $(3)$.

Answer 2

A Special Class of Recurrence Equations

To solve the homogenous recurrence $$ (S-\lambda)^ka_n=0\tag{1} $$ where $Sa_n=a_{n+1}$ is a shift operator, we note that if $a_n=\lambda^n b_n$ then $S^k(\lambda^nb_n)=(\lambda S)^kb_n$. Therefore, $(1)$ becomes $(\lambda S-\lambda)^kb_n=0$, which is equivalent to $$ (S-1)^kb_n=0\tag{2} $$ $(2)$ says that the $k^{\text{th}}$ forward difference of $b_n$ vanishes. That is, $b_n$ is a $k-1$ degree polynomial in $n$, which means that the solution to $(1)$ is $$ a_n=\lambda^n\sum_{j=0}^{k-1}c_jn^j\tag{3} $$

---

Particular and Homogenous Solutions

A particular solution to $a_{n+2}+4a_{n+1}+4a_n=7$ is $$ a_n=\frac79\tag{4} $$ The homogeneous equation $a_{n+2}+4a_{n+1}+4a_n=0$ is simply $(S+2)^2a_n=0$, and according to the preceding section, we get the solution to be $$ a_n=(c_0+c_1n)(-2)^n\tag{5} $$ Putting the particular and homogeneous solutions together gives $$ a_n=\frac79+(c_0+c_1n)(-2)^n\tag{6} $$ Now we just need to determine $c_0$ and $c_1$ to satisfy whatever other conditions we have.

Answer 3

To make your life easier start with the difference equation to get rid of the constant. You get (set $b_n = a_n - a_{n-1}$):

$$ b_{n+2} =-4 b_{n+1} - 4 b_n $$

Now use GF.

EDIT $$ a_{n+2} +4 a_{n+1} + 4 a_n = 7\\ a_{n+1} + 4 a_{n} +4 a_{n-1} = 7\\ \Delta a_{n+2} +4 \Delta a_{n+1} + 4 \Delta a_n = 0 $$ Now set $\Delta a_n = b_n$ and use GF.