# Solving Second-Order Linear Homogeneous Recurrence Relations with Constant Coefficients

In this post I will explain how to solve a type of recurrence relation known as Second-Order Linear Homogeneous Recurrence Relations. These types of equations have the form:

$a_k$ = A $\cdot$ $a_{k-1}$ + B $\cdot$ $a_{k-2}$       (where B$\neq$ 0 and k$\geq 2$)

Our main objective when approaching this problem is to obtain an explicit formula. The explicit formula is much more valuable than a recurrence relation because if we want to figure out the 100th value we just have to plug 100 into our formula, but if we had a recurrence relation we would need to obtain all 99 values before getting the 100th value.

In order to solve these types of equations we first assume that our explicit formula has the form $a_n = t^n$ where t is some real number and does not equal 0. This means that there is some value of t such that the following sequence:

$1, t, t^2, t^3, t^4, t^5,$ $\ldots, t^n$

satisfies the recurrence relation. Stated another way, this means that the relation can be written as follows:

$t^k$ = A $\cdot$ $t^{k-1}$ + B $\cdot$ $t^{k-2}$       (where B$\neq$ 0 and k$\geq 2$)

What happens when we let k = 2 (something beautiful! :p ). When we let k = 2 our equation turns into the extremely familiar quadratic equation which can be solved by factoring or the quadratic equation. This equation is also known as our characteristic equation of the relation and it has the form:

$t^2$ = At + B

or

$t^2$ – At – B = 0

Solving the equation from this point involves the distinct-root theorem which states that if our characteristic equation has the quadratic form and it has two distinct roots {r and s}, then the explicit form can be written in the following form:

$a_n$ = C$r^n$ + D$s^n$

where C and D are to be determined by the values of $a_0$ and $a_1$. In order to show you how this works in practice consider the following example.

Given the recurrence relation $a_k = 3a_{k-1} + 10a_{k-2}$ $k \geq 2, a_0 = 1$  $a_1 = 4$  what is the explicit formula?

First we suppose our explicit formula can be written in the form:

$t^k$ = $3t^{k-1}$ + $10t^{k-2}$

Let k = 2 in order to generate our quadratic equation:

$t^2$ = 3t + 10

or

$t^2$ – 3t – 10 = 0

What follows is just some basic algebra in order to figure out our possible values of t.

(t-5)(t+2) = 0

t = {-2, 5}

Now its time to use the distinct root theorem in order to find our explicit formula!! This is a really simple process and just requires a little bit of algebra (systems of equations) and our base values.

$a_n$ = C $5^n$ + D $(-2)^n$

Next let n = 0 (note: $a_0$ = 1)

1 = C $5^0$ + D $(-2)^0$

1 = C + D

1 – C = D

Now let n = 4 (note: $a_1$ = 4)

4 = C $5^1$ + D $(-2)^1$

4 = 5C – 2D

4 = 5C – 2(1-C)

(note: we made the substitution from our system of equations)

4 = 5C – 2 + 2C

6 = 7C

C = $\frac {6} {7}$

Finally we use our newly obtained value of C to solve for D

D = 1 – C

D = 1 – $\frac {6} {7}$

D = $\frac {1} {7}$

Thus our final explicit formula is:

$a_n$ = $\frac {6} {7}$ $5^n$ + $\frac {1} {7}$ $(-2)^n$

# Mathematical Induction III

Up until this point we have been discussing ordinary mathematical induction and in this post I will explain what strong mathematical induction is and how it differs from ordinary induction. Before I talk about the differences lets talk about the similarities. Both types of induction involve a basis step and an inductive step to be proved, but strong induction can involve multiple basis steps and each of these must be proven before moving onto the inductive step.

The other main difference between strong and ordinary induction is that since we are possibly including multiple basis steps we must define some type of statement to represent the statement of interests validity over a range of values. All of this talking in the abstract is probably kind of confusing so we will go over an example.

Given the sequence:

$s_0$= 0    $s_1$= 4    $s_n$ = 6$a_{n-1}$ – 5$a_{n-2}$

Prove that all the terms of the previous recurrence sequence is satisfied by the following equation:

$s_n$ = $5^n$ – 1

The first step is to prove the basis step, but this time we must prove two basis steps for the two given base values.

