- Thread starter
- Admin
- #1
VulcaBlack's question at Yahoo! Answers regarding an inhomogeneous linear recurrence
- Thread starter MarkFL
- Start date
- Thread starter
- Admin
- #2
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.
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.
- Thread starter
- Admin
- #3
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}\)
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}\)