Solve for A_n as n→∞: Difference Equation

[rsq_a]

This is a bit of a shot in the dark, but has anybody ever encountered a theory which can tell me what the solution of this equation:

A_n = nA_{n-2} + nA_{n-3}

behaves like, as n\to\infty? For convenience, you can set A_n = 1 for n = 0, \ldots, 3. Without the term on the right, it goes something like A_n \sim \Gamma(n/2).

 

[jasonRF]

I'm curious where this equation popped up. It is actually pretty interesting.

I think you might be able to use the Z transform to tackle this, which assumes that the Z transform of the solution exists! I rewrote your equation so that it holds for n\geq0:
A_{n+3}=(n+3)\left(A_{n+1}+A_n \right).
Then using the standard unilateral Z transform:
Z(A_n) = \tilde{A}(z) = \sum_{n=0}^{\infty}A_n z^{-n}
I get
<br /> \left(z^2 - 2 z - 3 \right) \tilde{A}(z) + \left( z + z^2 \right) \frac{d\tilde{A}(z)}{dz} = A_0 z^3 + A_1 z^2 + \left(3 A_0 + A_2 \right) z.<br />
For the homogeneous solution I get
<br /> \tilde{A}_h (z) = \gamma \left( \frac{z^3}{(z+1)^2} \right) e^{z-z^2/2},<br />
where \gamma is a constant to be determined.

For the particular solution I try variation of parameters,
<br /> \tilde{A}_p (z) = f(z) \tilde{A}_h (z),<br />
and get,
<br /> f = \int \, dz \, \frac{\left(A_0 z^2 + A_1 z + (3 A_0 + A_2) \right) (z+1)}{z^3} e^{-z+z^2/2}<br />
where I will let you determine the constant of integration. I was unable to get Mathematica to do the integral if A_0=A_1=A_2=1. However, if
A_0=0 and A_1=A_2=1 then mathematica gives me
<br /> f = \frac{1}{4} \left[3 \sqrt{\frac{2 \pi}{e}} erfi \left(\frac{z-1}{\sqrt{2}} \right) - \frac{2(3z+1)e^{-z+z^2/2}}{z^2}\right]+C<br />
where C is a constant to be determined and Mathematica defines
<br /> erfi(z)=\frac{erf(iz)}{i}<br />
where erf is the error function and i=\sqrt{-1}.

This isn't the solution to your problem, as you still have to do the inverse Z transform of \tilde{A}=\tilde{A}_h+\tilde{A}_p and determine a couple of constants I left floating around. But I think this approach is likely to lead to the solution. Please let us all know if you get further than this.

jason

 

[elect_eng]

It's not clear to me how the Z-transform can be used here. This equation is obviously nonlinear, and generally the Z-transform approach is for linear systems. If there is a way to treat the equation as linear in the limit as n goes to infinity, then this should be the first step and a clear argument would need to be presented as to why this is valid.

 

[jasonRF]

It's not clear to me how the Z-transform can be used here. This equation is obviously nonlinear, and generally the Z-transform approach is for linear systems. If there is a way to treat the equation as linear in the limit as n goes to infinity, then this should be the first step and a clear argument would need to be presented as to why this is valid.

While the equation has variable coefficients, it is certainly linear.

The approach I outlined is very similar to using Laplace or Fourier transforms to solve ODEs with variable coefficients - it will not always help, but sometimes it can yield an easier path to the solution.

 

[elect_eng]

While the equation has variable coefficients, it is certainly linear.

OK, I understand the terminology and interpretation of the equation now. This equation is classified as linear with variable coefficients. To me this is a type of equation that does not directly yield to frequency transforms. However, perhaps my knowledge is limited here. I'll look at your approach in more detail.

The approach I outlined is very similar to using Laplace or Fourier transforms to solve ODEs with variable coefficients - it will not always help, but sometimes it can yield an easier path to the solution.

I'm very familiar with using Z-transforms to solve linear difference equations with constant coefficients. It's just that I have not solved an equation with variable coefficients with this technique. But, again my training may be limited, and I would certainly like to know how to apply frequency transforms to differential and difference equations with variable coefficients.

 

[rsq_a]

Jason,

Thanks for your help. The Z-Transform is new to me, so I had to read up a little bit on it. For the moment, ignoring all the interesting work you did on the problem, my only question is what is the applicability of the Z-Transform to problems with factorially-divergent solutions?

In this case, we expect A_n \sim \Gamma(n/2 + \ldots). This has the effect that the Z-Transform is divergent everywhere in the complex plane. This is particularly troubling for the inversion process.

Suppose we have something simpler, say
A_{n+1} = n A_n

Then the inversion of the Z-Transform gives something like
A_n = \frac{1}{2\pi i} \int Ce^{-z} z^{n-1} \ dz

and we can see the \Gamma(n) function somewhere in there.

Suppose we take your homogeneous Z-Transform:

<br /> \frac{1}{2\pi i} \int \left( \frac{z^3}{(z+1)^2} \right) e^{z-z^2/2} z^{n-1} \ dz<br />

I don't quite see how the inversion will be done, or how useful it'd be. There are poles at z = \pm 1, but residue contributions certainly aren't going to get you that Gamma function behaviour as n \to ]\infty.

 

[elect_eng]

While the equation has variable coefficients, it is certainly linear.

The approach I outlined is very similar to using Laplace or Fourier transforms to solve ODEs with variable coefficients - it will not always help, but sometimes it can yield an easier path to the solution.

I don't mean to detract from this thread since it is not my thread and not my problem to solve. However, I find this very interesting and have learned quite a bit here.

I wanted to say thanks for setting me straight on this approach. My confusion came from the fact that all my previous training with transforms has been restricted to linear time-invariant systems, which are the most typical cases in engineering. Now that I understand this approach, I feel I have a new and useful tool in my bag of tricks.

One comment I can make is that when I did out the calculation, I came up with the following:

<br /> <br /> \left(z^2 - 2 z - 3 \right) \tilde{A}(z) + \left( z + z^2 \right) \frac{d\tilde{A}(z)}{dz} = A_0 z^3 + A_1 z^2 + \left(-2 A_0 + A_2 \right) z

This is slightly different from your expression. I think it is more likely that I made a mistake, but when I look at my work, I don't see where it is. Anyway, I thought I would just mention it in case the OP comes up with this answer also.

 

[jasonRF]

Jason,

Thanks for your help. The Z-Transform is new to me, so I had to read up a little bit on it. For the moment, ignoring all the interesting work you did on the problem, my only question is what is the applicability of the Z-Transform to problems with factorially-divergent solutions?
.

You are absolutely correct. I was assuming a solution with a Z transform exists, and didn't follow through that one extra step to see that I was in trouble. Sorry about that!

Sorry for hte late reply - I've been out of town working 24/7.

Cheers!

jason