# VulcaBlack's question at Yahoo! Answers regarding an inhomogeneous linear recurrence

#### MarkFL

Staff member
Here is the question:

Given the following recurrence relation, guess a closed-form solution:?

Given the following recurrence relation, guess a closed-form solution:
relation: P(n) = { 0 if n = 0
3*P(n-1) + 3n if n>0}

2. prove by induction

I have posted a link there to this topic so the OP can see my work.

#### MarkFL

Staff member
Hello VulcaBlack,

We are given the following inhomogeneous linear recurrence:

$$\displaystyle P_{n}=3P_{n-1}+3n$$ where $$\displaystyle P_0=0$$

If we are to "guess" a solution, we may look at the first several terms:

$$\displaystyle P_0=0=\frac{3^{0+2}-6\cdot0-9}{4}$$

$$\displaystyle P_1=3\cdot0+3\cdot1=3=\frac{3^{1+2}-6\cdot1-9}{4}$$

$$\displaystyle P_2=3\cdot3+3\cdot2=15=\frac{3^{2+2}-6\cdot2-9}{4}$$

$$\displaystyle P_3=3\cdot15+3\cdot3=54=\frac{3^{3+2}-6\cdot3-9}{4}$$

Thus, we may hypothesize that:

$$\displaystyle P_{n}=\frac{3^{n+2}-6n-9}{4}$$

We have already demonstrated the base case, and a few successive cases to be true, so let's now state the induction hypothesis $P_k$:

$$\displaystyle P_{k}=\frac{3^{k+2}-6k-9}{4}$$

Now, the recurrence relation tells us:

$$\displaystyle P_{k+1}=3P_{k}+3(k+1)$$

Using the induction hypothesis, this becomes:

$$\displaystyle P_{k+1}=3\left(\frac{3^{k+2}-6k-9}{4} \right)+3(k+1)$$

$$\displaystyle P_{k+1}=\frac{3^{k+3}-18k-27+12(k+1)}{4}$$

$$\displaystyle P_{k+1}=\frac{3^{(k+1)+2}-6(k+1)-9}{4}$$

We have derived $P_{k+1}$ from $P_{k}$ thereby completing the proof by induction.

#### MarkFL

Staff member
I wish to demonstrate also two techniques for deriving the solution which requires neither guessing, nor proof by induction.

One way to derive a solution is through a technique called symbolic differencing, in which we may transform the recurrence into a homogenous one, and use the characteristic roots to obtain the closed form, and then use the initial values to determine the parameters. Let's begin with the given recurrence:

(1) $$\displaystyle P_{n}=3P_{n-1}+3n$$ where $$\displaystyle P_0=0$$

We may also write the recurrence as:

(2) $$\displaystyle P_{n+1}=3P_{n}+3(n+1)$$

Subtracting (1) from (2), we obtain:

(3) $$\displaystyle P_{n+1}=4P_{n}-3P_{n-1}+3$$

(4) $$\displaystyle P_{n+2}=4P_{n+1}-3P_{n}+3$$

Subtracting (3) from (4), we obtain:

$$\displaystyle P_{n+2}=5P_{n+1}-7P_{m}+3P_{n-1}$$

Now we have a homogeneous recurrence, whose associated characteristic equation is:

$$\displaystyle r^3-5r^2+7r-3=(r-3)(r-1)^2=0$$

Based on the roots and their multiplicities, we may give the closed form as:

$$\displaystyle P_n=k_1+k_2n+k_3\cdot3^n$$

Using the initial values, we may write:

$$\displaystyle P_0=k_1+k_3=0$$

$$\displaystyle P_1=k_1+k_2+3k_3=3$$

$$\displaystyle P_2=k_1+2k_2+9k_3=15$$

Solving this system, we find:

$$\displaystyle k_1=-\frac{9}{4},\,k_2=-\frac{3}{2},\,k_3=\frac{9}{4}$$

Hence, we have:

$$\displaystyle P_n=-\frac{9}{4}-\frac{3}{2}n+\frac{9}{4}\cdot3^n=\frac{3^{n+2}-6n-9}{4}$$

Another way to solve the recurrence is to use the method of undetermined coefficients. We first solve the associated homogeneous recurrence:

$$\displaystyle P_{n}-3P_{n-1}=0$$

which has the characteristic equation:

$$\displaystyle r-3=0$$

Thus, a general solution to the homogeneous equation is:

$$\displaystyle h_{n}=c_13^n$$

Now, since the inhomogeneous term in the original recurrence is $$\displaystyle 3n$$, we seek a particular solution of the form:

$$\displaystyle p_{n}=An+B$$

where the parameters $A$ and $B$ are to be determined. Substituting this expression for $P_n$ into the original recurrence, we obtain:

$$\displaystyle (An+B)-3(A(n-1)+B)=3n$$

$$\displaystyle An+B-3(An-A+B)=3n$$

$$\displaystyle An+B-3An+3A-3B=3n$$

$$\displaystyle -2An+(3A-2B)=3n+0$$

Equating coefficients, we find:

$$\displaystyle -2A=3\,\therefore\,A=-\frac{3}{2}$$

$$\displaystyle 3A-2B=0\,\therefore\,B=-\frac{9}{4}$$

And so we have:

$$\displaystyle p_{n}=-\frac{3}{2}n-\frac{9}{4}$$

Now, by the principle of superposition, we have:

$$\displaystyle P_n=h_n+p_n=c_13^n-\frac{3}{2}n-\frac{9}{4}$$

Now we may determine the parameter $c_1$ from the given initial value:

$$\displaystyle P_0=c_1-\frac{9}{4}=0\,\therefore\,c_1=\frac{9}{4}$$

And we now have the solution satisfying the recurrence as:

$$\displaystyle P_n=\frac{9}{4}3^n-\frac{3}{2}n-\frac{9}{4}=\frac{3^{n+2}-6n-9}{4}$$