$s_0$ = $5^{(0)}$ – 1 = 0    (true)

$s_1$ = $5^{(1)}$ – 1 = 4    (true)

Next is our inductive step, but here is where it gets a little bit different. Strong mathematical induction supposes the truth of our inductive hypothesis for all values beginning at our lowest base case through k. This is different from ordinary mathematical induction because in that type of induction they say nothing about all values, but only values within a range for which the relation is defined. Below I will show you the difference between how the inductive hypothesis looks in either case.

Inductive Hypothesis (Ordinary Mathematical Induction)

Suppose for some arbitrarily chosen but particular k $\geq$ 2 the following equation is true

$s_k$ = $5^k$ – 1

Inductive Hypothesis (Strong Mathematical Induction)

Let k be some arbitrarily chosen but particular value such that k $\geq$ 1 and the following equation is true

$s_i$ = $5^i$ – 1 for all integers i with 0 $\leq$ i $\leq$ k

As you can see, the only difference between the two is the range over which our inductive hypothesis is valid. The strong version includes all possible values in its inductive hypothesis. The rest of the proof flows the same ways as the other type of inductive proofs.

We must next show that:

$s_{k+1}$ = $5^{k+1}$ – 1

We can use the original recurrence relation to arrive at this conclusion through some basic algebra manipulations:

$s_{k+1}$ = 6$s_{k}$ – 5$s_{k-1}$

$s_{k+1}$ = 6($5^k$ – 1) – 5($5^{k-1}$ – 1)

$s_{k+1}$ = 6 $\cdot$ $5^k$ – 6 – $5^{k}$ + 5

$s_{k+1}$ = (6 -1)$\cdot$ $5^k$ – 1

$s_{k+1}$ = 5$\cdot$ $5^k$ – 1

$s_{k+1}$ =$5^{k+1}$ – 1

$\therefore$ $s_n$ = 6$a_{n-1}$ – 5$a_{n-2}$ $\rightarrow$ $s_n$ = $5^n$ – 1

# Mathematical Induction II

This next post will focus on using mathematical induction to prove an inequality. Our statement to be proven is as follows:

$2n + 1 \textless 2^n$ for all integers n $\geq 3$

Solution:

The first step as always in theses types of proofs is to prove the basis step. This is accomplished by just inputting  values.

Show that P(3) is true:

$2n + 1 \textless 2^n$

$2(3) + 1 \textless 2^3$

$7 \textless 8$

As was shown above, the basis step checks out in our proof and we are now ready to move onto our inductive step.

Show that the inductive hypothesis is true:

Suppose that k is some arbitrarily chosen but particular value such that:

$2k + 1 \textless 2^k$ for all integers k $\geq 3$

We must show that

$2(k+1) + 1 \textless 2^{k+1}$ for all integers n $\geq 3$

We are allowed to use part of our inductive hypothesis because that’s what we are assuming to be true. In order to take advantage of our inductive hypothesis we must re-arrange out current statement P(k+1). The left side of this inequality can be written as follows:

$2(k+1) + 1 = 2k + 2 + 1 = (2k + 1) + 2$

With the left side of the inequality in this form we can make the following claim:

$(2k + 1) + 2 \textless 2^k + 2$

This result was achieved by simply substituting the 2k+1 term from our inductive hypothesis. Now if we can prove that $2^k + 2$ is strictly less than $2^{k+1}$ we will have finished the proof.

This next step takes a little finesse because we must remember how inequalities work. We must remember that by adding/subtracting/multiplying/dividing the same POSITIVE term for both sides we are maintaining the inequalities validity (try a few cases if  your not satisfied). This means that we can go through the following set of manipulations:

$2^k + 2 \textless 2^{k+1}$

$2 \textless 2^{k+1} - 2^k$

$2 \textless 2^k(2-1)$

$2 \textless 2^k(1)$

$2 \textless 2^k$

$\frac{2}{2} \textless \frac{2^k}{2}$

$1 \textless 2^{k-1}$

Our final inequality is clearly valid for all terms $k \geq 2$ thus by default it will be valid for all $k \geq 3$

$\therefore 2n + 1 \textless 2^n$ for all integers $n \geq 3$

# Combinatorics: R-Combinations

