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

Solving Difference Equations with Homogeneous and Inhomogeneous Parts?

  1. Aug 7, 2010 #1


    User Avatar
    Gold Member


    This is not a homework question, but something I was wondering about solving difference equations.

    For example, how would I solve the following difference equation;

    [tex]F_{n} = 2F_{n - 2p + 5} + 6p - 17; n, p \in \mathbb N[/tex]

    Since it has homogeneous and inhomogeneous parts together (and two unknowns - n and p) I don't know what to do. Any help on how I would solve this would be appreciated, thanks.

    (For where I got this formula from - I found this when thinking about a formula that would give me the minimum number of moves to complete a game of Tower of Hanoi with n discs and p poles.)
    Last edited: Aug 7, 2010
  2. jcsd
  3. Aug 7, 2010 #2


    User Avatar
    Science Advisor

    Since that is a linear equation, you can do this:
    Find the general solution to the homogeneous equation [itex]F_n= F_{n- 2p+ 5}[/itex]. call that "[itex]F_h[/itex]".

    Find a single function, [itex]F_p[/itex], that solves the entire equation.

    The general solution to the entire equation is the sum, [itex]F_h+ F_p[/itex].
  4. Aug 7, 2010 #3
    For every p, your equation is just an ordinary difference equation. So p is not really an unknown, rather a parameter.
    Define [tex]k\equiv |2p-5|[/tex], find the k roots of unity

    [tex]\lambda^k=1\qquad\rightarrow \lambda_m=e^{i2m\pi/k},\qquad m=0,1,\dots,k-1[/tex]

    Then the solution is


    The coeeficients c and d are really just one coefficient, because you get a linear relationship between them when you substitute the solution in the equation. To get the other coefficients you need initial conditions.
    Last edited: Aug 7, 2010
  5. Aug 7, 2010 #4


    User Avatar
    Gold Member

    Sorry, I left out the co-efficient 2. It should read;

    [tex]F_{n} = 2F_{n - 2p + 5} + 6p - 17; n, p \in \mathbb N[/tex]

    I'm not sure I completely understand what to do; is this working correct?

    Let [tex]F_{n} = k^{n}[/tex]

    [tex]\Rightarrow k^{n} = 2k^{n - 2p + 5}[/tex]

    [tex]\Rightarrow k^{2p - 5} = 2[/tex]

    [tex]\Rightarrow k = \sqrt[2p - 5] {2}e^{\frac{2im\pi}{2p - 5}}[/tex] for [tex]p \geq 3[/tex].

    Where do I go from here? I think I have to put the first root in like so;

    [tex]F_{n} = A\left(\sqrt{2}e^{\frac{2i\pi}{2p - 5}}\right)^{n} + B(\cdots)^{n}[/tex]

    But what do I put in the "B" bracket? Where does the 'm' come from, and what does it do/why is it there?
  6. Aug 7, 2010 #5
    You have to substitute


    in the omogeneous equation, not in the complete one.
    You get a polynomial in lambda, that will give various roots, and each of them is a solution. Since the equation is linear, you can multiply each solution by an arbitrary constant and then sum up everything, that's why the "m".
    This way you get a solution of the homogeneous equation. To get a complete solution, you have to add another term, that in your particular example must be simply a constant.
  7. Aug 7, 2010 #6


    User Avatar
    Gold Member

    But isn't that what I've done by saying that [tex]F_{n} = k^{n}[/tex] for the homogeneous part?

    Do you mean this? [tex]\sqrt[2p - 5] {2}e^{\frac{2im\pi}{2p - 5}}[/tex] I think it gives the roots for k, but I'm not entirely sure what to do from there except to just assume that whole thing is one root for k.

    Okay, that makes sense. I understand this.

    Is the term that I have to add (17 - 6p)?

    Because if we say that the homogeneous part is t, then t = 2t + 6p - 17, so t = 17 - 6p? Or not?
  8. Aug 7, 2010 #7
    Okay let' suppose p=4. Then your equation becomes


    Let's put


    Substituting in the homogeneous equation tou get


    and you have 3 roots:

    [tex]\lambda_1=2^{1/3}\qquad \lambda_2=2^{1/3}e^{2\pi i/3}\qquad \lambda_3=2^{1/3}e^{-2\pi i/3}[/tex]

    So the solution of the homogeneous eq is


    Now we need a particular solution of the inhomogeneous equation. Lets try


    Substituting, we find constant=-1, so finally

    Last edited: Aug 8, 2010
  9. Aug 8, 2010 #8


    User Avatar
    Gold Member

    Thanks. I think I know how to solve it now.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook