Difference Equations

In this post we will discuss Difference Equations.

One could say difference equations are the discrete analogue of differential equations.
Indeed the techniques used to solve them very much resembles the approach one takes for solving ordinary differential equations (ODEs).
An example of a difference equation is the Fibonacci sequence F_n = F_{n-1}+F_{n-2},\; F_0 = F_1 = 1 which we will learn how to solve later.

Difference equations are often not as extensively treated in undergraduate education as their continuous counterpart.
They are nevertheless important in all sorts of disciplines.
In probability theory difference equations (or “recurrence relations”) often arise when describing probabilistic transitions between a number of discrete states. In science and economy one is often interested in discretizing a differential equation into a difference equation so one can solve it numerically in a computer. There is a whole research area devoted just to approximating solutions to differential equations in this way so I am not going to delve much deeper into this.
Instead we will look at how to solve certain types of difference equations exactly and apply the theory to some nice puzzles, like Tower of Hanoi or finding out the probability of a mouse surviving in a filthy student corridor with a cat (a metaphor for finding the absorption probability of a discrete Markov Chain).

Let’s start off with some theory for the simplest kind of difference equations:

First Order Difference Equations:

The general form of a first order difference equation with constant coefficients is:

y_{n} + ay_{n-1} = b\;\;\;\;\;\;(*)
where a,b are a constants

To solve this equation we may first consider what happens in the case where b = 0, the so called homogeneous case.

Unwinding the equation iteratively we get y_{n} = -ay_{n-1} = a^2y_{n-2} = -a^3y_{n-3} = ... = (-a)^ny_0.
This has the general form C(-a)^n for some constant C.

To find the general solution when b \neq 0 this complementary solution of the homogeneous equation needs to be translated in some direction. To understand how this should be done we need to find a particular solution.

We could try the simplest possible solution, namely y_n = k for some constant k.
Plugging into (*) we get k+ak=b \Longrightarrow k = \frac{b}{a+1}, which is well defined as long as a \neq -1

If a = -1 we may instead try y_n = kn which after insertion into (*) yields
k(n+1)+akn=b \Longrightarrow k = \frac{b}{n(a+1)+1} = b.

The general solution to (*) thus becomes
y_n = \begin{cases} C(-a)^n + \frac{b}{a+1} & if\;\; a \neq -1 \\ C(-a)^n + bn & if \;\;a = -1 \end{cases}

We can indeed verify this solution is valid since in the former case (say) we have:
y_{n} + ay_{n-1} = C(-a)^{n} + \frac{b}{a+1} + a(C(-a)^{n-1} + \frac{b}{a+1}) =
C(-a)^{n} + \frac{b}{a+1} - (C(-a)^{n} - \frac{ab}{a+1}) = \frac{b}{a+1} + \frac{ab}{a+1} = \frac{b(a+1)}{a+1} = b.

Notice also the resemblance to ordinary differential equations where we also look for homogeneous and particular solutions in a similar way.

Moreover if we have an initial condition y_0 = C_0 then we can determine the general coefficient C.

 

Let’s move on to an application:

Problem 1 (Tower of Hanoi):

TowerOfHanoi

The Tower of Hanoi is a puzzle that consists of three vertical poles and n number of discs in different size.
Each disc has a hole in the middle so it can be moved between the poles.
Initially the discs are situated on the middle pole, ordered by size, with the largest disc at the bottom.
The discs are only allowed to be moved in such a way that a larger disc never sits on top of a smaller disc. Other than that discs are allowed to be moved freely between the poles.
The puzzle is solved when every disc either sits all on the left pole or all on the right pole.

What is the minimum number of moves required to solve the puzzle?

Solution:

Let y_n denote the minimum number of moves required to solve the puzzle.

Clearly y_0 = 0, y_1 = 1, y_2 = 3.

What about the general case?

In order to move the bottom disc to an empty pole we must first move the remaining n-1 discs to a different empty pole. By definition this requires y_{n-1} moves.

Once the n-1 discs have been moved aside and the bottom disc moved to its finial location, we need to move back the n-1 discs on top of the bottom disc to solve the puzzle. This requires another y_{n-1} moves.

In total we therefore need to use y_n = 2y_{n-1} + 1 moves.
This describes a first order difference equation.
According to our earlier discussion it has the general solution y_n = C2^n - 1.
Our initial condition y_0 = 0 yields 0 = C2^0 - 1 \Longrightarrow C = 1.

Hence the minimum number of moves required to solve the puzzle is y_n = 2^n -1.

 

