Finding a closed form for $f(n)=f(n-1)-9f(n-2)+9f(n-3)+5$ (with complex numbers)

Question

I'm trying to get a closed form for the non-homogeneous linear recurrence $$f(n)=f(n-1)-9f(n-2)+9f(n-3)+5$$ The initial values are $$f(0) = 1,\ f(1) = 1,\ f(2) = 2$$ But I'm having trouble when I found imaginary numbers.

Let's see: I know there are homogeneous linear recurrences associated to this non-homogeneous one, in this case it is $f(n) = f(n-1) - 9f(n-2) + 9f(n-3)$. Its characteristic equation is $x^3-x^2+9x-9 = 0$.

On the other hand, the non-homogeneous part is $1^n\cdot 5$ so, as I've been told, there is a homogeneous linear recurrence that is similar to the first one (non-homogeneous) and that has the characteristic equation $(x-5)(x^3-x^2+9x-9)$ but, when I find the roots of the second polynomial, I get $(x-1)(x^2+9)$ and this second part has no real roots... so...

I don't know if it is correct to write the homogeneous linear recurrence as: $$f(n) = a + 5^n b + (3i)^n c + (-3i)^n d$$

Actually, I have no idea of how I should do this problem from this moment onward. Could you help me? Thank you!

Answer 1

Using method of generating functions.

Let us write equation for general term: $$ f_n=f_{n-1}-9f_{n-2}+9f_{n-3}+5-4[n=0]-5[n=1]+5[n=2] $$ Make transform to $G(z):$ $$ G=zG-9z^2G+9z^3G+\frac{5}{1-z}-4-5z+5z^2\\ G=\frac{5}{(1-z)(1-z+9z^2-9z^3)}-\frac{4+5z-5z^2}{1-z+9z^2-9z^3} $$ In form of partial fractions: $$ G=\frac{36+81z}{10(1+9z^2)}+\frac{9}{10(1-z)}+\frac{1}{2(1-z)^2}-\frac{36+86z}{10(1+9z^2)}-\frac{4}{10(1-z)}\\ G=\frac{-5z}{10(1+9z^2)}+\frac{5}{10(1-z)}+\frac{1}{2(1-z)^2}\\ G=\frac{-z}{2(1+9z^2)}+\frac{1}{2(1-z)}+\frac{1}{2(1-z)^2} $$

And one more partial fraction for first addendum: $$ G=\frac{3i}{18}\left[\frac{A}{1+3iz}-\frac{A^*}{1-3iz}\right]+\frac{1}{2(1-z)}+\frac{1}{2(1-z)^2}$$

Where $A=A^*=-\frac{1}{2}$ Now apply inverse transform: $$ f(n)=\frac{i}{6}A(-3i)^n-\frac{i}{6}A^*(3i)^n+\frac{1}{2}+\frac{1}{2}(n+1)\\ f(n)=\frac{1}{2}+\frac{1}{2}(n+1)+\frac{i}{12}(3i)^n-\frac{i}{12}(-3i)^n $$ As it can be ssen, you had almost proper equation, with only term $(+5)$ mistreated. Reason: we add it, not multiply. By the way, important property: constants $c$ and $d$ must be self-conjuncted, because $f(n)$ is real-valued sequence.

And finally, let us rewrite expression a bit. $$ f(n)=\frac{1}{2}+\frac{1}{2}(n+1)+\frac{i}{12}(3i)^n\left[1-(-1)^n\right]\\ f(n)= \begin{cases} 1+k,\quad \quad \quad \quad \quad \text{for n=2k} \\ \frac{3}{2}+k-\frac{(-9)^k}{2},\quad \text{for n=2k+1} \end{cases} $$

Answer 2

You have the characteristic equation $$x^3 - x^2 + 9x - 9 = 0 \\ \implies (x - 1)(x^2 + 9) = 0 \\ \implies x = 1 \;\; \text{OR} \;\; 3i \;\; \text{OR} \;\; -3i$$ Thus the solutions to the homogeneous part are $$f(n) = c_1 \cdot 1^n + c_2 \cdot (3i)^n + c_3 \cdot (-3i)^n$$ But we have a constant nonhomogeneous part, which must satisfy the same recurrence relation. Let us guess that the nonhomogeneous solution is of the form $an + b$. $$an + b = a(n-1) + b - 9(a(n-2) + b) + 9(a(n-3) + b) + 5 \\ \implies 0 = -a + 18a - 27a + 5 \\ \implies -10a = -5 \\ \implies a = \frac{-5}{-10} = \frac{1}{2}$$ Since the $b$ term is absent, $b = 0$. Now we simply have $$f(n) = c_1(1)^n + c_2(3i)^n + c_3(-3i)^n + \frac{1}{2}n$$ which we solve for $f(0)$, $f(1)$, and $f(2)$: $$\begin{align*} f(0) = 1 &= c_1 + c_2 + c_3 \\ f(1) = 1 &= c_1 + 3ic_2 - 3ic_3 + \frac{1}{2} \\ f(2) = 2 &= c_1 - 9c_2 - 9c_3 + 1 \end{align*}$$ to get $c_1 = 1$, $c_2 = \frac{i}{12}$, $c_3 = -\frac{i}{12}$. Finally we have $$f(n) = 1 + \frac{(3i)^n - (-3i)^n}{12}i + \frac{1}{2}n$$