Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

2. Order Linear Inhomogenous Recurrence Relations with Constant Coefficients

  1. Jul 1, 2004 #1
    I need to show that the solution of

    [tex]a_n = c_1a_{n-1} + c_2a_{n-2} + f(n)[/tex] (1)

    is of the form

    [tex]U_n = V_n + g(n)[/tex] (2)

    where [itex]V_n[/itex] 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 [itex]bU_{n-1} + dU_{n-2}[/itex] 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.
     
  2. jcsd
  3. Jul 2, 2004 #2

    arildno

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    Dearly Missed

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

    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:
    [tex]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})=[/tex]
    [tex]f(n)-f(n)=0[/tex]

    That is, V(n) is a solution of the associated homogenous recurrence relation.
     
  4. Jul 3, 2004 #3
    Interesting. I'm not convinced though since you had to assume g(n) is a solution to (1). If it isn't, then what?
     
  5. Jul 3, 2004 #4

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    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 [itex]bU_{n-1} + dU_{n-2}[/itex] is also a solution to (1)?", No, you can't because it is not true: Pluginging [itex]bU_{n-1} + dU_{n-2}[/itex] into the equation would give (b+d)f(n), not f(n). A linear combination of solutions is a solution only for homogeneous equations.
     
  6. Jul 3, 2004 #5
    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.

    I came to this conclusion as well, but I wasn't really sure so I decided to post the problem here.
     
  7. Jul 3, 2004 #6

    arildno

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    Dearly Missed

    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.
     
  8. Jul 3, 2004 #7

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    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.
     
  9. Jul 3, 2004 #8
    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 [itex]V_n[/itex] is a solution to the correspoding homogenous equation, so this implies that [itex]V_n = c_1V_{n-1} + c_2V_{n-2}[/itex]. If [itex]V_n + g(n)[/itex] is a solution to the inhomogenous equaiton, then

    [tex]\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}[/tex]

    Hence, [itex]g(n) = c_1g(n-1) + c_2g(n-2) + f(n)[/itex] 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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: 2. Order Linear Inhomogenous Recurrence Relations with Constant Coefficients
Loading...