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

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

• You're right about it being pretty nasty. The generating function is useful to get asymptotics (you only need to look at the singularities), but actually carrying out the partial fraction decomposition seems to require more persistence than is justifiable. :-) – ShreevatsaR Apr 21 '14 at 5:25
• All but a couple of the partial fraction constants can be computed directly (without solving a system of linear equations), just by multiplying the rational function and the partial fraction template by $4z+1$ or $(1-z)^2$ (for example) and then plugging in $z=-1/4$ or $z=1$. That leaves a much simpler linear algebra problem. - By the way, do you mean for the denominator to include both $(2z-1)^2$ and $1-2z$? – Greg Martin Apr 21 '14 at 5:49
• Another relatively straightforward approach (though you still have to match initial conditions) would be to solve the two inhomogeneous equations $g_n = 12g_{n-2}-16g_{n-3}+6\cdot 2^n$ and $g_n = 12g_{n-2}-16g_{n-3}+25n$; if $j_n$ is a solution of the first inhomogeneous equation and $k_n$ is a solution of the second, then (convince yourself of this!) $j_n+k_n$ is a solution of the full inhomogeneous equation. – Steven Stadnicki Apr 21 '14 at 6:02
• @JackReacher: Actually the right expression is $48z^3/(1-2z)$: need to pull out both $2^3$ and $z^3$, to make the sum run from $0$ instead of $3$. Or you can do it as $6/(1-2z) - 6(1 + 2z + 2^2z^2)$ and get the same thing. – ShreevatsaR Apr 21 '14 at 7:08
• @GregMartin - Used your suggestions to knock out 3 of the constants, which made the rest of the computation somewhat easier. Thanks! – JackReacher Apr 22 '14 at 23:37

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$$

• I independently got the same $A(z)$ as you. (Well, I plugged in $\dfrac{23 + 12z - 284z^2 + 48z^3/(1-2z) + 25z/(1-z)^2}{1 - 12z^2 + 16z^3}$ into Wolfram Alpha: apart from the first expression above, it also gives the partial fraction decomposition thankfully.) The OP mistakenly wrote the $48z^3/(1-2z)$ term as $6/(1-2z)$, so that's the reason for the difference. – ShreevatsaR Apr 21 '14 at 7:09
• Thank you for confirming ! Cheers. – Claude Leibovici Apr 21 '14 at 7:11
• Also confirmed that the messy expression for $g_n$ given by the above, namely $19 - 2(n+1)2^n + 5(n+1) + 2\frac{(n+1)(n+2)}{2}2^n - (-4)^n$ does indeed simplify to $-(-4)^n + 2^n(n+1)n + 5n + 24$ as you got. :-) – ShreevatsaR Apr 21 '14 at 7:20
• @ClaudeLeibovici - Thanks for your answer, I'll continue working through mine to see if I come up with the same thing. But kind of a dumb question here: since $(1-2z)^3$ has multiplicity $3$, wouldn't you need an extra term for $\frac{C}{(1-2z)}$ in your partial fraction decomposition? – JackReacher Apr 21 '14 at 8:37
• Yes, but in this case, $C$ happens to equal $0$. – Greg Martin Apr 21 '14 at 12:48

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\ .$$

• Thanks, I see where I was going wrong with my approach now. Not trying the correct form for $p_n$. – JackReacher Apr 22 '14 at 0:06

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.

• thanks. When you go from your 'formidable' G(z) to the partial fraction decomposition - would it be fair to say that there is no short cut here, but to simply hash out the algebra? I managed to do it, but just wondering if there was a shorter way. – JackReacher Apr 22 '14 at 23:35
• @JackReacher, I don't see a simple way around it. Sorry. – vonbrand Apr 23 '14 at 1:17
• no problems. Thanks! – JackReacher Apr 23 '14 at 1:20

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.

• Where can I find a proof of these results? Especially the one about a sequence satisfying a nonhomogeneous recurrence also satisfying a homogeneous one. – weux082690 Sep 23 '17 at 13:52
• Keep in mind I wrote this answer like three years ago, so I may have had a different source in mind at the time, but it's probably all in Stanley's enumerative combinatorics. I think it's an easy calculation to verify that the recursion corresponding to the product of polynomials works though. – Nate Sep 23 '17 at 14:46