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!
Best Answer
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:
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$$