According to the legend the world will end once monks, fulfilling an ancient prophecy, have finished solving the puzzle for n=64.
According to our analysis the minimum number of moves required is 2^{64}-1 \approx 1.84 \times 10^{19}.
Even if they carry out one move per second it will take them approximately 5.82 \times 10^{11} years to complete, so I think we are safe for a while longer.

In order to look at remaining applications we need to go over some theory of second order difference equations:
 

Second Order Difference Equations:

A Second Order Difference Equation with constant coefficients have general form:

y_{n} + ay_{n-1} + by_{n-2} = c\;\;\;(*)
for n \geq 2 where y_0,y_1 are given and a,b,c are constants

Here too the general solution depends on finding complementary and particular solutions.

Let’s first consider the homogeneous case where c = 0.
With understanding of first order difference equations we might believe a solution of the form y_n = Cx^n can work here too. Lets see how that works out if we assume x \neq 0:
y_{n} + ay_{n-1} + by_{n-2} = 0 \Longleftrightarrow Cx^n + aCx^{n-1} + bCx^{n-2} = 0
\Longleftrightarrow x^2 + ax + b = 0 \Longleftrightarrow x = -\frac{a}{2} \pm \sqrt{(\frac{a}{2})^2 - b}.

Excellent! So if we choose r to be a root of the auxiliary equation x^2 + ax + b = 0 we get that y_n = Cr^n is a solution to y_{n} + ay_{n-1} + by_{n-2} = 0 for any constant C.

Ignoring the case where the auxiliary equation has no real roots we have two cases:

i) x^2 + ax + b = 0 has two distinct real roots x_1,x_2.
You may easily verify that
y_n = C_1x_1^n + C_2x_2^n
is a solution to the homogeneous equation for arbitrary constants C_1,C_2.

ii) x^2 + ax + b = 0 has a repeated real root x_1.
You may easily verify that
y_n = (C_1+nC_2)x_1^n
is a solution to the homogeneous equation for arbitrary constants C_1,C_2.

A particular solution may be found in similar fashion to how they were found for first order difference equations, by trying something simple like y_n = k or y_n = kn.

Complementary and particular solutions are finally added together for a general solution to (*).

The constants C_1,C_2 can be determined by plugging in values for y_0,y_1 and solving the resulting equation system in two unknowns C_1,C_2.

Again this bears striking resemblance to solutions of second order ordinary differential equations.

 
A nice direct application of this is that we may compute a closed form expression for the n^{th} Fibonacci number.

Problem 2 (Fibonacci Number Formula):

The Fibonacci sequence is given by F_n = F_{n-1}+F_{n-2},\; F_0 = F_1 = 1.

Solve this difference equation to get a closed formula for the n^{th} Fibonacci number.

Solution:

The Fibonacci recurrence is a homogeneous second order difference equation.
The auxiliary equation is given by:
x^2-x-1 = 0.

The roots of the quadratic equation are given by
x_1 = \frac{1+\sqrt{5}}{2} = \phi (Golden Ratio) and
x_2 = \frac{1-\sqrt{5}}{2} = 1 - x_1 = 1 - \phi.

This yields the general solution F_n = C_1\phi^n + C_2(1-\phi)^n.

Since F_0 = 1, F_1 = 1 we can determine C_1,C_2 via the equation system

\begin{cases} 1 = C_1\phi^0+C_2(1-\phi)^0 & \\ 1 = C_1\phi^1 + C_2(1-\phi)^1 & \end{cases}

Solving for C_1,C_2 we get C_1 = \frac{\phi}{2\phi-1} and C_2 = \frac{\phi-1}{2\phi -1}.

Hence F_n = \frac{\phi^{n+1} - (1-\phi)^{n+1}}{2\phi-1} where \phi = \frac{1+\sqrt{5}}{2}.

It is indeed not obvious that this expression needs to be an integer.

 

Let’s now turn our attention to a probabilistic application:

Problem 3 (Cat And Mouse):

A mouse finds its way to a filthy student corridor with N rooms as depicted below.

CatMouse

The mouse is small enough to creep through the tiny gap under each door of the corridor.
It initially starts in room k and moves every minute to an adjacent room with equal probability (out of fear for an equally afraid student).

Unfortunately for the mouse there is a cat owner in room 0.
If the mouse enters room 0 it will get instantly killed by the eager cat.
If on the other hand, the mouse reaches past the last room (room N-1) it will escape out the corridor and survive.

(i) What is the probability that the mouse will survive?

(ii) How long is it expected to take before we get a resolution to the mouse’s fate?

Solution:

