# How do I solve a non-homogeneous recurrence relation with constant coefficients WITHOUT the initial conditions?

I have these two recurrence relations:

(i) $$a_n = 6a_{n-1} - 12a_{n-2} + 8a_{n-3} +n2^n$$

(ii) $$a_n = 6a_{n-1} - 12a_{n-2} + 8a_{n-3} +n^22^n$$

I don't know how to solve them. I tried to solve the homogeneous part, let's say for (i), but I couldn't. I assumed that

$$a_{n-1} = b_0 + b_1(n-1) + b_2(n-1)^2$$ $$a_{n-2} = b_0 + b_1(n-2) + b_2(n-2)^2$$ $$a_{n-3} = b_0 + b_1(n-3) + b_2(n-3)^2$$

And so I did

$$\phi = 6[b_0 + b_1(n-1) + b_2(n-1)^2] - 12[b_0 + b_1(n-2) + b_2(n-2)^2] + 8[b_0 + b_1(n-3) + b_2(n-3)^2] +n2^n$$

Further

$$\phi = 6[b_0 + nb_1 - b_1 + b_2n^2 - 2b_2n + b_2] - 12[b_0 + b_1n-2b_1 + b_2n^2 -4b_2n +4b_2] + 8[b_0 -b_1n-3b_1 + b_2n^2 -6b_2n +b_29)] +n2^n$$

And

$$\phi = 2b_0 +2nb_1 -6b_1 +2b_2n^2 -12b_2n +30b_2 +n2^n$$

So

$$\phi = n^2(2b_2) +n(2b_1 -12b_2) + (2b_0 -6b_1 +30b_2) +n2^n$$

Or

$$\phi = n^2(2b_2) +n(2b_1 -12b_2 + 2^n) + (2b_0 -6b_1 +30b_2)$$

After this, I've gotten clueless. I even tried to assume that:

$$\phi = n^20 +n0 + 0$$

So I would get

$$(2b_2) = 0 \implies b_2=0$$ $$(2b_1 -12b_2 + 2^n) = 0$$ $$(2b_0 -6b_1 +30b_2) = 0$$

If $b_2$= 0, then

$$2b_0 -6b_1 +30b_2 = 0$$ $$2b_0 -6b_1 +30(0) = 0$$ $$2b_0 -6b_1 = 0$$ $$2b_0 = 6b_1$$ $$b_0 = 3b_1$$

And for the other part

$$2b_1 -12b_2 + 2^n = 0$$ $$2b_1 + 2^n = 0$$ $$b_1 = 2^{n-1}$$

So I got back to my assumption and tried to discover $a_0$. In order for that to happen, I'd need $n=1$.

$$a_{n-1} = b_0 + b_1(n-1) + b_2(n-1)^2$$ $$a_{1-1} = b_0 + b_1(1-1) + b_2(1-1)^2$$ $$a_{0} = b_0 + b_1(0) + b_2(0)^2$$ $$a_{0} = b_0$$

But knowing that

$$b_0 = 3b_1 \land b_1 = 2^{n-1}$$

Therefore $$b_0 = 2^{n-1}$$ $$b_0 = 2^{1-1}$$ $$b_0 = 1$$ $$a_0=b_0 = 1$$ $$a_0 = 1$$

But we know that $$b_0 = 3b_1$$ $$1 = 3b_1$$ $$\frac{1}{3} = b_1$$

Now I formulate a partiular solution:

$$a_n = b_0 + b_1n + b_2n^2$$

Since I know the values of each:

$$a_n = 1 + \frac{1}{3}n + 0n^2$$

I will now sum the particular with this:

$$\alpha4^n + \beta n4^n + \gamma8^n$$

So

$$A_n = 1 + \frac{1}{3}n + 0n^2 + \alpha4^n + \beta n4^n + \gamma8^n$$ $$A_n = 1 + \frac{1}{3}n + \alpha4^n + \beta n4^n + \gamma8^n$$

And I believe that $A_n$ is the General Solution for the recurrence (i).

Am I right? Did my deduction fail at any part? Do I have to do more than this? Thanks in advance!

• don't deface your question. if you cannot delete a question and there is a real need to disassociate yourself from it. use "flag" to request help from moderators. Commented Nov 13, 2017 at 18:30

There are certain sets of functions $f$ such that each function $f_i(x + 1)$ is a linear combination of the other functions, that is

$$\forall k \exists c\forall x ~:~ f_k(x + 1) = \sum_j f_j(x) c_j$$

Examples are like $\{1, x, x^2, \dots, x^n\}$, $\{2^x\}$, $\{x2^x, 2^x\}$, $\{\cos(x), \sin(x)\}$. I don't know if they have a name, I call them self linear functions. In practice when problems of "non-homogenous recursive equations" are given, what they actually mean are sums of linear and self linear functions, and why textbooks don't make that explicit, I have no idea.

Anyway, if you have a recursive relation $R(n)$ of the form

$$\sum_k a_k x_{n - k} = \sum_k^m f_k(n)$$

where $f$ is a set of $m$ self linear functions, then the way to solve the problem is:

