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 Vn is a solution to the corresponding homogeneous equation then Vn+ 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 Vn is a solution to the corresponding homogeneous equation then Vn+ 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 Vn+ 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(xn) is some linear recurrance relation- that is A(xn)= axn+2+ bxn+1+cxn, etc. A "homogeneous" equation is of the form A(xn)= 0. It's
easy to show that any linear combination of solutions is still a solution: If Vn and Un are satisfy A(Un)= 0 and A(Vn)= 0 then A(pUn+ qVn)= 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(pUn+qVn)= p A(Un)+ q A(Vn)= p(0)+ q(0)= 0.

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

That is, the difference between Rn and Sn satisfies the homogeneous equation: Rn- Sn= Un for some U satisfying the homogeneous equation. That is the same as saying Rn= Un+ Sn.

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 Vn + 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*}
V_n + g(n) &= c_1(V_{n-1} + g(n-1)) + c_2(V_{n-2} + g(n-2)) + f(n) \\
&= c_1V_{n-1} + c_2V_{n-2} + c_1g(n-1) + c_2g(n-2) + f(n) \\
&= V_n + c_1g(n-1) + c_2g(n-2) + f(n)
\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.