2. Order Linear Inhomogenous Recurrence Relations with Constant Coefficients

[e(ho0n3]

I need to show that the solution of

a_n = c_1a_{n-1} + c_2a_{n-2} + f(n) (1)

is of the form

U_n = V_n + g(n) (2)

where V_n is the solution of a 2. order linear homogenous recurrence relation with constant coefficients.

Could I use the argument that if (2) is a solution to (1), then there are constants b and d such that bU_{n-1} + dU_{n-2} is also a solution to (1)? This is the only thing I can think of (and am familiar with since the book uses this argument in two proofs). I don't know anything about generating functions so I don't know what to do.

 

[arildno]

Write your equation as:
a_{n}-c_{1}a_{n-1}-c_{2}a_{n-2}=f(n) (1)

Assume g(n) is a solution of (1)

Let U(n) be another solution of (1)

Let V(n) be the difference, V(n)=U(n)-g(n)
Then we have:
V_{n}-c_{1}V_{n-1}-c_{2}V_{n-2}=U_{n}-c_{1}U_{n-1}-c_{2}U_{n-2}-(g_{n}-c_{1}g_{n-1}-c_{2}g_{n-2})=
f(n)-f(n)=0

That is, V(n) is a solution of the associated homogenous recurrence relation.

 

[e(ho0n3]

Write your equation as:
a_{n}-c_{1}a_{n-1}-c_{2}a_{n-2}=f(n) (1)

Assume g(n) is a solution of (1)

Let U(n) be another solution of (1)

Let V(n) be the difference, V(n)=U(n)-g(n)
Then we have:
V_{n}-c_{1}V_{n-1}-c_{2}V_{n-2}=U_{n}-c_{1}U_{n-1}-c_{2}U_{n-2}-(g_{n}-c_{1}g_{n-1}-c_{2}g_{n-2})=
f(n)-f(n)=0

That is, V(n) is a solution of the associated homogenous recurrence relation.

Interesting. I'm not convinced though since you had to assume g(n) is a solution to (1). If it isn't, then what?

 

[HallsofIvy]

Interesting. I'm not convinced though since you had to assume g(n) is a solution to (1). If it isn't, then what?

That was an (unmentioned) condition of the original problem: if V_n is a solution to the corresponding homogeneous equation then V_n+ g(n) is a solution to the inhomgeneous equation if and only if g(n) is a particular solution to the inhomogeneous equation.

To answer the poster's original question: "Could I use the argument that if (2) is a solution to (1), then there are constants b and d such that bU_{n-1} + dU_{n-2} is also a solution to (1)?", No, you can't because it is not true: Pluginging bU_{n-1} + dU_{n-2} into the equation would give (b+d)f(n), not f(n). A linear combination of solutions is a solution only for homogeneous equations.

 

[e(ho0n3]

That was an (unmentioned) condition of the original problem: if V_n is a solution to the corresponding homogeneous equation then V_n+ g(n) is a solution to the inhomgeneous equation if and only if g(n) is a particular solution to the inhomogeneous equation.

I really wish I had the ability to figure this stuff out, like you seem to do. I still don't follow they line of logic being employed to determine that g(n) must be a solution in order for V_n+ g(n) to be a solution and vice versa.

To answer the poster's original question: "Could I use the argument that if (2) is a solution to (1), then there are constants b and d such that bU_{n-1} + dU_{n-2} is also a solution to (1)?", No, you can't because it is not true: Pluginging bU_{n-1} + dU_{n-2} into the equation would give (b+d)f(n), not f(n).

I came to this conclusion as well, but I wasn't really sure so I decided to post the problem here.

 

[arildno]

Suppose V(n) is a solution of the hom. equation.
Assume that V(n)+g(n) is a solution of the inhom. equation.

Then it follows that g(n) itself is a solution of the inhom. solution.

The converse:
Assume that g(n) is a solution of the inhom. equation.

It then follows that V(n)+g(n) is a solution of the inhom. equation.

 

[HallsofIvy]

To expand on what arildno just said: Suppose A(x_n) is some linear recurrance relation- that is A(x_n)= ax_n+2+ bx_n+1+cx_n, etc. A "homogeneous" equation is of the form A(x_n)= 0. It's
easy to show that any linear combination of solutions is still a solution: If V_n and U_n are satisfy A(U_n)= 0 and A(V_n)= 0 then A(pU_n+ qV_n)= 0 also for any number p and q. "Second order" or "constant coefficients" are not needed but "linear" is. You simply use the definition of A (or more generally the definition of "linear") to show that A(pU_n+qV_n)= p A(U_n)+ q A(V_n)= p(0)+ q(0)= 0.

Now, suppose R_n and S_n are both solutions to the non-homogeneous equation A()= f(n)- that is, that A(R_n)= f(n) and A(S_n)= f(n). Again, using the fact that A is linear, A(R_n- S_n)= A(R_n)- A(S_n)= f(n)- f(n)= 0.

That is, the difference between R_n and S_n satisfies the homogeneous equation: R_n- S_n= U_n for some U satisfying the homogeneous equation. That is the same as saying R_n= U_n+ S_n.

The exact same this is true, incidently, for homogenous and non-homogeneous differential equations.

 

[e(ho0n3]

Suppose V(n) is a solution of the hom. equation.
Assume that V(n)+g(n) is a solution of the inhom. equation.

Then it follows that g(n) itself is a solution of the inhom. solution.

The converse:
Assume that g(n) is a solution of the inhom. equation.

It then follows that V(n)+g(n) is a solution of the inhom. equation.

I still don't see how the consequent follows from the antecedent. Here is my reasoning on why g(n) must be assumed to be a solution of the inhom. equation so that V_n + g(n) is a solution:

We know that V_n is a solution to the correspoding homogenous equation, so this implies that V_n = c_1V_{n-1} + c_2V_{n-2}. If V_n + g(n) is a solution to the inhomogenous equaiton, then

\begin{align*}<br /> V_n + g(n) &amp;= c_1(V_{n-1} + g(n-1)) + c_2(V_{n-2} + g(n-2)) + f(n) \\<br /> &amp;= c_1V_{n-1} + c_2V_{n-2} + c_1g(n-1) + c_2g(n-2) + f(n) \\<br /> &amp;= V_n + c_1g(n-1) + c_2g(n-2) + f(n)<br /> \end{align}

Hence, g(n) = c_1g(n-1) + c_2g(n-2) + f(n) which statisfies the inhom. recurrence relation and so g(n) must be a solution of it. Maybe this is what you guys have been saying all along, but I'm just to dense to see it.