Proof for transforming a non-homogenous linear recurrent into a homogenous linear recurrence.

30 Views Asked by At

I need to prove that $b^np(n)$ becomes $(r-b)^{d+1}$ as shown in the theorem below.

A nonhomogeneous linear recurrence of the form $$a_0t_n + a_1t_{n-1} + \cdots + a_kt_{n - k} = b^np(n)$$ can be transformed into a homogeneous linear recurrence that has the characteristic equation $$\left(a_0r^k + a_1r^k + \cdots + a_k\right)(r - b)^{d + 1} = 0,$$ where $d$ is the degree of $p(n)$. Notice that the characteristic equation is composed of two parts:
$1.$ The characteristic equation for the corresponding homogeneous recurrence,
$2.$ A term obtained from the nonhomoegenous part of the recurrence.
If there is more than one term like $b^np(n)$ on the right side, each one contributes to the characteristic equation.