# Solve the following inhomogeneous recurrence relation...

Printable View

• Oct 29th 2012, 08:58 AM
TimsBobby2
Solve the following inhomogeneous recurrence relation...
Solve the inhomogeneous recurrence relation

an=3an-1+n2-3 with a0=1

Any help please? I tried a few different cases which got me nowhere.
• Oct 29th 2012, 11:15 AM
MarkFL
Re: Solve the following inhomogeneous recurrence relation...
You may use the process of symbolic differencing to get a homogeneous recurrence. We are given:

(1) $\displaystyle a_{n}=3a_{n-1}+n^2-3$

Now, replace $\displaystyle n$ with $\displaystyle n+1$ to get:

(2) $\displaystyle a_{n+1}=3a_{n}+(n+1)^2-3$

Now, subtract (1) from (2) to get another recurrence. Repeat this process until you have a homogeneous recurrence, from which you may determine the closed form from the characteristic roots, and then determine the parameters from the initial values.
• Oct 29th 2012, 11:21 AM
johnsomeone
Re: Solve the following inhomogeneous recurrence relation...
Think of recurrence equations as being like a discrete type of differential equation.

1) Solve the homogeneous case: $\displaystyle \tilde{a}_n = 3\tilde{a}_{n-1}$ to get $\displaystyle \tilde{a}_n = c3^n.$

2) Now use variation of parameters. Try: $\displaystyle a_n = 3^nb_n \ (\text{with }1 = a_0 = 3^0b_0 = b_0).$

$\displaystyle a_n = 3a_{n-1} + n^2-3 \text{ becomes } 3^nb_n = 3(3^{n-1}b_{n-1}) +n^2-3 = 3^nb_{n-1}+ n^2-3,$

$\displaystyle \text{giving } b_n = b_{n-1}+ \frac{n^2-3}{3^n}, \text{ with }b_0 = 1.$

$\displaystyle \text{That's solveable as a sum: } b_n = b_0 + \sum_{k=1}^n \frac{k^2-3}{3^k} \text{ for } n \ge 1.$

You can further simply that.