VulcaBlack's Inhomogeneous Linear Recurrence Q&A

[MarkFL]

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

please help

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

 

[MarkFL]

Hello VulcaBlack,

We are given the following inhomogeneous linear recurrence:

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

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

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

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

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

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

Thus, we may hypothesize that:

$$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$:

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

Now, the recurrence relation tells us:

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

Using the induction hypothesis, this becomes:

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

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

$$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]

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) $$P_{n}=3P_{n-1}+3n$$ where $$P_0=0$$

We may also write the recurrence as:

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

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

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

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

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

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

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

$$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:

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

Using the initial values, we may write:

$$P_0=k_1+k_3=0$$

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

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

Solving this system, we find:

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

Hence, we have:

$$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:

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

which has the characteristic equation:

$$r-3=0$$

Thus, a general solution to the homogeneous equation is:

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

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

$$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:

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

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

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

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

Equating coefficients, we find:

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

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

And so we have:

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

Now, by the principle of superposition, we have:

$$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:

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

And we now have the solution satisfying the recurrence as:

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