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:

\(\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]

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}\)