• Write out a system of $m + 1$ relations $R(n),R(n+1),\dots R(n + m)$
• Rewrite each instance of $f_i(n + z)$ with a linear combination $\sum_j f_j(n)c_j$
• With $m+1$ equations and $m$ unknown values $f_j(n)$, use linear algebra to eliminate the unknowns to get a single linear equation
• Bonus, the roots of $\sum_k a_k x_{n - k}$ will also be roots of the resulting equation because things work out nicely that way

So for example, if $R(n)$ is

$$a_n = 6a_{n-1} - 12a_{n-2} + 8a_{n-3} + n2^n$$

then organize it as

$$a_n - 6a_{n-1} + 12a_{n-2} - 8a_{n-3} = n2^n + 0\cdot 2^n$$

So the self linear set is $\{n2^n, 2^n\}$ so we need a system of 3 equations

\begin{align} % a_{n+2} - 6a_{n+1} + 12a_{n} - 8a_{n-1} &= (n + 2)2^{n + 2} + 0\cdot 2^{n + 2} \\ % a_{n+1} - 6a_{n} + 12a_{n-1} - 8a_{n-2} &= (n + 1)2^{n + 1} + 0\cdot 2^{n + 1} \\ % a_n - 6a_{n-1} + 12a_{n-2} - 8a_{n-3} &= n2^n + 0\cdot 2^n \\ % \end{align}

which is

\begin{align} % a_{n+2} - 6a_{n+1} + 12a_{n} - 8a_{n-1} &= 4n2^n + 8\cdot 2^{n} \\ % a_{n+1} - 6a_{n} + 12a_{n-1} - 8a_{n-2} &= 2n2^n + 2\cdot 2^{n} \\ % a_n - 6a_{n-1} + 12a_{n-2} - 8a_{n-3} &= n2^n + 0\cdot 2^n \\ % \end{align}

which is

$$\begin{bmatrix} 1 & -6 & 12 & -8 & 0 & 0 \\ 0 & 1 & -6 & 12 & -8 & 0 \\ 0 & 0 & 1 & -6 & 12 & -8 \\ \end{bmatrix} \begin{bmatrix} a_{n+2} \\ a_{n + 1} \\ a_{n} \\ a_{n - 1} \\ a_{n - 2} \\ a_{n - 3} \end{bmatrix} = \begin{bmatrix} 4 & 8 \\ 2 & 2 \\ 1 & 0 \\ \end{bmatrix} \begin{bmatrix} n2^n \\ 2^n \end{bmatrix}$$

Since a left null space of $\begin{bmatrix}4 & 8 \\2 & 2 \\1 & 0 \\\end{bmatrix}$ is $\begin{bmatrix} 1 & -4 & 4\end{bmatrix}$, then

$$\begin{bmatrix} 1 & -4 & 4 \end{bmatrix} \begin{bmatrix} 1 & -6 & 12 & -8 & 0 & 0 \\ 0 & 1 & -6 & 12 & -8 & 0 \\ 0 & 0 & 1 & -6 & 12 & -8 \\ \end{bmatrix} \begin{bmatrix} a_{n+2} \\ a_{n + 1} \\ a_{n} \\ a_{n - 1} \\ a_{n - 2} \\ a_{n - 3} \end{bmatrix} = \begin{bmatrix} 1 & -4 & 4 \end{bmatrix} \begin{bmatrix} 4 & 8 \\ 2 & 2 \\ 1 & 0 \\ \end{bmatrix} \begin{bmatrix} n2^n \\ 2^n \end{bmatrix}$$

$$\begin{bmatrix} 1 & -10 & 40 & -80 & 80 & -32 \\ \end{bmatrix} \begin{bmatrix} a_{n+2} \\ a_{n + 1} \\ a_{n} \\ a_{n - 1} \\ a_{n - 2} \\ a_{n - 3} \end{bmatrix} = \begin{bmatrix} 0 & 0 \end{bmatrix} \begin{bmatrix} n2^n \\ 2^n \end{bmatrix} = \begin{bmatrix} 0 \end{bmatrix}$$

The roots of the above linear equation are $2$ with multiplicity $5$, so it is

$$a_n = (A + Bn + Cn^2 + Dn^3 + En^4)2^n$$

• @GrombromK it is an equation with 5 unknown values. With 3 initial conditions you can determine the initlal 5 conditions and use that to determine the 5 unknown values. Can you solve basic linear recursions? Maybe you should start there if you are trying to learn, walk before you can run. Commented Nov 12, 2017 at 1:28
• @GrombromK Is this homework or something else? Commented Nov 12, 2017 at 1:37
• @GrombromK In the 2nd paragraph of your post you wrote "I assumed that...". Usually going around making baseless assumptions isn't going to help you solve anything. In my post, look at the last set of equations before the matrix equations. Can you see why those are true? Commented Nov 12, 2017 at 20:13

The characteristic polynomial is $$X^3-6X^2+12X-8=(X-2)^3$$ so the general solution of the homogeneous equation is $$a_n=b2^n+cn2^n+dn^22^n$$