Solving Difference Equations with Homogeneous and Inhomogeneous Parts?

[FeDeX_LaTeX]

Hello;

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;

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

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.)

 

[HallsofIvy]

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

Find a single function, F_p, that solves the entire equation.

The general solution to the entire equation is the sum, F_h+ F_p.

 

[Petr Mugver]

For every p, your equation is just an ordinary difference equation. So p is not really an unknown, rather a parameter.
Define k\equiv |2p-5|, find the k roots of unity

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

Then the solution is

F_n=\sum_{m=1}^{k-1}c_m\lambda_{m}^{n}+c+dn

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.

 

[FeDeX_LaTeX]

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

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

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

Let F_{n} = k^{n}

\Rightarrow k^{n} = 2k^{n - 2p + 5}

\Rightarrow k^{2p - 5} = 2

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

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

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

But what do I put in the "B" bracket? Where does the 'm' come from, and what does it do/why is it there?

 

[Petr Mugver]

But what do I put in the "B" bracket? Where does the 'm' come from, and what does it do/why is it there?

You have to substitute

F_n=\lambda^n

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.

 

[FeDeX_LaTeX]

You have to substitute

F_n=\lambda^n

in the omogeneous equation, not in the complete one.

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

You get a polynomial in lambda, that will give various roots, and each of them is a solution.

Do you mean this? \sqrt[2p - 5] {2}e^{\frac{2im\pi}{2p - 5}} 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.

Since the equation is linear, you can multiply each solution by an arbitrary constant and then sum up everything, that's why the "m".

Okay, that makes sense. I understand this.

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.

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?

 

[Petr Mugver]

Okay let' suppose p=4. Then your equation becomes

F_n-2F_{n-3}=1

Let's put

F_n=\lambda^n

Substituting in the homogeneous equation tou get

\lambda^3=2

and you have 3 roots:

\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}

So the solution of the homogeneous eq is

F^{Omog}_n=c_1\lambda_1^n+c_2\lambda_2^n+c_3\lambda_3^n

Now we need a particular solution of the inhomogeneous equation. Let's try

F^{Part}_n=constant

Substituting, we find constant=-1, so finally

F_n=c_1\lambda_1^n+c_2\lambda_2^n+c_3\lambda_3^n-1

 

[FeDeX_LaTeX]

Thanks. I think I know how to solve it now.