Difference/Recurrence Equations Explained

[Benny]

Hi I'm just wondering what difference/recurrence equations are about. From what I can recall from the bits and pieces I've readed, difference equations are somewhat similar or an analogue of differential equations. I've read through some things on first and second order difference equations but I don't really understand what they are about.

My book introduces difference equations as summations. They seem to be equations involving summations with different indices. I know what I've said is a little vague so here is an example question I have(not from the book I referred to).

Q. Find the general solution of the following difference equation.

$$y_{n + 1} - y_n = 2$$

Answer: $$y_n = A\left( {\frac{1}{2}} \right)^n + 2$$

Can someone explain to me what the equation actually means?. Any sort of explanation or references to useful websites would also be good. As I alluded to before I don't actually see the connection between difference equations and differential equations. Is it like when you have a real function f(x) and you the sequence f(n)? Any help would be appreciated.

 

[AKG]

I have no idea what this could mean. Assuming that solution is correct:

$$y_{n+1} - y_{n} = A\left (\frac 12 \right )^{n+1} + 2 - A\left (\frac 12 \right )^n - 2 = -\frac 12A\left (\frac 12 \right )^n$$

so

$$2 = -\frac 12A\left (\frac 12 \right )^n$$

$$A = -2^{n+2}$$

$$y_n = -4 + 2 = -2$$

 

[lurflurf]

The two main ways difference and differential equations are related are
1. Analogous formula
2. differential equations can be seen as differential equations where the differences are taken to zero in a limit sense.
your equation
$$y_{n+1}-y_n=2$$
perform indefinite summation on both sides
$$\sum_{n=0}^{n-1}(y_{n+1}-y_n)=\sum_{n=0}^{n-1}2$$

$$y_{n}-y_0=2n$$

$$y_n=y_0+2n$$
where y0 is the constant to be found by initial conditions.
The equation means find the functions with the given difference.

http://mathworld.wolfram.com/RecurrenceEquation.html

 

[Tide]

What you have is an arithmetic series and your "answer" is incorrect. The correct solution is

$$y_n = y_1 + (n-1)\times 2$$

where $y_1$ is an initial value. The answer you show looks like the solution of a geometric series. Did you copy the problem correctly?

 

[Benny]

I left out a factor 2 for the first term in the question. It should be $$2y_{n + 1} - y_n = 2$$ and the answer is the one that I included with my first post.

 

[Tide]

In that case, I would subtract $y_n$ from both sides to make it look like a difference equation and see where it leads:

$$2 (y_{n+1} - y_n}) = 2 - y_n$$

or

$$y_{n+1} - y_n = \frac {2-y_n}{2}$$

The right side suggests defining a new variable $z_n$ such that $z_n = y_n - 2$ or [itex]y_n = z_n + 2[/tex]. Substitute that into the equation:

$$z_{n+1} + 2 - z_n - 2 = -\frac {1}{2} z_n$$

or

$$z_{n+1} - z_n = -\frac {1}{2} z_n$$

Notice the additive constants are now gone! In fact, if we now just add $z_n$ to both side we obtain the simple relation

$$z_{n+1} = \frac {1}{2} z_n$$

which is just a simple geometric series with the solution

$$z_n = \left( \frac {1}{2} \right)^{n-1} z_1$$

You should be able to go from there and find the general solution for $y_n$ using the defintion of $z_n$ that we used.

 

[Hurkyl]

We can do other things, inspired by the methods of differential equations.

First, some notation:

$$Ey_n := y_{n+1}$$

Δ = E - 1
or, equivalently,

$$\Delta y_n := y_{n+1} - y_n$$


So, you have the equation 2Ey - y = 2. We'd like to rewrite it as Tide suggested. The "easy" way is to recognize you can subtract y from both sides, but if you didn't notice that, you could use E = 1 + Δ to get:

2 (1 + Δ) y - y = 2
2y + 2Δy - y = 2
2Δy + y = 2
Δy + (1/2) y = 1


First, the "plug and chug" method: this will be uninspired, but it does give you a solution to any difference equation with summations and products. You can safely skip down to the next section if you like.

In an ordinary differential equation we look for an integrating factor μ... we can do the same here. Notice that:

Δ(μy) = Eμ Δy + Δμ y

So, what we want is (Δμ) / Eμ = (1/2). Using Δ = E - 1, we can rearrange this to form:

Eμ = 2μ

By picking an initial value for $\mu_0$, in the general case we can write μ as a product. Here, however, we can find the closed form solution:

$$\mu_n = 2^n$$

So now, we have:

Δy + (1/2) y = 1
Δy + (Δμ)/(Eμ) y = 1
Eμ Δy + Δμ y = Eμ
Δ(μy) = Eμ

And now, we can take an antidifference (i.e. a sum). Notice that:

$$\sum_{k = 0}^{n-1} \Delta z_k = z_n - z_0$$

We can apply this here to get:

$$\begin{equation*} \begin{split} \mu_n y_n - \mu_0 y_0 &= \sum_{k = 0}^{n-1} E \mu_k \\ 2^n y_n - y_0 &= \sum_{k = 0}^{n - 1} 2^{k+1} \\ &= 2^{n+1} - 2 \\ y_n &= 2^{-n} y_0 + 2 - 2^{1-n} \\ &= A 2^{-n} + 2 \end{split} \end{equation*}$$

Where the last step was just collecting the coefficients.

##############################################$#$###############################################

Just like with differential equations, we recognize special forms that come up frequently. Recall that we are trying to solve:

Δy + (1/2) y = 1

The homogenous part is Δh + (1/2) h = 0. This has constant coefficients, so we can immediately posit the solution $h_n = r^n$. Plugging this in gives:

$$(r - 1) r^n + (1/2) r^n = 0$$

Which is easily solved to give r = (1/2). So, the homogenous solution is $h_n = A (1/2)^n$.

Now to find a particular solution of the original equation. Since the R.H.S. is also a constant, we can immediately posit a constant solution for y. (If the R.H.S. was a polynomial of degree n, we could posit a polynomial of degree n as a solution for y) This is easily seen to be y = 2.

So, the general solution is:

$$y_n = A (1/2)^n + 2$$

 

[Benny]

Thanks for the help guys but I still don't really understand well enough the main thing which characterises difference equations. I just read my book again and it says that first order recurrence relations for which n = 1 are exemplified by $$u_{n + 1} = au_n + k$$ with u_0 specified. The solution of the homogeneous relation (where k = 0) is immediate, $$u_n = Ca^n$$.

I don't understand why the solution would be so 'obvious.' Can someone please show me how the given expression for u_n can be verified to be a solution of the homogeneous relation? Perhaps it will make it easier for me to understand it. Any help would be good.

 

[Tide]

If $u_n = C a^n$ then $u_{n+1} = C a^{n+1}$ and substituting into $u_{n+1} = a u_n$ gives

$$C a^{n+1} = a \times C a^n$$

which is clearly true for any value of a. Therefore, $C a^n$ is the general solution.

To obtain the solution of the homogeneous equation from scratch simply step down with the index like this:

$$u_{n+1} = a u_n = a \times a u_{n-1} = a \times a \times a u_{n-2} ...$$

and so on until you get to the first index on the right side. You should see the pattern that develops.

 

[Benny]

Thanks again for your help Tide.