## 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):

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.

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

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