We are now given a new task, and a new scenario to model (yay! right). The next concept I will cover is r-combinations, meaning combinations with repeats. I will explain what this means with an example:

You are going to the grocery store in order to pick up three 2-liters of soda. Once you arrive at the store you have five different types of soda to choose from (pepsi, coca-cola, sprite, a&w root beer, and 7-up for example). Now you want to figure out the number of different combinations of soda you can bring home only this time your allowed to group the same type of item together. As an example {pepsi, pepsi, pepsi} would be a valid choice.

The best way to derive a formula for this type of problem is to envision your choices (5 types of sodas) as categories and the number of sodas you need (3) as being placed in one of those categories if selected. So if you pick 2 pepsi’s and 1 7-up  (and if pepsi and 7-up are categories #1 and #4 respectively) it could be represented by the following string

xx| | |x|

In order to get the total number of possibilities you must find the total number of unique strings of the form above with  4 bars and 3 x’s. This is a simple permutation with repeats problem. Note that there is one less vertical bar than there are categories because we omit the end bars. I know there are two end bars but you only subtract one because if you subtracted two from our equation we would not be simulating the correct string permutations. Our final answer becomes:

${7}\choose {3}$ = 35

# Combinatorics: Permutations with Repetition

Welcome to permutations level II! This post involves the concept of permutation, but with an added layer of complexity. Consider the word MISSISSIPPI; how would one go about getting the number of different ways this word can be arranged (permutation)? If you attempted to calculate this problem using the original formula you would get 11! which would be incorrect. You would be over counting for all of the repeated letters.

In order to complete this permutation you must think of each repeated letter as occupying a certain position in the sequence. For example, if we were to place the S’s first there would be 11 places that the S’s can go (e.g. {1,3,6,11}. We can use our combination formula to calculate the number of different subsets to place the S’s, equaling ${11}\choose {4}$. The rest of the calculation proceeds in a similar fashion and we arrive at the following:

${11}\choose {4}$  $\cdot$ ${7}\choose {4}$ $\cdot$  ${3}\choose {2}$ $\cdot$ ${1}\choose {1}$ = 34,650

# Combinatorics: Combinations

Combinations are similar to permutations in that they were created to model a certain situation, however, that situation is a little different. In order to explain the meaning of a combination consider the following example:

You are a teacher creating a gift basket will different types of candies and toys, and you have a total of five different items to choose from. You want to create baskets with exactly 3 items and each of those items has to be different than the other. Your goal is to figure out how many different types of baskets you can create.

Now the basket can hold 3 items but the order of the items in the basket doesn’t matter. In order to get the answer you could try and list all the terms and eventually come up with 10 different possibilities.

{a,b,c} {a,b,d} {a,b,e} {a,c,d} {a,c,e} {a,d,e} {b,c,d} {b,c,e} {b,d,e} {c,d,e}

Generating these terms is a lot harder than cranking out permutations, and it would take an eternity to generate the number of different choices if we had something like 10 different items to choose from. So it’s our task as mathematicians to simplify this scenario into mathematical formula that can be used to model this situation.

The formula for combinations can be derived from the formula for r-permutations, but it first requires viewing r-permutations in a different way. Instead of just viewing it as a way to position elements in a certain number of positions, you must think of r-permutations as a two step process.

Step 1: Generate a sets of r-elements

Step 2: Order those r-elements

So the r-permutation formula is implicitly calculating both step 1 & step 2 at the same time. Since we want just the result of step 1 we must divide out step 2. Which is why we come to the following formula:

${n}\choose{r}$ = $\frac{P(n,r)}{r!}$

# Combinatorics: Permutation Problems

Consider the word BYTES, how many different 3-permutations can be generated if the first letter must be B.

Solution:

I found this problem to be interesting because it takes a little bit of thinking. You can’t just plug in numbers to any formula to get an answer which makes it the perfect type of quiz or test question.

The first thing to realize is that we are asking for some type of r-permutation, but we have a restriction that the first letter must be ‘B’. Since the first letter must be ‘B’ there is only one choice for that position in our 3-permutation, which leaves two spots lefts. Now we must decide all possible combinations of two letters, but since ‘B’ must be placed at position one, we exclude it from our possible choices. The answer becomes

P(4,2) = $\frac {4!}{(4-2)!} = 12$

# Combinatorics: Permutation

This is the first of my series of post on combinatorics, a fascinating field that is used to model many real life scenarios. In my opinion, combinatorics attempts to model real life situations more so than many other topics in mathematics.

I will start with the most basic of concepts and move onto more advanced topics as we progress.

A permutation represents the number of different ordering of elements in a row. For example, the set of elements {a,b,c} has the following six permutations:

abc, acb, bac, bca, cab, cba

As you can see, there are six possible ways to order the set {a, b, c} but is there a mathematical formula to model this process? One can imagine that having to count each possible permutation could become a laborious task. Well in order to model this behavior, consider the following example:

Because we have three positions, each position can be thought of as having a certain number of choices. Position 1 can be occupied by three different choices (the full set), while position 2 can be occupied by only two different choices (full set – element at position one), and position 3 only has one choice.

$3 * 2 * 1 = 6$

Because of the multiplication rule, we can get the total number of different orderings of elements by just multiplying terms. So the formula for permutation is just n-factorial which makes sense because this expression models the exact process of placing terms until there is only one more term to place.

$n! = n \cdot (n-1) \cdot (n-2) \cdot (n-3) \cdot \ldots \cdot 3 \cdot 2 \cdot 1$

The above process of finding the number of permutations works if we want to permute an entire set, but what if we want to find the number of 2-permutations in a set of three. This would represent the number of different ways the entire set can be grouped together in sets of two. If we were to find the number of 2-permutations of our original set {a, b, c} it would look as follows:

ab, ba, ac, ca, bc, cb

Once again we come to the number six which is kind of interesting if you think about it. The number of different ways to arrange three terms in a set of three is identical to the number of ways to order two terms. This type of permutation is called an r-permutation and it represents the number of ways a set of r elements can be arranged from a greater set of n elements where $1 \leq r \leq n$ Can you take a minute to think about the last restriction we placed on r? Well obviously r cannot be a fraction (no fractions of elements), and it has to be less than n, you can’t have a set of n+1 elements if there are only at most n elements in a set.

The formula for r-permutations is as follows:

$P(n,r) = r-permutations = \frac {n!}{(n-r)!}$

This formula can be easily understood if you envision a row if terms getting ready to be multiplied together in order to get the full permutation and then dividing out the number of terms that will leave only the first r terms. In the next post I will give more examples and talk less about theory.

# Mathematical Induction I

Mathematical Induction is a tricky topic and can appear impossible to understand at first. To begin, it’s important to realize that induction comes directly from Peano’s 5th Axiom (or 9th depending on your website of choice).

Remember that an axiom is a rule or statement that is universally accepted without proof. So although the principle of induction is without proof, it can be understood logically from a few examples. The example that I understood best involved a ladder.

Consider a ladder, the first step to climbing this hypothetical ladder is to first climb the lowest rung (base case), and then if you can climb the next rung (n + 1 inductive hypothesis) then you could climb the the entire ladder. This intuitively makes sense because if you can climb the base rung, and the next rung, every other case amounts to just climbing another rung which has already been shown to be possible by the inductive step.

Most induction problems are usually defined for natural numbers (positive-integers). This is good because it allows us to take advantage of the well-ordering principle. This principle basically gives us a “base” to work with because it states that every non-empty set of positive integers has a smallest value. So the goal of induction is to prove a base case, and then prove a more general case (n+1), in effect producing a proof for all natural numbers.

The best way to learn anything is through practice and mathematical induction is no different. Now that I’ve discussed the basics of induction I’ll begin with a classic induction proof and my next post’s will focus on different types of proofs that can be done inductively.

Use mathematical induction to prove that

1 + 2 + 3 + 4 + 5 + … + n = $\frac{n(n+1)}{2}$ for all integers n $\geq$ 1

This is usually one of the first proofs that teachers introduce because its easy to understand and  it just rely’s on algebra. So as always we start with a basis step

Show that P(1) is true

1 = $\frac{(1)((1) + 1)}{2}$ (by basic algebra)

Next we must consider an inductive hypothesis and ultimately prove the formula

Suppose that k is any arbitrarily chosen but particular integer with k $\geq$ 1. Suppose that:

1 + 2 + 3 + 4 +5 + … + k = $\frac{k(k+1)}{2}$

This step is called a hypothesis because its what we are trying to prove, but it noteworthy to remember that this hypothesis is taken as truth and can be used throughout the proof as such.

So the real heart of the problem comes down to proving the following statement:

1 + 2 + 3 + 4 + 5 + … + k + (k+1) =  $\frac{(k+1)((k+1)+1)}{2}$

This can be accomplished with basic algebra and our inductive hypothesis. Take note of the following substitution.

(1 + 2 + 3 + 4 + 5 + … + k) + (k+1) =  $\frac{(k+1)((k+1)+1)}{2}$

$\frac{k(k+1)}{2}$ + (k+1) =  $\frac{(k+1)((k+1)+1)}{2}$

We are allowed to make this substitution because we are supposing it to be true, that’s why its called an inductive hypothesis. The proof is complete once we have shown that the left side of the equation implies the right side of the equation (which is accomplished with basic algebra).

Left-Side

$\frac{k(k+1)}{2}$ +$\frac{2(k+1)}{2}$ =

$\frac {k(k+1) + 2(k+1)}{2}$ =

$\frac {k^2 + k + 2k + 2}{2}$ =

$\frac{k^2 + 3k + 2}{2}$ =

Right-Side

$\frac{(k+1)((k+1)+1)}{2}$

= $\frac{(k+1)(k+2)}{2}$

= $\frac{k^2 + 2k + k + 2}{2}$

= $\frac{k^2 + 3k + 2}{2}$

Left-Side = Right Side ?

$\frac{k^2 + 3k + 2}{2}$$\frac{k^2 + 3k + 2}{2}$ (true)

$\therefore$ 1 + 2 + 3 + 4 + 5 + … + n = $\frac{n(n+1)}{2}$ for all integers n $\geq$ 1

In the next post I’ll focus on using induction with inequalities as well as discuss more examples.

# Multi-Level Cache Performance Problem

This is a homework problem that I was given:

Suppose you have the following statistics for a Processor with several different choices for memory hierarchy.

Base CPI = 1.5 
Processor Speed = 2 GHZ
Main Memory Access Time = 100ns
L1 miss rate per instruction = 7%
L2 direct mapped access = 12 cycles
Global miss rate with L2 direct mapped = 3.5%
L2 8-way set associative access = 28 cycles
Global miss rate with L2 8-way set associative access = 1.5%

Note: A global miss rate is the percentage of references that miss in all levels of cache (and therefore must access Main memory)

1. Calculate the Total CPI if L2 cache is available and is direct mapped.
2. Calculate the Total CPI if L2 is available and is 8-way set associative.

Solution

First,

Total CPI = Base CPI + Memory-Stall Cycles per Instruction

Memory-Stall Cycles per Instruction = Miss Penalty (in cycles) x Miss Rate

The first order of business is to figure out the miss penalty if there was not a second cache. This is easily determined by the following calculation:

Main Memory Access Time/ (1/Processor Speed) = (100) / (.5) = 200 cycles

Note: Main Memory Access Time is in ns, and the inverse of Processor Speed will be in ns/cycles, so by dividing the two we get the number of cycles. We are doing this calculation because it takes a certain amount of time to go all the way to main memory (100ns) and the processor speed determines how fast we can go (2GHz) and by changing clock speed to clock rate by inversion we can calculate the number of cycles required to go to main memory (miss penalty).

Because the problem involves two caches, when there is a miss in L1 there will be an attempt to retrieve the information from L2 and then if the information is still not found it will access main memory, so the flow looks something like this.

Access L1 —–> Access L2 —–> Access Main Memory

(it’s implied that if there is a “hit” we will not need to continue the flow)

The problem tells us that L2 direct mapped access takes = 12 cycles

So the calculation will look as follow:

Total CPI = 1.5 + (0.07 x 12) + (0.035 x 200) = 9.34 CPI

Because you miss 7% of the time you will need to access L2 and that takes 12 cycles so you multiply the two. Then if it’s still not found we must access main memory which takes 200 cycles and the global miss rate is 3.5%

Total CPI = 1.5 + (0.07 x 28) + (0.015 x 200) = 6.46

The second calculation is done in a similar fashion