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

Question

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!

Answer 1

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

Answer 2

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