Solving the non-homogeneous recurrence relation: $g_{n} = 12g_{n-2}-16g_{n-3}+6\cdot 2^n+25n$

Question

$g_{n} = 12g_{n-2}-16g_{n-3}+6\cdot 2^n+25n$ With initial conditions $g_{0} = 23, g_{1} = 37, g_{2} = 42 $

This is a practice question I'm working on, and I'm running into absurd amounts of calculations with everything I have tried. I would really appreciate some guidance on this question, as I get the feeling there must be an easier way, or short cut to this question somewhere.

I've tried using both generating functions and the usual method of solving non-homogeneous recurrence relations.

The first method with generating functions, I let

$$A(z) = \sum^{\infty}_{n=0} a_{n}z^n$$ be a generating function. Putting in the initial conditions, I get:

$$ A(z) = 23 + 37z + 42z^2 + \sum^{\infty}_{n=3} (12g_{n-2}-16g_{n-3}+6\cdot 2^n+25n)z^n$$

after a bunch of simplifying and expressing the RHS in terms of $A(z)$, I get:

$$A(z) = 23 + 37z + 42z^2 + 12z^2(A(z)-23) - 16z^3A(Z)+ \frac{6}{1-2z}+25(\frac{z}{(1-z)^2} - z- 2z^2)$$

After rearranging and moving the $A(z)$ terms to the other side, I get:

$$A(z) = \frac{29-67z+23z^2+14z^3-24z^4}{(2z-1)^2(4z+1)(1-2z)(1-z)^2} $$

which turns into an absolutely hideous partial fraction decomposition, trying to solve for 6 constants. I pretty much went as far as I could go with it and still ran into a dead end, so i decided to try the usual method.

Doing the usual method, I try to solve the homogeneous part first, which is reasonably easy. My characteristic polynomial is $x^3-12x+16=0$, giving me roots $\lambda = 2 $(of multiplicity 2) and $\lambda = -4 $

So my solution to the homogeneous part is:

$$b_n = C_12^n+C_2n2^n+C_3(-4)^n$$

Now to get a particular solution, I try: $p_n = C_4n^2\cdot 6 \cdot 2^n + C_5n$

$$ \implies C_4n^2\cdot 6 \cdot 2^n + C_5n = 12(C_4(n-2)^2\cdot 6 \cdot 2^{(n-2)} + C_5(n-2)) - 16(C_4(n-3)^2\cdot 6 \cdot 2^{(n-3)} + C_5(n-3)) + 6\cdot2^n+25n $$

Another pretty nasty algebraic exercise (although not quite as bad as the generating function). However, I persist and after expanding the terms, I try to collect the $n^2\cdot2^n$ and $n$ terms together - to try and solve a simultaneous equation, but I run into the problem that I get terms without $n^2\cdot2^n$ nor $n$ and then some terms with $n\cdot 2^{n}$.

Would greatly appreciate some help with this practice question! Many thanks in advance.

Answer 1

I started your problem from scratch and arrived to something different (I have not been able to find where there has been a difference). First, I arrived to $$A(z)=\frac{-616 z^5+1540 z^4-1198 z^3+267 z^2+55 z-23}{(z-1)^2 (2 z-1)^3 (4 z+1)}$$ which decomposes as $$A(z)=-\frac{19}{z-1}-\frac{2}{(1-2 z)^2}+\frac{5}{(z-1)^2}-\frac{2}{(2 z-1)^3}-\frac{1}{4 z+1}$$ Reworking from here, I arrived to quite messy expressions for $g_n$ which, fortunately, simplify to $$g_n=2^n (n+1) n+5 n-(-4)^n+24$$

Answer 2

