Steps to solve this inhomogeneous recurrence relation?

Question

I have the following question:

$$\begin{cases} f(0) &= 3\\ f(n) &= 9f(n-1)-14,\quad n>0 \end{cases}$$ I tackle this inhomogeneous equation by defining a new function with following relationship:

$$\begin{cases} f(n) = 9^n \times g(n) \end{cases}$$

However, I am struggling with the negative constant term and keep ending with a solution which seems illogical to me. Could someone show me the necessary steps?

Answer 1

"The general solution to an inhomogeneous linear recurrence relation is the general solution to the associated homogeneous recurrence, plus any particular solution of the inhomogeneous recurrence."

Quite a mouthful, but what is means is this:

1. Solve the homogeneous recurrence you get by eliminating the right-hand side: $f(n)=9f(n-1).$ We know the answer is $f(n) = c9^n,$ for some constant $c$.

2. Find any solution at all to the inhomogeneous recurrence. In this case we can try $f(n) \equiv k.$ That leads to $k=9k-14\implies k = 7/4.$

3. Now the general solution to the inhomogeneous recurrence is the sum of the results in the two previous steps: $f(n)= c9^n - 7/4$

4. Finally, use the initial condition to solve for $c$. I leave that to you.

Answer 2

Let $A(z) = \sum_{n=0}^\infty f(n)z^n$. Multiplying both sides of the recurrence by $z^n$ and summing over $n$, we have $$ \sum_{n=1}^\infty f(n)z^n = \sum_{n=1}^\infty 9f(n-1)z^n - \sum_{n=1}^\infty 14z^n. $$ Writing the above in terms of $A(z)$, $$ A(z) - 3 = 9zf(z) -\frac{14z}{1-z}. $$ Solving for $A(z)$, we have $$ A(z) = \frac3{1-9z} - \frac{14z}{(1-z)(1-9z)}. $$ Partial fraction decomposition yields $$ A(z) = \frac74\cdot\frac1{1-z} + \frac54\cdot\frac1{1-9z},\\ $$ with power series representation $$ A(z) = \sum_{n=0}^\infty \left(\frac 74 + \frac 54\cdot 9^n\right)z^n. $$ It follows that $$ f(n) = \frac 74 + \frac 54\cdot 9^n, \; n\geqslant0. $$

Answer 3

Your solution to this problem continues as follows. Divide the recurrence relation through by $9^n$ to obtain $g(n)=g(n-1)-\frac{14}{9^n}$ for $n\ge 1$, and $g(0)=3$. Then $$ g(n)=3-\sum_{k=1}^{n}{\frac{14}{9^k}}=3-14\frac{\frac{1}{9}-\frac{1}{9^{n+1}}}{1-\frac{1}{9}}=3-\frac{14}{8}\left(1-\frac{1}{9^n}\right)=\frac{5}{4}+\frac{7}{4}\cdot\frac{1}{9^n}, $$ so $$ f(n)=g(n)\cdot 9^n=\frac{5}{4}\cdot9^n+\frac{7}{4}=\frac{5\cdot 9^n+7}{4} $$

Answer 4

You can find several terms and see pattern: $$\begin{align} &f(1)=9f(0)-14; \\ &f(2)=9f(1)-14=9(9f(0)-14)-14=9^2f(0)-9\cdot 14-14; \\ &f(3)=9f(2)-14=9(9^2f(0)-9\cdot 14-14)-14=9^3f(0)-9^2\cdot 14-9\cdot 14-14; \\ &\cdots \\ &f(n)=9^nf(0)-(9^{n-1}+9^{n-2}+\cdots+9+1)\cdot 14=9^nf(0)-\frac{9^n-1}{9-1}\cdot 14=9^n\left(f(0)-\frac74\right)+\frac74.\end{align}$$ Now use the initial value: $$f(n)=9^n\left(3-\frac74\right)+\frac74=\frac54\cdot 9^n+\frac74.$$ The general formula:

$$f(n+1)=af(n)+b, f(0): \\ f(n)=\left(f(0)-\frac{b}{1-a}\right)\cdot a^n+\frac{b}{1-a}.$$

Applying the formula: $$f(n)=\left(3-\frac{-14}{1-9}\right)+\frac{-14}{1-9}=\frac54\cdot 9^n+\frac74.$$

Answer 5

In problems of this type I prefer to convert the sequence to a generalized Fibonacci form. I have solved this exact problem elsewhere and the solution to the general form $f(n) = Af(n-1)+B$ is given here. The result is this:

$$f_n=\frac{[(A-1)f_0+B]A^n-B}{A-1}$$

for $A\ne 1$.