(i)
Let p_k denote the probability that the mouse will survive given that it is currently in room k.

Since the mouse is equally likely to go left or right we get the following homogeneous second order difference equation:

p_k = \frac{1}{2}p_{k-1} + \frac{1}{2}p_{k+1}.

Since the mouse is guaranteed to die if it reaches room 0 we get p_0 = 0.
Similarly since it will escape if it reaches the end on the opposite side of the corridor we get p_N = 1.

We can now solve this difference equation using the methods we have been discussing.
The auxiliary equation is given by:
x = \frac{1}{2} + \frac{1}{2}x^2 \Longleftrightarrow x^2 - 2x + 1 = 0 \Longleftrightarrow (x-1)^2 = 0 \Longleftrightarrow x = 1.

This time we have a repeated root so the general solution takes the form
p_k = (C_1+kC_2)1^k = C_1+kC_2.

The initial condition p_0 = 0 implies C_1 = 0.
The condition p_N = 1 implies C_2 = \frac{1}{N}.

Hence p_k = \frac{k}{N}.

(ii)
To compute the expected duration of the mouse’s activity in the corridor we may begin by introducing some notation.
Let D_k denote the expected duration until death or escape given that the mouse is currently in room k.

Since the mouse stays in each room for one minute before switching to an adjacent room (with equal probability) we obtain the non-homogeneous second order difference equation:

D_k = \frac{1}{2}D_{k-1} + \frac{1}{2}D_{k+1} + 1.

Moreover D_0 = 0 = D_N since activity ends at either end state.

We have already seen that the homogeneous equation has general solution D_k = C_1+kC_2.

We now need to find a particular solution.
To spare you the trial and error computation, it turns out that both D_k = C and D_k = Ck lead to degenerate solutions, meaning we cannot determine the constant C.

The obvious next candidate to try is D_k = Ck^2 where C is a constant to be determined.
Inserting yields Ck^2 = \frac{1}{2}C(k-1)^2 + \frac{1}{2}C(k+1)^2 + 1 \Longrightarrow C = -1

Therefore the general solution is given by
D_k = C_1 + kC_2 - k^2

The initial condition D_0 = 0 yields C_1 = 0.
The second condition D_N = 0 gives 0 = C_1 + NC_2 - N^2 \Longrightarrow 0 = N(C_2-N) \Longrightarrow C_2 = N

Hence we expect the mouse to run around in the corridor for k(N-k) minutes before either getting killed by the cat or running out of the corridor, provided that the mouse starts in room k.

 

Those of you who have studied elementary probability might have recognized already that the problem above was simply a restatement of the Gamblers Ruin Paradox. Instead of a mouse and a cat we have two opponents each holding k and N-k dollars respectively. The opponents play a fair game (say they flip a fair coin) and if one opponent loses, he has to give away one dollar to the other opponent. They play the game until one of them holds all N dollars. The question is what the probability is of the first opponent losing all his money (i.e the mouse getting eaten by the cat).

The seeming “paradox” here being despite playing a fair game the first player will still lose all his money if he plays a very rich opponent, say a casino. Indeed if we assume for arguments sake that the casino has infinite amount of money, then the probability that the first player loses all his money is lim_{N \rightarrow \infty} (1 -\frac{k}{N}) = 1 i.e the game will (almost surely) not continue forever, despite even chance of winning or losing, no matter what finite amount of chips the first player starts with.

Below are some neat exercises for you to try.
They can all be solved by identifying a difference equation and solving it.

Exercise 1 (Stair Climbing – Easy):

In how many different ways can you climb a stair of n steps by taking either one or two steps at a time?

For example you can climb a stair of 4 steps in any of the following 5 ways:
(2,2),(2,1,1),(1,2,1),(1,1,2),(1,1,1,1)

(Hint: Do you recognize the difference equation from somewhere?)

 

Exercise 2 (Dividing A Pizza – Intermediate):

What is the maximum number of pieces you can get if you divide a pizza using n straight cuts?

Note: pieces need not be of the same size, nor contain any crust

PizzaSlicing

(Hint: What happens if you make a cut crossing all previous cuts, yet not crossing any of the existing intersection points?)

 

Advertisements
This entry was posted in Combinatorics, Discrete Math (General), Probability, Uncategorized and tagged , , , , , , , , , , . Bookmark the permalink.

3 Responses to Difference Equations

  1. Pingback: 7th CPC-THE REAL TRUTH BEHIND THE DEMAND

  2. Pingback: Puzzles With Handicap | Mathematical Mélange

  3. Pingback: Dynamic Programming | Mathematical Mélange

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s