Simplest way I know: Define the generating function: $$ G(z) = \sum_{n \ge 0} g_n z^n $$ Write the recurrence without subtraction in indices: $$ g_{n + 3} = 12 g_{n + 1} - 16 g_n + 48 \cdot 2^n + 25 n + 75 $$ If you multiply by $z^n$, sum over $n \ge 0$, and recognize the resulting sums: \begin{align} \sum_{n \ge 0} g_{n + k} z^k &= \frac{G(z) - g_0 - g_1 z - \ldots - z_{k - 1} z^{k - 1}}{z^k} \\ \sum_{n \ge 0} z^n &= \frac{1}{1 - z} \\ \sum_{n \ge 0} n z^n &= z \frac{\mathrm{d}}{\mathrm{d} z} \frac{1}{1 - z} \\ &= \frac{z}{(1 - z)^2} \end{align} to get: $$ \frac{G(z) - 23 - 37 z - 42 z^2}{z^3} = 12 \frac{G(z) - 23}{z} - 16 G(z) + 48 \frac{1}{1 - 2 z} + 25 \frac{z}{(1 - z)^2} + 75 \frac{1}{1 - z} $$ This gives the formidable: \begin{align} G(z) &= \frac{23 - 55 z - 267 z^2 + 1198 z^3 - 1540 z^4 + 612 z^5} {1 - 4 z + 7 z^2 - 62 z^3 + 124 z^4 - 104 z^5 + 32 z^6} \\ &= \frac{19}{1 - z} + \frac{5}{(1 - z)^2} - \frac{2}{(1 - 2 z)^2} + \frac{2}{(1 - 2 z)^3} - \frac{1}{1 + 4 z} \end{align} Using the generalized binomial theorem, in particular for natural $m$: $$ (1 - u)^{-m} = \sum_{k \ge 0} \binom{m + k - 1}{m - 1} u^k $$ and the expansion as polynomials of the binomial coefficients: \begin{align} g_n &= 19 + 5 \binom{n + 2 - 1}{2 - 1} - 2 \binom{n + 2 - 1}{2 - 1} \cdot 2^n + 2 \binom{n + 3 - 1}{3 - 1} \cdot 2^n - 4^n \\ &= 24 + 5 n + (n^2 + n) \cdot 2^n - 4^n \end{align}

The algebra help by maxima is gratefully aknowledged.

Answer 3

For a homogeneous linear recurrence $A_n = c_1A_{n-1} + ... + c_kA_{n-k}$ call let $P_A(x)= x^k - c_1x^{k-1} -... -c_k$ be it's characteristic polynomial. The main theorem about these is that for any choice of initial values for $A_0, A_1, ... ,A_k$ we can write a unique closed form for $A_n$ as a linear combination of terms of the form $n^l\lambda^n$ where $\lambda$ is a root of$P_A(x)$ of multiplicity greater than $l$. Moreover any sequence of that form will satisfy the same recursion.

Now suppose we have a non-homogeneous recurrence of the form $A'_n = c_1A'_{n-1} + ... + c_kA'_{n-k} + B_n$, where $B_n$ satisfies a homogeneous linear recurrence with characteristic polynomial $P_B(x)$. The main result here is that $A'_n$ also satisfies a homogeneous recurrence relation, and in fact it satisfies the recurrence relation with characteristic polynomial $P_{A'}(x)=P_A(x)P_B(x)$.

So in light of these two results I can look at your question and know right away that it must have a closed form of the form $A_n= a_1 + a_2n + a_32^n + a_4n2^n + a_5n^22^n+a_6(-4)^n$ and from there solving for the coefficients is easy given the first few terms.

Answer 4

The characteristic polynomial $\lambda^3-12\lambda +16$ of the corresponding homogeneous difference equation $$h_n-12 h_{n-2}+16 h_{n-3}=0\tag{1}$$ has $2$, $2$, $-4$ as roots. The general solution of $(1)$ is therefore given by $$h_n=(A+Bn) 2^n+ C(-4)^n$$ with arbitrary $A$, $B$, $C$.

On the right hand side of the given difference equation $$g_n-12 g_{n-2}+16 g_{n-3}=6\cdot 2^n+25n\tag{2}$$ we see a linear combination of a solution of $(1)$ belonging to the eigenvalue $2$ of multiplicity $2$, and a polynomial of degree $1$. For a particular solution $n\to p_n$ of $(2)$ we therefore make the "Ansatz" $$p_n:= D\, n^2\>2^n + (E + F n)$$ and now have to determine $D$, $E$, $F$ such that $(2)$ is satisfied identically in $n$. Solving the resulting system of linear equations gives $$p_n= n^2\>2^n+24+5 n\ .$$ The general solution of $(2)$ is therefore given by $$g_n=h_n+p_n=\left(A+Bn+ n^2\right)2^n + C(-4)^n+24+5n\qquad(n\in{\mathbb Z})\ .$$ Finally the constants $A$, $B$, $C$ have to be determined by the initial condtions. One obtains $A=0$, $B=1$, $C=-1$, so that we have the following end result: $$g_n=(n+n^2)\>2^n-(-4)^n+24+5n\ .$$