$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.
Best Answer
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$$