Sample Solutions in Lectures

Symbolic Logic

Among the following four sentences

(a)
Today is a rainy day.
(b)
David was wet this morning.
(c)
Did David get soaked in the rain?
(d)
Please read the notes.

only (a) and (b) are propositions. If we denote by p and q respectively the propositions (a) and (b), then

p q represents ''Today is a rainy day and David was wet this morning''.

p q represents ''Either today is a rainy day, or David was wet this morning, or both''.

p represents ''Today is not a rainy day''.

In general, when p and q are propositions, p q (i.e. ''p and q'') for example is true (T) if and only if both p and q are true. The precise effect or truth values for the above connectives can be summerized in the following truth tables

In fact we can take these tables as the precise definitions for the corresponding connectives. Likewise one way of describing completely a compound proposition is to give explicitly its truth table. Conversely, we note that a truth table can also be used to define a compound proposition.

Show ( p) ( q) and (p q) are equivalent.
Solution We first construct below the truth table for the two compound propositions

Since the last two columns are the same, we conclude ( p) ( q) and (p q) are equivalent.
Show (p q) and ( p) ( q) are not logically equivalent.
Solution This is manifested in the following truth table

because the corresponding truth values differ (at 2 places).
Show (p q) ( p) is a tautology and (p q) ( p) is a contradiction.
Solution From the following truth table

We see (p q) ( p) is always true and is thus a tautology and (p q) ( p) is always false and is thus a contradiction.

Let p denote ''I buy shares'' and q denote ''I'll be rich''. Then p q means ''If I buy shares then I'll be rich''. Let us check row by row the ''reasonableness'' of the truth table for p q given shortly before.

Row 1:	''I buy shares'' (p true) and ''I'll be rich'' (q true) is certainly consistent with (p q) being true.
Row 2:	''I buy shares'' and ''I won't be rich'' means ''If I buy shares then I'll be rich'' (i.e. p q) is false.
Row 3 and 4:	''I don't buy shares'' won't contradict our statement p q, regardless of whether I'll be rich, as obviously there are other ways to get rich.

Switching Circuits and Boolean Algebra

For switching systems with state space S={0,1}, the ''+'' and '''' operation are binary and the '''' operation is unary.
Solution This is because for any switching systems x and y, we have that x+y, x y and x' are all still switching systems with the same state space S.
Note Binary operator or operation has nothing to do with binary numbers.

Switching system (S, +, , ,0,1)with S = {0,1} is a Boolean algebra.
Solution We need to show B1 -- B5, by letting ''+'', '''' and '''' specifically denote switches in parallel, in series and in complementation respectively. The identities in B1 are valid because

The proof of B2 -- B5 is elementary. Hence we'll simply show only the first half of B3, i.e. a + (b c) = (a + b) (a+c). We'll show the identity by the use of the evaluation table below
Let be the set of real number, +, be the normal addition and multiplication, 0, 1 be the normal numbers. If we define by x'= 1-x for any x , then is (, +, , ,0,1) a Boolean algebra?
Solution No. Because neither the 1st half of B3 nor the 2nd half of B5 is satisfied. For example,
1 + (2 3) (1 + 2) (1 + 3).
Suppose S={1,2,3,5,6,10,15,30}. Let a+b denote the least common multiple of a and b, a b denote the greatest common divisor of a and b, and a'=30/a. Prove (S,+,, , 1, 30) is a Boolean algebra.
Solution Since this question is marked by a pair of solid arrows on the margin, it is entirely optional and is not examinable. I'll thus save it for one of those bored evenings or sleepless nights.

Convert (p q) r into the corresponding Boolean expression.
Solution Since p q is equivalent to ( p) q, we see that (p q) r is equivalent to ( (p q)) r which is thus converted to (p + q)' + r.
(De Morgan's Laws) Let (S, +, , ,0,1) be a Boolean algebra, then for any x, y S
(x+y)' = x' y', (x y)' = x' + y'.
Solution Proof obvious from the theorem in the previous lecture.
Let B = { 0,1 } and (B,+,,,0,1) be a Boolean algebra. Then is also a Boolean algebra if

Boolean Functions

Let f: {0,1}³ {0,1} be given by f(x,y,z) = xyz + min(x, (y+z)'). Write f as a Boolean expression, i.e. as a sum of product terms.
Solution From the following truth table

We see that only two rows will actually contribute to the final Boolean expression
f(x,y,z) = xy'z' + xyz
where the binary operator '''' is omitted for simplicity.

Show Boolean expressions x and xy + xy' are equivalent.

(a)
By truth table

(b)
By properties of Boolean algebra

(c)
By canonical form

Find the minimal representation for f = xy + xy + xx' + xy'.
Solution First we observe

Since f is not identical to 0 or 1, and its equivalent expression x has only 1 product term and 1 literal in total, this equivalent Boolean expression must be a minimal representation of f.
Show f = xyz' + xy'z + xy'z' + x'yz + x'yz' is equivalent to any of the 4 Boolean expressions below

(a)
xy' + x'y + xyz'
(b)
xy' + x'y + xz'
(c)
xy' + x'y + yz'
(d)
xy' + x'yz + yz'
and (a) and (d) are not minimal.
Solution Since f is already in canonical form, once we convert (a)--(d) into canonical forms we should see that the newly obtained canonical forms are in exactly the same form as f itself. For (a), for instance, we have

which is same as f. We can also derive (a)--(d) from f directly. For (c), for instance, we have

It is easy to see that expressions (a)--(d) all have 3 product terms. However (a) and (d) both have 7 literals while (b) and (c) both have only 6 literals. Hence neither (a) nor (d) is a minimal representation. We finally note that (b) and (c) in example 4 are minimal representations.
The Boolean expression f in example 4 may be drawn as a switching circuit below according to (b)

Draw a gate implementation for the Boolean expression xy'z'+xyz.
Solution
Show that any Boolean expression can be represented by NAND-gates alone.
Solution Since every Boolean expression can be represented by some AND-gates, OR-gates and NOT-gates, if we can construct these 3 types of gates with NAND-gates alone, then we have shown that any Boolean expression can be presented by just the NAND-gates. Since we can construct NOT-gates via

AND-gates via

and OR-gates via

because (p'q')'=p+q, we conclude that NAND-gates alone are enough to represent any Boolean expressions.

Karnaugh Maps

For Boolean expressions with variables x,y and z,

are both valid grids, and there are other possible valid grids as well.
For Boolean expression with 4 variables w,x,y and z, a typical valid grid would be

where , , and are the 4 neighbours of the shaded box.
For Boolean expression with 5 variables v,w,x,y and z, the following grid

is a typical grid and shaded box has 5 neighbours , , ..., .

The circled area in the Karnaugh map

is a 2 2 block representing

In other words, the block of 4 is simplified to a single product term y (with 1=N-M=3-2 literals)
The circled area in the Karnaugh map

is a 2 4 block representing z.
Notice that in a typical term w'x'y'z in the block, the variable names w, x and ymay change inside the circled block, and are thus not present in the final product term which becomes z.

Use Karnaugh map to simplify F = xyz + x'y + x'y'z'.
Solution

(a)
F = xyz + x'yz + x'y z' + x'y'z' is the canonical form.
(b)

(c)
No isolated 1's .
(d)
No blocks of 4. But there are pairing choices. We select least number of pairs.

(e)
No blocks of 4 means no blocks of 2^m for m 2.
Thus the minimal representation can be read off as yz + x'z'.
Suppose a Boolean expression can be represented by the following Karnaugh map

the the simplification procedure is as follows.

(a)
No isolated 1's.
(b)
Only 2 possible pairs exist, that can't be included in a block of 4 (1's). Since a 2nd pair will not cover any uncircled 1's that are not be covered by blocks of 4, we need to pick just 1 pair.

(c)
No blocks of 8. But there are 3 blocks of 4, each covering new 1's. The Karnaugh map now looks like

(d)
Since no uncircled 1's are left over the procedure is completed. The minimal representation is thus read off as
wy + yz + w'y' + x'y'z'
If one reverses the procedure and goes from big blocks to smaller ones, the results may not be minimal. For instance, with bigger block first, we would have to circle in the Karnaugh map below in the following order

then

which gives 5 product terms (corresponding to 5 circles). However, if we drop the block of 4 circle, we still have all the 1's circled. But the new and equivalent expression will only have 4 product terms.
With our normal procedure, nevertheless, we'll arrive at the correct answer represented by

Propositional Logic

p q r p is same as p ((q ( r)) p). However p q r p would be same as p (q (( r) p)) had we adopted higher precedence for than for .

Show (p q, p r, q r, r) is a valid argument.
Solution From the table

we see all critical rows (in this case, those with the shaded positions all containing a T) correspond to (the circled) T(true) for r. Hence the argument is valid.
Show that the argument (p q, p q ) is invalid.
Solution

We see that on the 3rd row, a critical row, the premise p q is true while the conclusion p q is false. Hence the argument (p q, p q ) is invalid.

Let p be the statement ''I'm sick'' and qbe the statement ''I go and see a doctor''. The p qmeans ''If I'm sick, then I go and see a doctor''. The converse of this statement is ''If I go and see a doctor, them I'm sick'', while the inverse reads ''If I'm not sick, then I won't go and see a doctor''. However, the contrapositive takes the form ''If I don't go and see a doctor, then I'm not sick''.

Show that the following argument form

p q, q r, p s t, r, q u s, t

(*)

is valid by breaking it into a list of known elementary valid argument forms or rules.

Solution We'll treat all the rules of inference introduced earlier in this subsection as the known elementary argument forms. The logical inference for the argument form in the question is as follows.

(1) q r premise

r premise

q by modus tollens

(2) p q premise

q by (1)

p by disjunctive syllogism

(3) q u s premise

q by (1)

u s by modus ponens

(4) u s by (3)

s by conjunctive simplification

(5) p by (2)

s by (4)

p s by conjunctive addition

(6) p s t premise

p s by (5)

t by modus ponens

Can you explain, in additional details, how those 6 proof steps in the above example come into existence?

Solution In the following we shall give the ''reverse route'' for the proof of the above argument form. Basically we shall start with the conclusion t (marked by below), then go downwards towards other ''required'' intermediate propositions by making use of the known premises. The final proof of the argument form will be essentially in the reverse order of the ''reverse route''. The main idea is to try to lead from the conclusion to eventually reach only the premises.

From the above diagram we see that we could derive the conclusion tin the order of

With the help of the above order of derivation, we have

(a) r, q r, q (modus tollens)

(b) q, p q, p (disjunctive syllogism)

(c) q, q u s, u s (modus ponens)

(d) u s, s (conjunctive simplification)

(e) p, s, p s (conjunctive addition)

(f) p s, p s t, t (modus ponens)

That is, the conclusion is derived from the use of the basic inference rules.

Can you do example 6 once agagin, with some differences?
Solution The ''dumbest'' way is to try to determine for each proposition (symbol) if it is true or not. This way one could be wasting a lot of time unnecessarily; but this often ensures one gets closer and closer to the solution of the problem.
In the argument form in examples 5-6, we have 6 basic propositions p, q, r, s , t and u. We will now proceed to determine (in the order dictated by the actual circumstances) whether each of these 6 propositions is true or not.

(i)

r is given as a premise, so the truth value of proposition r is already determined (r is false).
(ii)

q r, r, q,    so the truth value of q is determined (q is false).
(iii)

p q, q, p,    so the truth value of p is determined (p is true).
(iv)

q, q u s, u s.
(v)

u s, u,    so u is determined (u is true).
(vi)

u s, s,    so s is determined (s is true).
(vii)

p, s, p s.
(viii)

p s, p s t, t,    so the truth value of t is determined (t is true).

We have by now established the truth value of all the concerned basic propositions p,q,r,s,t,u. We can now proceed to determine if the conclusion t of the original argument form is true or not. In this case, it is obvious because we have already shown t is true. So the argument form (*) in example 5 is valid. Notice that step (v) is completely unnecessary. But we probably wouldn't know it at that time.
Note This ''dumb'' method can be very useful if you want to determine whether or not the conclusion of a lengthy argument form is true or not. I'll leave you to think about why.

A detective established that one person in a gang comprised of 4 members A,B,C and D killed a person named E. The detective obtained the following statements from the gang members (S_A denotes the statement made by A. Likewise for S_B, S_Cand S_D)

(i): S_A: B killed E.
(ii): S_B: C was shooting craps with A when E was knocked off.
(iii): S_C: B didn't kill E.
(iv): S_D: C didn't kill E.

The detective was then able to conclude that all but one were lying. Can you decide who killed E?

Solution Let (1)--(4) to be given later on be 4 statements. The 1st two, (1) and (2) below, are true due to the detective's work.

(1):: Only one of the statements S_A, S_B, S_C, S_D. is true
(2):: One of A, B, C and D killed E.

From the (content of the) statements S_A and S_C we know

(3):: S_A S_D is true because if S_A is true, then B killed E which implies C didn't kill E due to (2), implying S_D is also true.

and from (1)

(4):: S_A S_B S_C S_D is true.

Let us examine the following sequence of statements.

(a) S_A S_D S_A true implies S_Dtrue, i.e. (S_A, S_D) (from (3))

(b) S_A S_B S_C S_D S_A true implies S_B, S_C and S_Dall false (from (4))

(c) S_B S_C S_D S_D conjunctive simplification (direct)

(d) S_A S_D hypothetical syllogism (from (b), (c))

(e) S_D S_A modus tollens (from (a))

(f) S_A S_A hypothetical syllogism (from (d), (e))

We note all the statements on the sequence apart from the first two (a) and (b) are obtained from their previous statements or form the valid argument forms. However the first 2 statements (a) and (b) are both true hence the conclusion in (f) is also true. A statement sequence of this type is sometimes called a proof sequence with the last entry called a theorem. The whole sequence is called the proof of the theorem.

Alternatively sequence (a)--(f) can also be regarded as a valid argument form in which a special feature is that the truth of the first 2 statements will ensure that all the premises there are true.

From (3) and (4) and (a)--(f) we conclude S_A S_A is true. Hence S_A must be false from the rule of contradiction (if S_A were true then S_A would be true, implying S_A is false: contradiction).

From the definition of S_C we see S_A S_C. From the modus ponens

S_A S_C, S_A, S_C

we conclude S_C is true. Since (1) gives

S_C S_A S_B S_D ,

we obtain from the (conjunctive simplification) argument

S_C S_A S_B S_D, S_A S_B S_D S_D, S_C S_D

that S_C S_D. Finally from modus ponens (S_C S_D, S_C, S_D) , we conclude S_D is true, that is, C killed E. We note that in the above example, we have deliberately disintegreted our argument into smaller pieces with mathematical symbolisation. It turns out that verbal arguments in this case are much more concise. For a good comparison, we give below an alternative solution.

Re-do the previous qestion more directly.
Solution (alternative for example 6) Suppose A wasn't lying, then A's statement B killed E is true. Since A spoke the truth means B,C and D would be lying, hence the statement C didn't kill E said by D would be false, implying C did kill E. But this is a contradiction to the assumption A spoke the truth. Hence A was lying, which means B didn't kill E, which in turn implies C spoke the truth. Since only one person was not lying, D must have lied. Hence Cdidn't kill E is false. Hence C killed E.

Predicate Calculus

The statement that |sin (x) | 1 for any real-valued number x can be written in either of the following forms

Hence we see that the domain of a predicate could also be absorbed in the predicate itself.

parentheses
,
,
,

Let be the set of natural integers, i.e. ={ 0, 1, 2, ... }. Represent mathematically the following statements.

(a)

The sum or subtraction of any integers will remain an integer.
(b)

An integer, if divided by an integer, may not remain an integer.
(c)

There exist 2 integers such that the sum of the squares of these 2 integers can be written as the square of an integer.
(d)

The sum of the squares of any 2 integers can be written as the square of an integer.

Solution We'll explain in more details in the first 2 cases.
(a)
This statement can be written in any of the following 3 forms
This is because essentially (m+n) says the sum of 2 integers is again an integer, and (m-n) says likewise for the subtraction of 2 integers. We note that while the 1st form is perhaps the neatest, the 1st and the 2nd forms can both be interpreted as an equivalent ''shorthand'' notation of the 3rd form. Moreover, the 3rd form can be regarded as an embedded predicate statement because the 3rd form can considered as
m , P(m) ,
where P(m) for each given m is again a predicate statement:
n , ((m+n) ) ((m-n) )) .
(b)

First we rephrase the original sentence in a form closer to the mathematical language. It is easy to observe that the original sentence is equivalent to ''There exist 2 integers such that the division of the 1st integer by the 2nd integer is no longer an integer''. Written symbolically,
m, n ,    m/n .
Obviously the above form can also be written in other equivalent variant forms similar to the case (a).
(c)

m , n , p ,   m²+n² = p².
(d)

m , n , p ,    m² + n² = p².
Are the 2 statements (a) and (b) below true?

(a)

m , n , p , m²+n² = p² and m,n,p 1.
(b)

m , n , p , m² + n² = p².

Solution We note that more than 1 quantifier are used in both (a) and (b).

(a)

Though m = 0, n = 0 and p=0 satisfy m² + n² = p², they do not satisfy m,n, p 1. Hence this case is not able to shed much light on the validity of the statement (a). However m=3, n=4 and p=5 satisfy both m² + n² = p² and m, n, p 1. We see that (a) is true regardless of other cases of m,n and p.
(b)

For m = 0, n=0, we can choose p=0 so that m² + n² = p², i.e. the predicate is true in this particular case. However, for m =1 and n=1, we see that if a p satisfies p² = m² + n² = 2, then p must be . But no such nonnegative integers p satisfy p²=2. Hence (b) is false.
For those who happen to know a little about taking a limit of a sequence, we just mention that if the following statement is true
{ x , x > 0 }, N , n { x , n N }, |a_n - a| < .

What is the negation of the statement ''Everyone loves someone''?
Solution Let D denote the set of all people, and predicate L(x,y) denote that person x loves person y. Then the statement ''Everyone loves someone'' can be written as
x D, y D, L(x,y)
or equivalently ( x D, ( y D, L(x,y) ). Hence the negation is
x D, y D, L(x,y)
which means ''There is someone who loves no one''. We note here the order in which the quantifiers appear is important. If for instance we change the order of quantifiers for the original statement and consider instead
y D, x D, L(x,y) ,
we see that this new statement is true means that ''There's someone everyone loves'' which is quite different from the original statement.
Let S be the set of all students and A, the set of all assignments. Let predicate D(x,y) denote that student x has done assignment y, and predicate P(x) denote that student xpasses this unit. Represent the predicate statement ''If a student does all the assignments, then he or she will pass this unit''.
Solution We begin with writing out certain related simpler but uesful components. We first observe that student x does all assignments can be written as
y A, D(x,y).
Hence the statement ''If student x does all the assignments, then he or she will pass this unit'' can be written as
( y A, D(x,y)) P(x) .
It is now straightforward to see that the original statement ''If a student does all the assignments, then he or she will pass this unit'' can thus be simply denoted by
x S, ( y A, D(x,y)) P(x) .

Give the contrapositive, converse and inverse of the statement ''If a real number is greater than 3 then its square is greater than 4''.
Solution The statements can be written as

original: x , (x > 3) (x² > 4) (a)

contrapositive: x , (x² 4) (x 3) (b)

converse: x , (x² > 4) (x > 3) (c)

inverse: x , (x 3) (x² 4) (d)

It is easy to see that (a) and (b) are both true, while (c) and (d) are both wrong. For example, if we take x = 2.5 in (c) we have x² = 2.5² > 4 but x > 3 is false. Hence (c) is false.

Statement ''One has to drink water in order to survive'', means for any person, drinking water is a necessary condition for survival, i.e.
person x, (x drinks water) (x survives).
It is obviously not a sufficient condition because drinking water alone is not enough to guarantee the survival of a person, i.e. the statement
person x, (x drinks water) (x survives)
is not true.

Set and Its Connection with Boolean Algebra

{ rose, daffodil, carnation } is a set of flower names.

Let A = {1,2,3,{4}, {1,2} } and B = {1,2, {4}, 5 }, which are obviously both sets. Then

(a)	2 A	2 is an element of A
(b)	4 A	4 is not an element of A
(c)	{4} A	{4 } is an element of A
(d)	{4} A	{4} is not a subset of A because the element 4 in {4} is not an element in A
(e)	{1,2} A	1,2 are both elements of A
(f)	{1,2} A	{1,2} is an element of A
(g)	B A	5 B but 5 A
(h)	A B = { 1,2,3, {4}, 5, {1,2,}}	union of A and B
(i)	A B = { 1,2, { 4}}	intersection of A and B
(j)	A - B = { 3,{1,2}}	set A minus set B
(k)	B-A = {5}	set B minus set A

The power set of A = { 1,2,3} is
{(A)} = { , {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}} .
Let A₁ = {1,2} and A₂ = {3}, then {A₁,A₂} is a partition of A = {1,2,3} because A₁ and A₂ are disjoint and A₁ A₂ = A. Let B₁ = { x | x < 0}, B₂ = { x | x 0} and B₃ = { x | x 0 }. Then {B₁, B₂} is a partition of but {B₂, B₃} is not a partition because B₂ B₃ .
Let be taken as the universal set and let be the set of rational numbers. Then the complement of , i.e. ' = { x | x } is the set of irrational numbers.

= { (x,y) | x,y } represents a plane.
{1,2} { 3,4,5} = { (1,3), (1,4), (1,5), (2,3), (2,4), (2,5) }.
{1,2} = {2,1} but (1,2) (2,1).

Efficiency, Big

Let f: be given by f(n) = 2n -3. Show f(n) = (n).
Solution Observe

By taking C = 3 and M =3 (and D = ), we see f(n) is (n). We note that there are many different yet all valid choices of Cand M. For example,

implies we can choose C=5 and M =1 in the definition of f(n) = (n).
Show is () for x .
Solution The inequality

i.e. |f(x)| 21 for x 1, gives immediately f(x) = () (by choosing C = 21 and M=1 in the definition).
Let f(n)=n(n+5). Prove f(n)=(n²).
Solution We need to find constant M and positive constant Csuch that |f(n)| Cn² for all n M. There are different ways to achieve this, and we give below 2 most obvious ones.

(a)

We take in this case M=1 and C=3.
(b)

We take in this case M=5 and C=2.
From (a) or (b) we see that f(n)=(n²).
For m n 0, xⁿ = (x^m).
Solution DIY.

n = (n) is obviously true. But the reversed identity (n) = n is not true, because 2n is (n) but is not equal to the r.h.s. n.

Mathematical Induction

Suppose (a) Foxes can only give birth to foxes and (b) Jim is a fox. Will Jim ever have a rabbit as one of his future offspring?
Solution Just about everyone will say ''not possible'' immediately. Why? This is because the P.M.I. is already in our natural mind without being noticed. However, let us see how the underlying logic works mathematically.
Let S_n denote the statement that Jim's offsprings of the n-th generation are all foxes. Then

(i)

S₀ is true, because Jim's offsprings of 0-th generation consists of Jim himself alone, who from (b) is a fox.
(ii)

Assume S_k is true with k 0, i.e. the k-th generation of Jim's offsprings are all foxes. Then, according to (a), all the children of this k-th generation can only be foxes. That is the (k +1)-th generation of Jim's offsprings will all be foxes. i.e. S_k+1 is true.
From the P.M.I., we conclude S_n is true for all n 0. Hence all Jim's offsprings will be foxes. In other words, Jim will never have a ''rabbit'' as one of his offsprings. It is perhaps surprising that just about everyone can subconsciously perform the above reasoning, with the use of the principle of mathematical induction, in a nip of time.
Prove inductively for all integers n 1,

(*)

Solution Let S_n denote the statement (*). Since th initial index for n 1 is n = 1, we first verify

(i)

S₁ is true:

Hence equality (*) holds for n=1, meaning S₁ is true.
(ii)

Assume S_k is true for some k 1, then by the definition of S_k we have

(**)

We now prove S_k+1 is also true. For n = k+1,

i.e. S_k+1 is true.

We thus conclude from the P.M.I. that S_n is true for all n 1. This means (*) will hold for all integers n 1.
Can you do the above example once again, but this time perhaps more informally?
Solution Let us consider how to prove by induction the following statement

(1)

First, we are happy with the first case (initial index m=1) because S₁ is true as is readily verified via _j=1¹ =1 and (1/2)1(1+1)=1. The main task is the step from the assumption of S_k being true to the proof of S_k+1 being true. In other words, we, by assuming

(2)

have to show

(3)

is true as well. But how can we prove (3) by perhaps the use of knowledge in the form of (2)? Well, the idea is to examine both sides of the statement in (3) to see if we can ''dis-integrate'' or ''break'' the expressions into the forms that are present in the existing knowledge (2), plus the ''nasty bits''. For instance, the l.h.s. of (3)

(4)

is ''deceiving'': we can't use the existing knowledge (2) on it directly. So we break the expression (4) into

(5)

in which the last term (k+1) is the ''nasty bit'', while the first expression is in the ready form for the use of (2). In general, one can not expect to prove a nontrivial statement for n=k+1 without using the assumption for n=k. Thus we expect that we won't be able prove the statement (3) without replacing part of its expression by using the assumption (2). Hence the purpose in establishing (5) for (4) and thus for the l.h.s. of (3) is that we can now use the knowledge (2). Since now we are able to break the l.h.s. of (3) into the form of (5), and the _j=1^k j part in (5) can be replaced by the known (2), (thus successfully making use of the assumption (2): almost a must!), we can now hope that the outcome will be equal to the r.h.s. of (3) because we have used the assumed knowledge (2). (If this were not the case, then further this type of ''breaking'' would be needed.)
We are now ready to proceed. The l.h.s. of (3) is

,

which is

After replacing _j=1ⁿ j by k(k+1)/2 due to (2), it reads

which is then simplified to

This completes the proof that assumption (2) for n=k implies the result (3) for n=k+1. Combining with the earlier validation of S₁, the statement S_n is proved by mathematical induction for any integer n 1.
What would happen, if I were unlucky and looked at the expression (3) in example 3 on the right hand side?
Solution If we are ''unlucky'', no worries, at most just a bit extra work. Let us assume that we looked the other way and saw the r.h.s. of (3) first and we still want to prove it by making use of the induction assumption (2). The first step is to ''break'' that expression into containing forms that are identifiable with some of those in (2). But for expression like

(6)

Yes, a bit tricky, but can still be done. Let us first examine the expression in (6). It is a 2nd order polynomial in k with a leading coefficient {1\over2}. Let us now examine the expression in r.h.s. of (2), it is also a 2nd order polynomial in k. So we can imagine

(7)

in which the ''nasty bits'' can be calculated as

which is just (after simplification)

(k+1) (8)

Thus the r.h.s. of (3) is equal to

in which the first part is _j=1^k j due to (2) and second part is (k+1) due to (7) to (8). We thus finally have that the r.h.s. of (3) is equal to

and that (3) is proved through the use of (2).

Let n,r with r n. We define {n \choose r}, called ''n choose r'', to be the total number of r-element subsets that can be chosen from a set of n elements. We thus have

(a) only 1 empty set
(b) the only subset with all elements in it is the set itself
(c) if r 1, n>1}

Let us briefly explain (c). Suppose S be a set of n elements and a S is any element, then S = T {a} if T = S - {a}. To choose r elements from S (there are different ways to do so), we can either choose r elements from T entirely (there are different ways to do so), or choose a as one element and another r-1 elements from T (there are different ways to do so). Hence (c) is valid.
Recall the convention 0! =1. Let us prove

(***)

Solution Let S_n denote the following statement

(i)

S₀ is true from either (a) or (b), because .
(ii)

Assume for n 0, S_k is true for all 0 k n. Then from (c) for 1 r n we have

As for r=0 and r = n +1, we see from (a) and (b)

Hence S_n+1 is true..
From (i) and (ii) and the S.P.M.I. (with m=m'=0), we conclude S_n is true for all n 0.
For integer n 1 show the following statement (often called binomial theorem or binomial expansion) is true
S_n:
Solution

(i)

S₁ is true because

(ii)

Assume S_k is true for some k 1, then

i.e. S_k+1 is true.
Hence from the P.M.I. we conclude S_n is true for all n 1.

Prove 2n + 1 < 2ⁿ, n 3.
Solution I'm quite exhausted by now; if you're not then supply the proof yourself.

Analysis of Algorithms

Find 13 from the ordered list {1,3,5,7,9,13,15,17,19 } with both the binary search and the sequential search. Give the number of comparisons needed in both cases.
Binary search. 3 comparisons are needed as can be seen from the diagram below

Sequential search. 6 comparisons are needed in this case, see

Notation

Let f: be given by f(n) = 2n+1. Then

(a)
f(n) = (n²) ,
(b)
f(n) = (n) .

Solution

(a)

|f(n)| = 2n + 1 2n² + n² = 3n² for n 1 implies f(n) = (n²) by the 1st principle, i.e. by the definition.
(b)

We need to find the upper bound and the lower bound for the function f(n). From

i.e. 2n |f(n)| 3n for n 1, we easily conclude f(n) = (n).
Let f: be given by . Show

(a)
f(n) = (1) ,
(b)
f(n) = (1) .

Solution

(a)

i.e. |f(n)| (1/2) (1) for any n 1. Hence f(n) = (1) (with C = 1/2 and M = 1).
(b)

We already found an upper bound for f(n) in (a); we just need to find a lower bound in order to show f(n)= (1). Since n 2 implies n-1 n/2, we have

i.e. 1 8|f(n)| for n 2. Hence, together with the upper bound found in (a), we have

or |g(n)|/8 |f(n)| |g(n)|/2 for g(n) 1, with M=2, C=1/2 and D=1/8. According to the definition, we thus have f(n)= (g(n)), i.e. f(n) = (1).

What on earth is the big ''''?
Solution Big is essentially a measurement for the magnitude of functions at ''infinity'', and tells roughly who is ''bigger''. We say function f(n) is of order of big of function g(n), i.e. f(n)= (g), if the magnitude of f(n) will be eventually bounded from above by a constant multiple of the magnitude of g(n). Magnitude |f(n)| bounded by a constant multiple of that of g means

|f(n)| C |g(n)| (*)

for a constant C>0, while ''eventually'' means (*) needs only to be valid for the ''later'' n's. In other words, (*) needs only to be true for n M for a constant M. We note that what the actual values the positive constant C and the constant M take is not important, what is important is that once a C is chosen, it has to remain unchanged in (*) for all n M. This is like comparing the potential weight (magnitude) of a cat and a dog: we have to wait until they have fully grown up (n M), but exactly when (i.e. the value of M) is not really important.
Let f: be given by . Show in very rudimentary details how we can prove f(n)= (n²).
Solution From the definition of notation, we have to establish an upper bound and lower bound, corresponding to the 2nd and the 1st inequality relation in the formula below
D |n²| |f(n)| C |n²| .
To establish an upper bound is to find some positive constants C and M such that

(1)

is true at least for n M. But how can we do this? And in what general direction should we proceed? We observe that on the r.h.s. of (1) it is a just a single term, while the l.h.s. of (1) is a polynomial fraction.
We will now try to ''move'' from the expression

(2)

to the expression

C n² (3)

gradually, in terms of the '' '' sign. In such ''moves'', we will keep some terms intact, dump some terms and replace some terms. The general rule is that one should always keep the dominant (leading) terms, while throwing away or manipulating other non-dominant terms in an expression. Back in expression (2), we see that the dominant term in the numerator n³+2n²-1 is n³ while the the dominant term in the denominator n+1 is n. So we are happy to throw away (legitimately) the term -1 in the numerator to arrive at a simpler form (which is closer to the final target in (3)). We thus get the first ''move''

(4)

Because the numerator and denominator of the result

(5)

of the first ''move'' are both non-negative, we throw away the ''1'' in the denominator of (5), because the less the denominator, the larger the total fraction. Hence our 2nd ''move'' is

(6)

The newly obtained result after the 2nd move is thus

n²+2n (7)

which is even closer to (3). How do we make the last ''move''? We observe that (7) contains inhomogeneous terms (i.e. different powers) while (3) contains only an homogeneous term. So our next step is to ''promote'' legitimately other orders to the same leading order n². In doing so, we notice that

2n 2n²

when n 0, hence our 3rd ''move'' gives

n²+2n n² +2n² = 3n² .

Putting all the above ''moves'' together, we obtain for n 0

(8)

Since value of (2) is non-negative if n 1, we see that (8) implies

(9)

is true for all n 1. In other words, (1) is true if we choose C=3 and M=1.
Now we proceed to establish a lower bound for f(n). We need to find positive constant D and constant L such that

(10)

for all n L. If we can establish (10), then along with the already established (1), we see that

(11)

is true for n = max(M,L).
To derive (10), we proceed similarly. First let us throw away some non-significant terms legitimately, by keeping the dominant ones and assuming n 1 (thus (2) is non-negative). Our first ''move'' is to throw away the term 2n² in the numerator of (2). Notice that our new ''moves'' are for the '' '' sign, not the '' '' as in the previous case. Thus we can't throw way the ''-1'' in the numerator and ''1'' in the denominator as they would break the sought '' '' sign. Hence after the first ''move'', we obtain

(12)

Next, let us promote the (non-leading) ''1'' in the denominator to arrive at an homogeneous expression, i.e. we need to promote the ''1'' into something like ''constant n''. This turns out easy as 1 n thus 1/(n+1) 1/(n+n) for n 1. Hence our 2nd ''move'' gives

(13)

Observe the r.h.s. of (13), we see that we need to promote the ''-1'' in the numerator to the form of ''constant n³'' to ensure homogeneity. In other words, we need to establish something like

-1 constant n³ . (14)

It would be obviously true if we choose the constant in (14) to be just say -2 and ask for n 1. But this would inflict out-of-proportion damages on our leading term n³. So we have to choose the constant carefully. Since n³ is eventually much larger than the lower order term -1, we can take out a portion of n³, say n³/4 without affecting the magnitude order, and use it to compensate the ''-1''. In other words,

(15)

If we choose n large enough, then the terms in the square brackets in (15) will be non-negative, and then we can legitimately throw that away because we are establishing a '' '' relation. To ensure

(16)

we need n 4^1/3. Hence if we choose n 2, it will be enough to guarantee the non-negativeness in (16). Hence our 3rd ''move'' is

or

(17)

Putting ''moves'' 1--3 together, we obtain

(18)

Notice that (18) and (9) can be put together as

which implies f(n)= (n²).
Redo example 4 in such a (recommended) way that the proof will be both concise and mathematically acceptable.
Solution To find an upper bound we first observe

The inequality above was due to the (legitimate!) increase of the numerator and the decrease of the denominator, it could be done so because we were looking for an upper bound. Obviously we won't allow in this case a decrease of the numerator or an increase of the denominator. To find a lower bound, incidentally, the oppsite is true. We have thus so far shown
|f(n)| 2n² , whenever n 2 .
For a lower bound, we observe

which means
|f(n)| n²/2 , whenever n 1 .
Hence, by putting together the upper bound and the lower bound, we have
n²/2 |f(n)| 2n² , whenever n 2 .
This in the definition of notation corresponds to C=2, D=1/2 and M=max(1, 2)=2 where, for any values a and b, max(a, b) denotes their maximum value. Hence we finally conclude f(n)= (n²).
Show that log₂ n =(n) for positive integer n.
Solution We first prove by induction the statement
S_n: log₂ n < n
for n 1. Obviously S₁ is true because l.h.s.= log₂ 1=0 < 1=r.h.s. Assume S_k is true for an integer k 1, i.e. log₂ k< k, then
log₂ (k+1) log₂( k + k) = log₂(2k) = log₂ 2 + log₂ k =1 + log₂ k < 1 + k ,
i.e. log₂ (k+1)< k+1. Hence S_k+1 is also true. From the P.M.I. we have thus shown that S_n is true for all integers n 1. Since log₂ n 0 for n 1 implies | log₂ n|= log₂ n |n| for n 1, we finally conclude log₂ n=(n).

Number Bases

When base number p=2, the system is called the binary number system. Two digits are needed, and these two digits are chosen to be ''0'' and ''1'', consistently representing the values of 0 and 1 respectively. For example,
(1011.1)₂ = 1 2³+0 2²+1 2 + 1+1 (1/2) =(11.5)₁₀ ,
i.e. 1011.1₂ is equal to 11.5 in decimal.
When base p=8, the system is called the octal number system. Naturally we still conveniently use the existing first 8 digits in the decimal system, i.e. 0,1,2, ,7, to denote the corresponding values for the new number system. For example,
13.7₈=1 8¹+3 8⁰+7 8^-1=11.875 ,
i.e. 13.7₈ represents the decimal number 11.875.
When p=16, the system is called the hexadecimal number system. 16 digits are needed in this system, representing values from 0 to 15. We shall still make use of the 1st 10 digits 0,1, , 9 from the decimal number system, and use A,B,C,D,E,F to make up for the rest of the digits. Hence the digits for the hexadecimal system are
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F ,
representing 0 to 15 respectively. For example,

A 7F₁₆ = A 16²+7 16¹ +F 16⁰

= 10 16²+7 16 + 15 1 = 2687 .
When p=10, the system is our standard decimal number system. Thus for instance (36429)₁₀ is just 36429.

Convert 45 to base 4.

That is, we first divide 45 by 4. The quotient 11 is then divided by 4, with the new quotient 2 being again divided by 4. This repeating process is then stopped because the latest quotient has reached 0. The remainders obtained at these division steps, when listed in the reverse order, finally give the desired representation of 45 in base 4.
Convert 123 into binary.
Solution We illustrate here an alternative approach to number conversions. It uses exactly the same algorithm as before, and the only difference lies in the organisation or presentation of the derivation. Obviously you don't have to bother with this approach if you don't like it: the approach adopted in the previous example is already neat enough.

Hence 123=1111011₂.
Convert 0.1 to base 2.

Convert (7A.1)₁₆ into binary format.
Solution Since 16=2⁴, 1 digit in hexademical will correspond to exactly 4 digits in binary. Since

we have
(7A 1)₁₆=(01111010.0001)₂ .
Convert the binary number (1111010.0001)₂ to base 8.
Solution Since 8=2³ implies every 3 consecutive digits, going left or right starting from the fractional point, in binary will correspond to a single digit in base 8. By grouping consecutive digits into blocks of 3, appending proper 0's if necessary, we have
(1111010.0001)₂= (001 111 010.000 100)₂ =(172.04)₈
because 001₂=1₈, 111₂=7₈, 010₂=2₈ and 100₂=4₈.

Find 343₅+114₅ .

i.e. 343₅+114₅=1012₅ . We note that the addition is performed digitwise from the rightmost digit towards the left. On the rightmost digit, 3₅+4₅=7₁₀=(12)₅ gives the resulting digit 2 and the carry 1 to the next digit on the left. On the 2nd rightmost digit, we have thus 4₅+1₅+ (carry) 1₅=6₁₀=(11)₅, resulting to digit 1 plus a new carry 1. As the last step, we then have 3₅+1₅+1₅=5₁₀=(10)₅. This completes our addition.
Find 10011₂-101₂ .

Hence 10011₂-101₂=1110₂ . The subtraction is also performed digitwise from the rightmost digit towards the left. On the rightmost digit, 1₂-1₂=0₂ gives the resulting digit 0. On the 2nd rightmost digit, 1₂-0₂=1₂ gives the result 1. On the 3rd rightmost digit, we borrow 1 from the digit on the left; actually we have to borrow 1 further on the left because the digit on the immediate left is 0 and therefore can't be borrowed. The subtraction on the 3rd rightmost digit thus becomes (10)₂-1₂=2₁₀ -1₁₀=1₁₀=1₂. Finally, the 4th rightmost digit, after borrowed 1 from the left and being borrowed 1 from the right, is left with the remaining 1. This completes the subtraction.

Graphs and Their Basic Types

In the graph below (heavy dots denote vertices, lines or arcs denote edges)

the vertex set V={v₁, v₂, v₃, v₄,v₅}, the edge set E={e₁, e₂, e₃, e₄} and the edge-endpoint function is given by

edge e endpoints (e)

e₁ {v₁}

e₂ {v₁, v₂}

e₃ {v₂, v₃}

e₄ {v₂, v₃}

e₅ {v₂, v₃}

Note The e₁ type edge is called a loop, and e₃, e₄, e₅ type edges are called multiple edges or parallel edges.
In the directed graph below

the vertex set V={v₁, v₂, v₃}, the edge set E={e₁, e₂, e₃, e₄}, and the edge-endpoint function is given by

edge e endpoints pair (e)

e₁ (v₁, v₁)

e₂ (v₁, v₂)

e₃ (v₃, v₂)

e₄ (v₂, v₃)

The complete graph with n vertices is denoted by K_n. The first few are
A graph is complete bipartite if it is a simple graph, and its vertices can be put into two groups so that any pair of vertices from different groups are joined by an edge while no pair of vertices are joined by an edge if they are from a same group. Such a graph is denoted by K_m,n if the two groups contains exactly m and n vertices respectively. For example,

A graph H is a subgraph of graph G iff

(i)

V(H) V(G),
(ii)

E(H) E(G),
(iii)

every edge in H has same endpoints as in G.

Suppose we let V={v₁, v₂, v₃}, E={e} and ₁(e)={v₁, v₂}, then graph G₁(V,E, ₁) can be drawn as

If we choose ₂(e) = {v₂, v₃} then graph G₂ = (V,E, ₂) represents

Although it is obvious that
V(G₂) V(G₁) , E(G₂) E(G₁) = {e} ,
the endpoints of e in G₂ are different from those of e in G₁. Hence G₂ is not a subgraph of G₁.
Note Intuitively we see from the diagram that e={v₂, v₃} in G₂ is not an ''edge'' of G₁ breaks the condition (ii) in this definition of a subgraph. This argument is however based on the implicit edge association with the corresponding end points. In other words, condition (iii) may be dropped, as in some texts, if the condition (ii) is extended in this sense. See the note at the end of this lecture for further explanations.
For graph G

graph H

and graph F

are both subgraphs of G.

For graph

we have (v₁)=5, (v₂)=4, (v₃) =1 and (v₄)=0.

Graph G

is disconnected, because we can't walk from vertex v₄ to for instance vertex v₁, i.e. there is no walk from v₄ to v₁. Obviously G can be decomposed into three connected components G₁, G₂ and G₃.

V(G₁) = {v₁, v₂, v₃} , E(G₁) = {e₁, e₂} ;

V(G₂) = { v₄} , E(G₂) = (the empty set) ;

V(G₃) = { v₄, v₅, v₆} , E(G₃) = {e₃, e₄, e₄} .

This way each of G₁, G₂ and G₃ is a connected subgraph.

Graph

is planar because it can be drawn as
Graph

is nonplanar because, after removing edges e and f, and vertex v, the graph becomes K_3,3. Hence Kuratowski's Theorem implies the original graph is nonplanar. We note that removal of vertex like v (and then connecting the end points v₁ and v₂) is called series reduction. If a graph is planar, then obviously any of its subgraphs is also planar, even if series reductions are further performed. Hence Kuratowski's Theorem can be rephrased as saying a graph is nonplanar iff it contains a subgraph which, after series reduction, is K₅ or K_3,3.

Eulerian and Hamiltonian Circuits

In the following graph

(a)

Walk v₁e₁v₂e₃v₃e₄v₁, loop v₂e₂v₂ and vertex v₃ are all circuits, but vertex v₃ is a trivial circuit.
(b)

v₁e₁v₂e₂v₂e₃v₃e₄v₁ is an Eulerian circuit but not a Hamiltonian circuit.
(c)

v₁e₁v₂e₃v₃e₄v₁ is a Hamiltonian circuit, but not an Eulerian circuit.
K₃ is an Eulerian graph, K₄ is not Eulerian.
Graph

has an Eulerian path but is not Eulerian.

Due to the above Euler's theorem, the seven bridge problem described earlier has no solution, i.e. the graph in the problem does not have an Eulerian circuit because all vertices there (A, B, C, D) have odd degrees.
As for the travelling salesman problem, we need to find all the Hamiltonian circuits for the graph, calculate the respective total distance and then choose the shortest route.

route total distance

A B C D A 30 + 30 + 25 + 40 = 125

A B D C A 140

A C B D A 155

A C D B A 140

A D B C A 155

A D C B A 125

Hence the best route is either ABCDA or ADCBA.

Find an Eulerian path for the graph G below

We start at v₅ because (v₅) = 5 is odd. We can't choose edge e₅ to travel next because the removal of e₅ breaks G into 2 connected parts. However we can choose e₆ or e₇ or e₉. We choose e₆. One Eulerian path is thus

Graph Isomorphism and Matrix Representations

Show graphs G₁ and G₂ below are isomorphic.

Solution How to find isomorphism function g and h in general will be clearer when we introduce the concept of isomorphism invariants later on. But at this stage it is mostly guesswork. Let g and h be given by

g(v₁) = w₂, g(v₂) = w₁, g(v₃) = w₄, g(v₄) = w₃ ,

h(e₁) = f₂, h(e₂) = f₁, h(e₃) = f₄, h(e₄) = f₃, h(e₅) = f₅

which can be alternatively represented in the diagrams below

We now verify the preservation of endpoints under g and h

e₁ {v₁,v₂} f₂ {w₁,w₂} = {g(v₁), g(v₂)}

e₂ {v₂, v₄} f₁ {w₁,w₃} = {g(v₂), g(v₄)}

e₃ {v₂,v₃} f₄ {w₁,w₄} = {g(v₂), g(v₃)}

e₄ {v₁,v₄} f₃ {w₂,w₃} = {g(v₁), g(v₄)}

e₅ {v₃,v₄} f₅ {w₃,w₄}= {g(v₃), g(v₄)} ,
where we used e {v, w} to indicate that edge e has endpoints {v, w}. Since g and h are obviously one-to-one and onto, the pair g and h thus constitute an isomorphism of graphs G₁ and G₂, i.e. G₁ and G₂ are isomorphic.

Graphs G₁ and G₂ below

are not isomorphic to each other because vertex v of G₁ has degree 5 while no vertices of G₂ have degree 5.
Back to example 1. We now explain briefly how we found the isomorphism functions g and h there.
First, since v₂, v₄ in G₁ and w₁ and w₃ in G₂ are the only vertices of degree 3, g must map v₂, v₄ to w₁, w₃ or w₃, w₁ respectively. We thus choose g(v₂) = w₁ and g(v₄) = w₃. Since {v₂, v₄} are the endpoints of e₂, we must have h(e₂) = f₁ so that the endpoints {v₂, v₄} of edge e₂ are preserved because f₁ has endpoints {w₁, w₃} = {g(v₂), g(v₄)}.
Next we need to map v₁, v₃ to w₂, w₄ or w₄, w₂ respectively. If we choose w₂ = g(v₁) we must have w₄ = g(v₃). Thus the edge e₁ joining v₁ and v₂ should be mapped to the edge f₂ joining g(v₁) = w₂ and g(v₂) = w₁, i.e. f₂ = h(e₁). The rest of g and h can be determined similarly.

The adjacency matrix of digraph

is
The adjacency matrix of graph

is

Consider the digraph

which has the adjacency matrix A below

Since

we see there are exactly \shade{2} walks of length 2 that start at v₃ and end at v₁. Since

has only 0's in the third column, we conclude that no vertex can reach v₃ via a walk of nonzero length.

Trees

Graphs

are both trees.
Graph

is not a tree.

List all (up to isomorphism) trees of 4 vertices. From the Lemma, there exists a vertex, call it v₀, of degree 1. We denote by v₁ the only vertex which is connected to v₀. Since there are exactly 3 edges in a tree of 4 vertices, the highest degree v₁ can attain is 3. It is also obvious that v₁ must have at least 2 edges because otherwise edge {v₀, v₁} would be disconnected from the remaining vertices, which would contradict the definition of a tree. Hence we conclude 2 (v₁) 3 and will enumerate the two cases below.

(a)

(v₁)=3.

(b)

(v₁)=2. This means v₁ is connected to another vertex v₂. Since only one extra edge is needed, the edge has to be attached to v₂.

Hence there are exactly 2 different trees, which are (a) and (b) respectively.

Draw a binary tree to represent ((a-b) c) + (d/e).
Solution

For binary tree

the traversals are as follows.

The binary tree representation of (a+b c)/d is easily seen as

But how is the calculation actually done? It may be processed via a postorder traversal

a, b, c, , +, d, / ( )

by interpreting each binary operation as acting on the 2 quantities immediately to its left. That is, , , , ,*, means , , ( * ), , if , , , are numbers and * is any binary operation. This way, the formula is processed successively in following sequence

a , b , c , , + , d , /
a , b c , + , d , /
a+b c , d , /
(a + b c)/d .

The sequence ( ) is said to be in the Polish postfix notation.

Use a binary tree to sort the following list of numbers
15, 7, 24, 11, 27, 13, 18, 19, 9 .
We note that when a binary tree is used to sort a list, the inorder traversal will be automatically assumed in this unit.
Solution To sort a list, just create a binary tree by adding to the tree one item after another, because the insertion is essentially a sorting process. The binary tree constructed during the course of sorting the above list then reads

The sorted list is thus
7, 9, 11, 13, 15, 18, 19, 24, 27 .
We note that a better tree sorting algorithm will involve balancing the trees. However such additional features fall beyond the current unit scope.

Spanning Trees

Graph G

becomes

after removing edge {v₂,v₃} from G to break the cycle v₅ v₂ v₃ v₅, and becomes a spanning tree

after removing edge { v₄,v₃} to break the last remaining cycle v₅ v₃ v₄ v₅. Of course, there can be different spanning trees for the same connected graph G.
Suppose we want to establish a communications network among four centres A,B,C and D, and due to geographical problems direct communications (via cables for instance) may only be established between the two centres connected by an edge is the graph

Suppose each communication link (edge) costs 1000 to install. Since communications may be relayed via intermediate centres, we may choose a spanning tree to lay the communication links so as to minimise the total cost. We now list below all possible spanning trees

each will thus only cost 3000 to build, in comparison with the 5000 (5 edges) required for the original graph G.
Back to the graph G in example 1, see the graph below

Recall that a spanning tree was obtained there by breaking all the cycles in the graph. However, we can also construct a spanning tree in the opposite way, that is, by gradually collecting edges from G, and making sure that the resulting subgraph is always connected and contains no cycles. For instance, a spanning tree T₄, different from that obtained in example 1, can derived from the following 4 steps

Notice that neither e₅ nor e₆ can be added because that would create cycles. We stop the procedure when consideration for all edges are exhausted.

Find a spanning tree for the graph

Solution Since the graph is already provided with a vertex list and an edge list, we might just as well use these lists as the outcome of steps (i) and (ii) though we could use lists of different orders. Steps (iii)-(vi) can be summarised in the following table

Notice that at step 1, since e₁ has vertices v₂ and v₃ and L(2)=2 L(3)=3, we thus change L(2),L(3) both to 2 and add e₁ to the spanning tree. At step 5, since e₅ has vertices v₂ and v₄ and L(2)=L(4)=2 (at the end of step 4), we know from (v) that we can't add e₅ to the tree (because the addition of e₅ would create a cycle). At step 7, since e₇ has vertices v₁ and v₂ whose labels are 1 and 2 respectively, we change in this step all the labels with value either 1 or 2 to the min(1,2)=1. At step 10, nothing needs to be considered because all labels are now equal at the end of step 9, implying the spanning tree is already obtained. The spanning tree, collecting the edges in the last column, has edges { e₁,e_2,e₃,e₄,e₇,e₉ }, or

Find a minimal spanning tree for the weighted graph

in which the number on the edges indicates the corresponding weight.

Solution Since this is a simple graph, we may use a pair of vertices to represent an edge. One possible list of edges ordered in increasing weight is

e₁={v₂,v₃} , w(e₁)=1 ; e₆={v₅,v₇} , w(e₆)=4 ;

e₂={v₅,v₆} , w(e₂)=2 ; e₇={v₁,v₂} , w(e₇)=4 ;

e₃={v₆,v₇} , w(e₃)=3 ; e₈={v₁,v₄} , w(e₈)=5 ;

e₄={v₃,v₄} , w(e₄)=3 ; e₉={v₃,v₅} , w(e₉)=5 ;

e₅={v₂,v₄} , w(e₅)=4 ; e₁₀={v₃,v₇} , w(e₁₀)=7 .

We note that this edge list happens to be the same as that in example 4. The Kruskal's algorithm on this example can be performed/summarised in the following table

in which the numbers conveniently represented by the bar ''---'' are the same as the numbers in the previous step. You may of course use the actual numbers instead if you so prefer. Hence a minimal spanning tree can be formed by the edges {e₁,e₂,e₃,e₄,e₇,e₉}. The corresponding total weight is 18 (=1+2+3+3+4+5).

Relations

Let A={ 1, 3 } and B= { 2, 5 }. Then we ask how elements in A are related to elements in B via the inequality '' ''. The answer is
1 2, 1 5, 3 2, 3 5 .
In other words, 3 pairs (1, 2), (1, 5) and (3, 5) observe the '' '' relationship. Hence by collecting them in R, i.e.
R= { (1, 2), (1, 5), (3 ,5) } ,
we know relation R describes precisely the relationship between elements of A and elements of B under '' ''. For example,

3 R 5 (3, 5) R 3 is related to 5 by R 3 5 ,

3 2 (3, 2) R 3 is not related to 2 by R 3 2 .

Let A ={ 1,2} and B={ 1,2,3} and define a binary relation R from A to B by

for any (x,y) A B: (x,y) R iff x-y is even

(a): Give R by its explicit elements.
(b): Is 1R1 ? Is 2R3 ? Is 1R3 ?

Solution

(a)

For any (x,y) pair in A B ={ (1,1), (1,2), (1,3), (2,1), (2,2), (2,3) }, we must check if xRy or if x-y is even. This is done in the following table

(x,y)	property of x-y	conclusion
(1,1)	1-1 even	(1,1) R
(1,2)	1-2 odd	(1,2) R
(1,3)	1-3 even	(1,3) R
(2,1)	2-1 odd	(2,1) R
(2,2)	2-2 oven	(2,2) R
(2,3)	2-3 odd	(2,3) R

Hence R={ (1,1), (1,3), (2,2)}.

(b)

Yes. 1R1 since (1,1) R.
No. 2R3 since (2,3) R.
Yes. 1R3 since (1,3) R.

Function f: {1,2,3} { 1,2,3,4,5,6} with f(n)=n(n+1)/2 is equivalent to the relation
F={(1,1), (2,3), (3,6)}
in which, for instance, (2,3) corresponds to 3=f(2).

Let A= be the set of all real numbers, and a binary relation S on the set A be defined by
S={ (x,y) | (x-10)²+y² 16, or (x-5)²+y² 4 } .
Graph S in the Cartesian plane.
Solution Recall from analytic geometry that a Cartesian plane is a plane with the normal x and y axis, and a circle of radius r centred at the coordinates (a,b) is given precisely by the equation
(x-a)² +(y-b)²= r² .
Hence equation (x-10)²+y²=16 (=4²) represents a circle of radius 4 centred at the coordinates (10,0), and (x-5)²+y²=4 is a circle of radius 2 centred at the coordinates (5,0). Thus S is the union of these 2 disks, and is represented by the shaded area in the graph below.
Let A={1,2,3} and a binary relation E be defined by (x,y) E iff x-y is even and x,y A. Then E={ (1,1), (2,2), (3,3), (1,3), (3,1)} can be represented by the following digraph

(2,2):

2-2=0 even, hence the loop at vertex labelled by 2 A.
(1,3):

1-3=-2 even, hence the arrow from vertex 1 to vertex 3.

Let A={ 0,1,2,3} and a relation R on A be given by
R={ (0,0), (0,1), (0,3), (1,0), (1,1), (2,2), (3,0), (3,3) } .
Is R reflexive? symmetric? transitive?
Solution We'll make use of the digraph for R on the right.

(a)

R is reflexive, i.e. there is a loop at each vertex.
(b)

R is symmetric, i.e. the arrows joining a pair of different vertices always appear in a pair with opposite arrow directions.
(c)

R is not transitive. This is because otherwise the arrow from 1 to 0 and arrow from 0 to 3 would imply the existence of an arrow from 1 to 3 (which doesn't exist). In other words (1,0) R, (0,3) R and (1,3) R imply R is not transitive.

Note It is equally easy to show these properties without resorting to the digraph.
Let m,n and d be integers with d 0. Then if d divides (m-n), denoted by d | (m-n), i.e. m-n=dk for some integer k, then we say m is congruent to n modulo d, written simply as m n (mod d). Let R be the relation of congruence modulo 3 on the set of all integers, i.e.
m R n m n (mod) 3 3 | (m-n) .
Show R is an equivalence relation.
Solution We just need to verify that R is reflexive, symmetric and transitive.

(a)

Reflexive: for any n we have nRn because 3 divides n-n=0.
(b)

Symmetric: for any m,n if mRn, i.e. m n (mod 3) then there exists a k such that m-n =3k. This means n-m=3(-k), i.e. n m (mod 3), implying finally nRm. For example, 7R4 is equivalent to 4R7 can be seen from
7R4 7 4 (mod 3) 7-4 =3 1 4-7 =3 (-1) 4 7 (mod 3) 4R7
(c)

Transitive: for any m,n,p , if mRn and nRp, then there exist r,s such that m-n =3r and n-p=3s. Hence m-p=(m-n)+(n-p)=3(r+s), i.e. mRp.
We thus conclude that R is an equivalence relation.

Equivalence Relations

Let set A={ 2, 4, 6, 8, 10 } and R be a binary relation on A defined by

(m,n) R iff m n (mod 4) m,n A .

Recall that m n (mod 4) is equivalent to saying 4 divides (m-n) or (m-n) is an integer multiple of 4. Thus it is easy to see

(m,n) m-n conclusion is multiple of 4?

(2,2) 2-2=0 (2,2) R yes, 0 is a multiple of 4

(2,4) 2-4=-2 (2,4) R no, -2 is not a multiple of 4

(2,6) 2-6=-4 (2,6) R -4: yes

(2,8) 2-8=-6 (2,8) R -6: no

(2,10) 2-10=-8 (2,10) R -8: yes

(4,2) 4-2=2 (4,2) R 2: no

(4,4) 4-4=0 (4,4) R 0: yes

(4,6) 4-6=-2 (4,6) R -2: no

which gives explicitly

R = { (2,2), (2,6), (2,10), (4,4), (4,8), (6,6), (6,10), (8,8), (10,10), (6,2), (10,2), (8,4), (10,6) } .

This relation R can be drawn as

and is obviously an equivalence relation (cf. examples in the previous lecture). Notice that there are 2 ''connnected'' components, one containing elements 4 and 8 and the other, elements 2, 6 and 10. Here the ''connection'' is made through certain walks along the directions of the arrows. These 2 components are just the 2 distinct equivalence classes under the equivalence relation R. Naturally we may use any element in an equivalence class to represent that particular class which basically contains all elements that are connected to the arbitrarily chosen representative element. Hence, in this case, we may choose 2 to represent the class {2,6,10}, written simply [2]={2,6,10}, and choose for instance 8 to represent the other class {4,8}, that is, [8]={4,8}. Since any member of an equivalence class can be used to represent that class, [6] and [10] will be representing exactly the same equivalence class as [2]. Hence

[2] [6] [10] = { 2, 6, 10 }, [4] [8] = { 4, 8 } .

are the 2 distinct equivalnce classes.

For the binary relation R defined in example 1, let us verify the results of the above lemma.
Solution Actually this is more like explanations.

(a)

(i) of the lemma in this case implies 2 [2]={2,6,10}, 6 [6], 10 [10], 4 [4] and 8 [8]={4,8} which is obviously true due to the explicit formula at the end of example 1.
(b)

(ii) in this case is the same as saying [2]=[6]=[10] and [4]=[8], which are already shown in example 1.
(c)

(iii) is consistent with the fact that any 2 of the equivalence classes [2], [4], [6], [8] and [10] are either disjoint (e.g. [2] and [4] have no elements in common) or exactly the same (e.g. [2]=[6]).
(d)

(iv) for the equivalence class {2,6,10} implies we can use either 2 or 6 or 10 to represent that same class, which is consistent with [2]=[6]=[10] observed in example 1. Similar observations can be made to the equivalence class {4,8}.
Show that the distinct equivalence classes in example 1 form a partition of the set A there.
Solution In example 1 we have shown that [2]={2,6,10} and [4]={4,8} are the only distinct equivalence classes. Since A in example 1 is given by A={2,4,6,8,10}, we can easily verify
(a): A = [2] [4] ; (b): [2] [4] = .
From the definition of the set partition (see the earlier lecture for sets) we conclude that { [2], [4] } is a partition of set A.

Let R be the equivalence relation defined on by R={(m,n): m,n , m n (mod 3)}, see examples in the previous lecture. Give the partition of in terms of the equivalence classes of R.
Solution

(a)

Pick any element in , say 0, we have
[0] ={ x : x R 0} = { ... , -6, -3, 0, 3, 6, ... } .
(b)

Pick any element in \ [0], say 1, we have
[1] ={x : x R 1} = { ... , -5, -2, 1, 4, 7, ... } .
(c)

Pick any element in \ ([0] [1]), say 5, we have
[5] ={ x : x R 5} = { ... , -4, -1, 2, 5, 8, ... } .
(d)

Since \ ([0] [1] [5]) = , all distinct equivalence classes are now exhausted. Hence the partition of under R is { [0], [1], [5] }.

Let A={ 0,1,2,3} and R={(0,1), (1,2), (2,3)}. From the graph for R

we see that a transitive closure, or closure w.r.t. the transitivity, can be obtained by adding arrows (0,2) due to (0,1) and (1,2), (1,3) due to (1,2) and (2,3), and (0,3) due to (0,1) and newly obtained (1,3). Hence the directed graph R' will be

i.e. R' ={(0,1), (1,2), (2,3), (0,2), (1,3), (0,3) }.
Note We may make an equivalence relation out of R as follows

Partial Order Relations

Let A={0,1,2} and R={ (0,0),(0,1),(0,2),(1,1), (1,2), (2,2)} and S={(0,0),(1,1),(2,2)} be 2 relations on A. Show

(i)

R is a partial order relation.
(ii)

S is an equivalence relation.

Solution We choose to use digraphs to make the explanations in this case.

(i)

The digraph for R on the right implies

Reflexive: loops on every vertex.

Transitive: if you can travel from vertex v to vertex w along consecutive arrows of same direction, then there is also a single arrow pointing from v to w.

Antisymmetric: no type of arrows.

(ii)

The digraph for S on the right is reflexive due to loops on every vertex, and is symmetric and transitive because no no-loop arrows exist.

Let A be the set of all subsets of set { a,b,c}. Show the ''subset'' relation on A, i.e. u,v A,
u v or uRv , iff u v ,
is a partial order relation. Find a minimal element and a greatest element.
Solution It is easy to verify that '' '' is a partial ordering. Since is a subset of any u A, i.e. u, we see is not only a minimal element, it is also a least element of A. Since for any u A one has u { a,b,c}, i.e. u { a,b,c}, we see that { a,b,c} is a greatest element of A.

The relation in example 2 can be drawn as

It is somewhat ''messy'' and some arrows can be derived from transitivity anyway. If we

omit all loops,

omit all arrows that can be inferred from transitivity,

draw arrows without heads,

understand that all arrows point upwards,
then the above graph simplifies to

This type of graph is called a Hasse diagram, it is often used to represent a partially ordered set.
Let A ={ 1,2,3,9,18} and for any a,b A,
a b iff a | b .
Draw the Hasse diagram of the relation.
Solution First it is easy to verify that the relation defined above is a partial ordering. The directed graph of relation is

and the Hasse diagram is
(a)

Let set A be given by
A={ 3, 4, 5, 6, 10, 12 }
and a binary relation R on A be defined by
(x, y) R iff x | y ,
i.e. (x,y) R if and only if x divides y. Give explicitly R in terms of its elements and draw the corresponding Hasse diagram.
(b)

Let a new binary relation R' on the set A given in (a) be defined by
(x, y) R' if and only if either x | y or y | x
and R'' be the transitive closure of R'. Use directed graphs to represent R, R' and R'' respectively. Which of the three relations R, R' and R'' is an equivalence relation? For the equivalence relation, give all the distinct equivalence classes.

Solution

(a)

Among all the elements of set A={ 3, 4, 5, 6, 10, 12 }, obviously 3 A, for instance, divides 3, 6 and 12. Hence by the definition of the relation R specified by the question we conclude (3,3), (3,6) and (3,12) are all elements of the relation R. Likewise we can show that (4,4), (4,12), (5,5), (5,10), (6,6), (6,12), (10,10), (12,12) are all elements of R. In fact we have
R = { (3,3), (3,6), (3,12), (4,4), (4,12), (5,5), (5,10), (6,6), (6,12), (10,10), (12,12) } .
Hence the digraph for R is

which induces the following Hasse diagram

(b)

The digraphs for R is already given in (a). As for R' we observe that, according to the definition of the relation R', if (x,y) (e.g. (3,6) ) is in R so will (y,x) (thus e.g. (6,3) ). Hence we can obtain R' by adding to R the symmetric pairs like (6,3), (12,3) etc. In terms of the digraph, such addition of elements is equivalent to drawing an opposite arrows to each existing (non-loop) arrows. The digraph of R' thus takes the following form

Since relation R'' is the transitive closure of R', we can derive R'' from R' by connecting 3 to 4 and 4 to 6 and connecting 4 to 3 and 6 to 4. We connect 3 to 4 via an direct arrow because we can travel from 3 to 12 and then from 12 to 4 all along the arrows, and we connect 4 to 3 because we can travel from 4 to 12 then to 3 all along the arrows too. Similar reasons are applicable for the arrows from 4 to 6 and 6 to 4. Hence R'' can be drawn as

Since there is no arrow from element 12 to element 3 in the digraph of R despite the existence of an arrow from 3 to 12, relation R is not symmetric hence is not an equivalence relation. Since relation R' is not transitive (because its transitive closure R'' is not the same as R' itself), relation R' is not an equivalence relation either. As for the relation R'' , it is obviously reflexive, symmetric and transitive. Hence R'' is an equivalence relation.
Since elements 3, 4, 6 and 12 are all related (connected) to each other through the arrows of the digraph R'' and none of these 4 elements are related to any other elements, they must form a single equivalence class. Hence we have
[3] = { 3, 4, 6, 12 } .
Likewise we can derive another equivalence class
[5] = { 5, 10 } .
Because any element of A is either in the equivalence class [3] or in the equivalence class [5], these two classes are all the distinct equivalence classes.

Recurrence Relations

For sequence {a_i}_i, the following formula
a_n = 7a_n-1 - 5a_n-2
is a recurrent relation valid for n 2. The elements in the sequence that are not related by the above formula are a₀ and a₁. Hence a₀ and a₁ can be determined by the initial conditions. Once the values of a₀ and a₁ are specified, the whole sequence {a_i}_{i 0} is completely specified by the recurrence relation.

Let a sequence {a_i}_i be determined by the recurrence relation

a_n = 3a_n-1 + 2a_n-2

(*)

and the initial conditions

a₀ = 1, a₁ = 2 .

(**)

Calculate a₄ recursively first. Then calculate a₄ again iteratively.

Solution Recursively we use (*) repeatedly (''topdown'') to decrease the indices involved until they all reach the initial ones. Hence

a₄ = 3a₃ + 2a₂ used (*) for n=4

= 3(3a₂ + 2a₁) + 2a₂ used (*) for n=3

= 11 a₂ + 6a₁

= 11 (3a₁ + 2a₀) + 6a₁

= 39a₁ + 22a₀

= 39 2 + 22 1 = 100 . used (**)

Iterately we use (*) repeatedly (''building-up'') to derive more and more known elements until the desired index is reached. Hence

a₀ = 1 ,

a₁ = 2 ,

a₂ = 3a₁ + 2a₀ = 8 ,

a₃ = 3a₂ + 2a₁ = 28 , used (*) for n=3

a₄ = 3a₃ + 2a₂ = 100 . used (*) for n=4

Let f(n) for n be given by the recurrence relation

f(n) = n f(n-1), n , n 1

f(0) = 1 (initial condition) .

Find the solution f(n).
Solution We first derive

f(n) = nf(n-1) if n 1

= n(n-1) f(n-2) if n 2

= n(n-1)(n-2)f(n-3) if n 3

= n! f(0) = n! .

Then we can show inductively f(n) = n! for n 0.

a_n = 5a_n-1 + 2a_n-2 + 3ⁿ, n 2, is a 2nd order linear constant coefficient recurrence relation and is nonhomogeneous. This is because we can equivalently rewrite it as
a_k+2 - 5a_k+1 - 2a_k = 3^k+2, k 0 .
In terms of the notation in (***) we have in this case m=2 and
c_m=c₂=1, c_m-1=c₁=-5, c_m-2=c₀=-2, g(n)=3ⁿ⁺² .
B_n+2 = sin (B_n+1), n -1, is not a linear recurrence relation because sin(B_n+1) is not a linear function of the dependent function B_n+1.
a_n+1 = na_n, n 0, is not a constant coefficient recurrence relation, though it is linear and homogeneous.
f(n+1) = 3f(n-5) + 4 f(n-2), n 5, is a homogeneous, 6th order, linear, constant coefficient recurrence relation. Observe that the difference of the highest index (n+1) and the lowest index (n-2) is exactly the order 6 of the recurrence relation.
a_n+1 = ra_n with constant r and n 0 induces a geometric sequence {a_n}_{n 0} with a_n = ra_n-1 = r(ra_n-2) =r²a_n-2 = = rⁿa₀, i.e. a_n = rⁿa₀ as its solution.

Recurrence relation a_n+2 + 3a_n+1 + 2a_n = 0, n 0, has the characteristic equation ² + 3 + 2 = 0.
Recurrence relation f(n+1) = 3f(n-2) + n² + 5, n 2 has the characteristic equation ³ - 3 = 0 because the recurrence relation can be written via n = k+2 as f(k+3) - 3f(k) = (k+2)² + 5. In fact we have in this case c_m c₃=1, c₂=0, c₁=0 and c₀=-3 in (***), and thus the characteristic equation c₃ ³+c₂ ²+c₁ +c₀=0 becomes simply ³-3=0.
Note An alternative way to construct the characteristic equation: Since the highest index in the recurrence relation is n+1 while the lowest index is n-2, their difference (n+1)-(n-2)=3 must be the order m, i.e. m=3. Likewise the characteristic equation can also be obtained in following way.

(i)

Remove the nonhomogeneous terms g(n). This way the recurrence relation f(n+1) = 3f(n-2) + n² + 5 becomes the reduced recurrence relation f(n+1) = 3f(n-2).
(ii)

Find the lowest index L. Here we thus have L=n-2.
(iii)

For each term in the reduced recurrence relation, if its index is K then replace the term by ^K-L. For the term f(n+1) we see K=n+1 hence K-L=(n+1)-(n-2)=3. Hence f(n+1) is to be replaced by ³. Likewise for the term f(n-2) on the r.h.s. we see K=n-2 hence K-L=0, implying that the term f(n-2) is to be replaced by ⁰ which is simply 1. This way the reduced recurrence relation is finally replaced into the characteristic equation ³=1.

Find the general solution of
a_n+2 - 5a_n+1 + 6a_n = 0 , n 0 .
Give also the particular solution satisfying a₀ = 0 and a₁=1.
Solution Since the associated characteristic equation is
² - 5 + 6 = 0
and has 2 distinct roots ₁ = 2 and ₂ = 3, the general solution for the recurrence relation, according to the theorem earlier on, thus read a_n = A₁2ⁿ + A₂3ⁿ, n 0, where A₁ and A₂ are 2 arbitrary constants. To find the particular solution, we need to determine A₁ and A₂ explicitly by the initial conditions a₀ = 0 and a₁ = 1. Hence we require

a₀ = A₁2⁰ + A₂3⁰ = 0

a₁ = A₁ 2¹ + A₂3¹ = 1

i.e.

A₁ + A₂ = 0

2A₁ + 3A₂ = 1

The solution of the above equations are found to be A₁ = -1 and A₂ = 1. Thus the particular solution is a_n = -2ⁿ + 3ⁿ for n 0.
Note It is often a good practice to check your answers, even if just partially. To check the above particular solution, we see

a₀ = -2⁰ + 3⁰ = 0

a₁ = - 2¹ + 3¹ = 1

a_n+2 - 5a_n+1 + 6a_n = (-2ⁿ⁺² + 3ⁿ⁺²) -5(-2ⁿ⁺¹ + 3ⁿ⁺¹) + 6 (-2ⁿ + 3ⁿ)

= -2ⁿ (2² - 5 2+6) + 3ⁿ (3² - 5 3 + 6) = 0 .

i.e. all conditions satisfied.

Solution of Linear Homogeneous Recurrence Relations

Find a particular solution of
f(n+2)+4f(n+1) +4f(n)=0, n 0
with initial conditions f(0)=1 and f(1)=2.
Solution For clarity we artificially split the solution procedure into 3 steps below.

(a)

The associated characteristic equation is
²+4 +4 =0 ,
which has a repeated root ₁=-2. In other words, all of its roots counting the multiplicity are
₁, ₁ (i.e. m₁=2, k=1) .
(b)

The general solution from the theorem in this lecture is thus
f(n) = (A_1,0+A_1,1n)ⁿ₁ = (B₀+B₁n)(-2)ⁿ ,
where B₀ and B₁, denoting A_1,0 and A_1,1 respectively, are arbitrary constants.
(c)

Constants B₀ and B₁ are to be determined from the initial conditions

f(0) = (B₀ +B₁ 0)(-2)⁰ =1

f(1) = (B₀+B₁ 1)(-2)¹ = 2

imply
B₀=1, -2(B₀+B₁)=2 .
They are thus B₀=1 and B₁=-2. Hence the requested particular solution is
f(n)=(1-2n)(-2)ⁿ , n 0 .
Find the general solution of
a_n+3-3a_n+2+4a_n=0 , n 0.
Solution The associated characteristic equation is
F() ³-3²+4 =0 .
Although there are formulas to give explicit roots for a 3rd order polynomial in terms of its coefficients, we are taking a shortcut here by guessing one root ₁=-1. We can check that ₁=-1 is indeed a root by verifying F(-1)=(-1)³-3(-1)²+4 =0. To find the remaining roots, we first factorise F( ) by performing a long division

which implies
³-3²+4 = ( +1)(² -4 +4)=( +1)( -2)² .
Therefore all the roots, counting the corresponding multicity, are
-1 , 2 , 2 ,
i.e. ₁ =-1, m₁=1 and ₂ =2, m₂ =2. Hence the general solution reads (with A=A_1,0, B=A_2,0, C=A_2,1)
a_n=A(-1)ⁿ+(B+Cn)2ⁿ , n 0 .
Find the particular solution of
u_n+3+3u_n+2+3u_n+1+u_n=0 , n 0
satisfying the initial conditions u₀=1, u₁=1 and u₂=-7.
Solution

(a)

The associated characteristic equation
³+3²+3 + 1 ( +1)³ =0
has roots ₁ =-1 with multiplicity 3, i.e. m₁=3.
(b)

The general solution then reads for arbitrary constants A, B and C
u_n =(A+Bn +Cn²)(-1)ⁿ , n 0 .
(c)

To determine A,B and C through the use of the initial conditions, we set n in the solution expression in (b) to 0, 1 and 2 respectively, and then observe

u₀ gives A = 1

u₁ gives (A+B+C)(-1) = 1

u₂ gives A+2B+4C = -7 .

The solution of these 3 equations,
A=1, B=0, C=-2.
finally produces the required particular solution
u_n =(1-2n²)(-1)ⁿ , n 0 .

Basics of Linear Nonhomogeneous Recurrence Relations

Find a particular solution of a_n+2-5a_n=2 3ⁿ for n 0.
Solution As the r.h.s. is 2 3ⁿ, we try the special solution in the form of a_n=C3ⁿ, with the constant C to be determined. The substitution of a_n=C3ⁿ into the recurrence relation thus gives

i.e. 4C=2 or C=1/2. Hence a_n= (3ⁿ)/2 for n 0 is a particular solution.
Find a particular solution of f_n+1-2f_n+3f_n-4=6n, n 4.
Solution As the r.h.s. is 6n, we try the similar form
f_n = An+B ,
with constants A and B to be determined. Hence f_n be a solution requires

6n = f_n+1 - 2f_n + 3f_{n - 4}

= (A(n+1)+B) - 2(An+B) + 3(A(n-4)+B)

= 2An + (2B-11A)

i.e.
2A = 6 , 2B - 11A = 0
which imples A = B = 33/2 .
Therefore our particular solution is f_n=3n + 33/2.

Find the particular solution of

a_n+3-7a_n+2+16a_n+1-12a_n=4ⁿn

with

a₀=-2 , a₁ =0 , a₂=5 .

Solution We first find the general solution u_n for the corresponding homogeneous problem. Then we look for a particular solution v_n for the nonhomogeneous problem without concerning ourselves with the initial conditions. Once these two are done, we obtain the general solution a_n=u_n+v_n for the nonhomogeneous recurrence relation, and we just need to use the initial conditions to determine the arbitrary constants in the general solution a_n so as to derive the final particular solution of our interest.

(a)

The associated characteristic equation

³ -7 ²+16 -12 =0

can be shown to admit the following roots

₁ =3,	(m₁=1, simple root)
₂ =2,	(m₂=2, double root) .

We can easily verify this by first guessing ₁ =3 is a root and then factorising ³-7 ²+16 - 12 into ( -3)( ² -4 +4) to find the remaining roots. If you are concerned that you might not be able to guess a first root like ₁ in similar circumstances, then you can leave your worry behind because we won't expect you to make such a guess.

The general solutions for the corresponding homogeneous problem thus reads
u_n=A3ⁿ+(B+C n)2ⁿ , n 0 .
That is, u_n solves a_n+3-7a_n+2+16a_n+1-12a_n=0.

(b)

Since the r.h.s. of the nonhomogeneous recurrence relation is 4ⁿ n, which fits into the description of 4ⁿ (1st order polynomial in n), we'll try a particular solution in a similar form, i.e.

v_n=4ⁿ(Dn+E) .

The substitution of v_n into the original recurrence relation then gives

4ⁿ n	=	v_n+3-7v_n+2+16v_n+1-12v_n
	=	4ⁿ⁺³(D(n+3)+E)-7 4ⁿ⁺²(D(n+2)+E)
		+ 16 4ⁿ⁺¹ (D(n+1)+E)-12 4ⁿ(Dn+E) ,

i.e.

n	=	64(Dn+3D+E)-112(Dn+2D+E)
		+ 64(Dn+D+E)-12(Dn+E)
	=	4Dn+4E+32D .

Hence we have

4D=1 , 4E+32D=0 D=1/4 , E=-2

and consequently v_n=4ⁿ(n/4 - 2).

(c)

The general solution for the nonhomogeneous problem is then given by a_n=u_n+v_n, i.e.

a_n =4ⁿ(n/4 - 2) + A3ⁿ+(B+Cn)2ⁿ , n 0 .

(d)

We now determine A, B, C by the initial conditions and the use of the solution expression in (b)

Initial Conditions

Induced Equations

Solutions

a₀ = -2

a₁ = 0

a₂ = 5

A+B-2	=	-2
3A+2B+2C-24	=	5
9A+4B+8C	=	29

A	=	1
B	=	-1
C	=	3

Finally the particular solution satisfying both the nonhomogeneous recurrence relations and the initial conditions is given by

a_n=4ⁿ(n/4 - 2) + 3ⁿ + (3n-1)2ⁿ , n 0 .

Solutions of Linear Nonhomogeneous Recurrence Relations

Solve a_n+2+a_n+1-6a_n=2ⁿ for n 0.
Solution First we observe that the homogeneous problem
u_n+2 + u_n+1 -6u_n=0
has the general solution u_n=A 2ⁿ +B(-3)ⁿ for n 0 because the associated characteristic equation ²+ -6 =0 has 2 distinct roots ₁=2 and ₂=-3. Since the r.h.s. of the nonhomogeneous recurrence relation is 2ⁿ, if we formally follow the strategy in the previous lecture we would try v_n=C2ⁿ for a particular solution. But there is a difficulty: C2ⁿ fits into the format of u_n which is a solution of the homogeneous problem. In other words it can't be a particular solution of the nonhomogeneous problem. This is really because ''2'' happens to be one of the 2 roots ₁ and ₂. However, we suspect that a particular solution would still have to have 2ⁿ as a factor, so we try v_n=Cn2ⁿ. Substituting it to v_n+2+v_n+1 -6v_n=2ⁿ, we obtain
C(n+2)2ⁿ⁺²+C(n+1)2ⁿ⁺¹-6Cn2ⁿ = 2ⁿ ,
i.e. 10C2ⁿ=2ⁿ or C=1/10. Hence a particular solution is v_n=(n/10)2ⁿ and the general solution of our nonhomogeneous recurrence relation is
a_n=A2ⁿ+B(-3)ⁿ + 2ⁿ , n 0 .

Find the general solution of f(n+2)-6f(n+1)+9f(n)=5 3ⁿ, n 0.
Solution Let f(n)=u_n+v_n, with u_n being the general solution of the homogeneous problem and v_n a particular solution.

(a)

Find u_n: The associated characteristic equation ² -6 + 9 =0 has a repeated root =3 with multiplicity 2. Hence the general solution of the homogeneous problem
u_n+2-6u_n+1+9u_n=0 , n 0
is u_n = (A+Bn)3ⁿ.
(b)

Find v_n: Since the r.h.s. of the recurrence relation, the nonhomogeneous part, is 5 3ⁿ and 3 is a root of multiplicity 2 of the characteristic equation (i.e. =3, k=0, M=2), we try due to (***) v_n =B₀ ⁿ n^M Cn²3ⁿ: we just need to observe that C3ⁿ is of the form 5 3ⁿ and that the extra factor n² is due to =3 being a double root of the characteristic equation. Thus

5 3ⁿ = v_n+2-6v_n+1+9v_n

= C(n+2)²3ⁿ⁺²-6C(n+1)²3ⁿ⁺¹+9Cn²3ⁿ

= 18C3ⁿ .

Hence C=5/18 and v_n =(5/18)n²3ⁿ. Therefore our general solution reads
f(n) = A + Bn + n² 3ⁿ , n 0 .

Find the particular solution of

a_n+4-5a_n+3+9a_n+2-7a_n+1 +2a_n=3 , n 0

satisfying the initial conditions a₀ = 2, a₁ = -1/2, a₂ = -5, a₃ = -31/2 .

Solution We first find the general solution u_n for the homogeneous problem. We then find a particular solution v_n for the nonhomogeneous problem without considering the initial conditions. Then a_n=u_n+v_n would be the general solution of the nonhomogeneous problem. We finally make use of the initial conditions to determine the arbitrary constants in the general solution so as to arrive at our required particular solution.

(a)

Find u_n: Since the associated characteristic equation

⁴-5 ³ +9 ² -7 + 2 =0

has the sum of all the coefficients being zero, i.e. 1-5+9-7+2=0, it must have a root =1. After factorising out ( -1) via ⁴-5 ³+9 ²-7 + 2 = ( -1)( ³-4 ²+5 -2), the rest of the roots will come from ³-4 ²+5 -2 =0. Notice that ³-4 ²+5 -2=0 can again be factorised by a factor ( -1) because 1-4+5-2=0. This way we can derive in the end that the roots are

₁ =1	with multiplicity	m₁=3 , and
₂=2	with multiplicity	m₂=1 .

Thus the general solutions for the homogeneous problem is

u_n = (A+Bn+Cn²)1ⁿ+D2ⁿ ,

or simply u_n=A+Bn+Cn²+D2ⁿ because 1ⁿ 1.

(b)

Find v_n: Notice that the nonhomogeneous part is a constant 3 which can be written as 3 1ⁿ when cast into the form of (**), and that 1 is in fact a root of multiplicity 3. In other words, we have in (***) =1, k=0 and M=3. Hence we try a particular solution v_n=En³ 1ⁿ =En³. The substitution of v_n into the nonhomogeneous recurrence equations then gives, using a formula in the subsection Binomial Expansions in the Preliminary Mathematics at the beginning of these notes,

3	=	v_n+4-5v_n+3+9v_n+2-7v_n+1+2v_n
	=	E(n+4)³-5E(n+3)³+9E(n+2)³-7E(n+1)³+2En³
	=	E(n³ + 3n² 4+3n 4²+4³) -5E(n³ + 3n² 3+3n 3²+3³)
		+ 9E(n³ + 3n² 2+3n 2²+2³) -7E(n³ + 3n² 1+3n 1²+1³) + 2En³
	=	-6E ,

i.e. E= -1/2. Hence v_n= -n³/2.

Note Should you find it very tedious to perform the expansions in the above, you could just substitute, say, n=0 into
3 = E(n+4)³-5E(n+3)³+9E(n+2)³-7E(n+1)³+2En³
to obtain readily 3=E4³-5E3³+9E2³-7E=-6E. Incidentally you don't have to substitute n=0; you can in fact substitute any value for n because the equation is valid for all n. Obviously this alternative technique also applys even if there are more than 1 unknowns in the equation; we just need to substitute sufficiently many distinct values for n to collect enough equations to determine the unknowns. The drawback of this technique is that you have to make sure that the form you have proposed for v_n is absolutely correct through the use of the proper theory, otherwise an error in the form for v_n will go undetected in this alternative approach.

(c)

The general solution of the nonhomogenous problem thus read

a_n = u_n + v_n = A + Bn + Cn² + D2ⁿ - n³/2.

(d)

We now ask the solution in (c) to comply with the initial conditions.

Initial Conditions

Induced Equations

Solutions

a₀ = 2

a₁ = -1/2

a₂ = -5

a₃ = -31/2

A+D = 2

A+B+C+2D = 0

A+2B+4C+4D = -1

A+3B+9C+8D = -2

A = 3

B = -2

C = 1

D = -1

Hence our required particular solution takes the following final form

a_n = 3 - 2n + n² - n³/2 - 2ⁿ, n 0 .

Find the general solution of a_n+1-a_n=n2ⁿ+1 for n 0.
Solution

(a)

The general solution for homogeneous problem is u_n=A because the only root of the characteristic equation is ₁=1.
(b)

Since n2ⁿ+1 = 2ⁿ n +1ⁿ is of the form ₁ⁿ(b₁n+b₀)+ ⁿ₂ c₀ and ₂=1 is a simple root of the characteristic equation, we try the similar form v_n = 2ⁿ(B+Cn) + Dn for a particular solution. Substiting v_n into the recurrence relation, we have

n2ⁿ+1 = v_n+1-v_n = 2ⁿ⁺¹(B+C(n+1)) + D(n+1) - 2ⁿ(B+Cn) - Dn

= 2ⁿ(Cn+B+2C) + D ,

i.e.
2ⁿ ( (C-1)n + (B+2C) ) + (D-1) = 0 .
In order the above equation be identically 0 for all n 0, we require all its coefficients to be 0, i.e.
C-1=0 , B+2C=0 , D-1=0 .
Hence B=-2, C=1 and D=1 and the particular solution v_n =2ⁿ(n-2)+n.
(c)

The general solution is u_n+v_n and thus reads
a_n = 2ⁿ(n-2)+n+A , n 0 .
Let m and S(n)= i^m for n . Convert the problem of finding S(n) to a problem of solving a recurrence relation.
Solution We first observe
S(n+1)= (n+1)^m + i^m = S(n) + (n+1)^m .
Since the general solution will contain just 1 arbitrary constant, 1 initial condition should suffice. Hence S(n) is the solution of

S(n+1)-S(n) = (n+1)^m, n

S(0) = 0 .

Preorder:	a, b, d, c, e, f, g
Inorder:	d, b, a, f, e, g, c
Postorder:	d, b, f, g, e, c, a

(1)	q r	premise
	r	premise
	q	by modus tollens
(2)	p q	premise
	q	by (1)
	p	by disjunctive syllogism
(3)	q u s	premise
	q	by (1)
	u s	by modus ponens
(4)	u s	by (3)
	s	by conjunctive simplification
(5)	p	by (2)
	s	by (4)
	p s	by conjunctive addition
(6)	p s t	premise
	p s	by (5)
	t	by modus ponens

(a)	r, q r, q	(modus tollens)
(b)	q, p q, p	(disjunctive syllogism)
(c)	q, q u s, u s	(modus ponens)
(d)	u s, s	(conjunctive simplification)
(e)	p, s, p s	(conjunctive addition)
(f)	p s, p s t, t	(modus ponens)

(a)	S_A S_D	S_A true implies S_Dtrue, i.e. (S_A, S_D) (from (3))
(b)	S_A S_B S_C S_D	S_A true implies S_B, S_C and S_Dall false (from (4))
(c)	S_B S_C S_D S_D	conjunctive simplification (direct)
(d)	S_A S_D	hypothetical syllogism (from (b), (c))
(e)	S_D S_A	modus tollens (from (a))
(f)	S_A S_A	hypothetical syllogism (from (d), (e))

original:	x , (x > 3) (x² > 4)	(a)
contrapositive:	x , (x² 4) (x 3)	(b)
converse:	x , (x² > 4) (x > 3)	(c)
inverse:	x , (x 3) (x² 4)	(d)

(a)		only 1 empty set
(b)		the only subset with all elements in it is the set itself
(c)		if r 1, n>1}

A 7F₁₆	=	A 16²+7 16¹ +F 16⁰
	=	10 16²+7 16 + 15 1 = 2687 .

edge e		endpoints (e)

e₁		{v₁}
e₂		{v₁, v₂}
e₃		{v₂, v₃}
e₄		{v₂, v₃}
e₅		{v₂, v₃}

edge e		endpoints pair (e)

e₁		(v₁, v₁)
e₂		(v₁, v₂)
e₃		(v₃, v₂)
e₄		(v₂, v₃)

V(G₁)	=	{v₁, v₂, v₃} ,	E(G₁)	=	{e₁, e₂} ;
V(G₂)	=	{ v₄} ,	E(G₂)	=	(the empty set) ;
V(G₃)	=	{ v₄, v₅, v₆} ,	E(G₃)	=	{e₃, e₄, e₄} .

route		total distance

A B C D A		30 + 30 + 25 + 40 = 125
A B D C A		140
A C B D A		155
A C D B A		140
A D B C A		155
A D C B A		125

e₁ {v₁,v₂}		f₂ {w₁,w₂} = {g(v₁), g(v₂)}
e₂ {v₂, v₄}		f₁ {w₁,w₃} = {g(v₂), g(v₄)}
e₃ {v₂,v₃}		f₄ {w₁,w₄} = {g(v₂), g(v₃)}
e₄ {v₁,v₄}		f₃ {w₂,w₃} = {g(v₁), g(v₄)}
e₅ {v₃,v₄}		f₅ {w₃,w₄}= {g(v₃), g(v₄)} ,

e₁={v₂,v₃} , w(e₁)=1 ;	e₆={v₅,v₇} , w(e₆)=4 ;
e₂={v₅,v₆} , w(e₂)=2 ;	e₇={v₁,v₂} , w(e₇)=4 ;
e₃={v₆,v₇} , w(e₃)=3 ;	e₈={v₁,v₄} , w(e₈)=5 ;
e₄={v₃,v₄} , w(e₄)=3 ;	e₉={v₃,v₅} , w(e₉)=5 ;
e₅={v₂,v₄} , w(e₅)=4 ;	e₁₀={v₃,v₇} , w(e₁₀)=7 .

3 R 5		(3, 5) R	3 is related to 5 by R		3 5 ,
3 2		(3, 2) R	3 is not related to 2 by R		3 2 .

(m,n)	m-n	conclusion	is multiple of 4?

(2,2)	2-2=0	(2,2) R	yes, 0 is a multiple of 4
(2,4)	2-4=-2	(2,4) R	no, -2 is not a multiple of 4
(2,6)	2-6=-4	(2,6) R	-4: yes
(2,8)	2-8=-6	(2,8) R	-6: no
(2,10)	2-10=-8	(2,10) R	-8: yes
(4,2)	4-2=2	(4,2) R	2: no
(4,4)	4-4=0	(4,4) R	0: yes
(4,6)	4-6=-2	(4,6) R	-2: no

a₄	=	3a₃ + 2a₂	used () for n=4*
	=	3(3a₂ + 2a₁) + 2a₂	used () for n=3*
	=	11 a₂ + 6a₁
	=	11 (3a₁ + 2a₀) + 6a₁
	=	39a₁ + 22a₀
	=	39 2 + 22 1 = 100 .	used (**)

a₀	=	1 ,
a₁	=	2 ,
a₂	=	3a₁ + 2a₀ = 8 ,
a₃	=	3a₂ + 2a₁ = 28 ,	used () for n=3*
a₄	=	3a₃ + 2a₂ = 100 .	used () for n=4*

f(n)	=	nf(n-1)	if n 1
	=	n(n-1) f(n-2)	if n 2
	=	n(n-1)(n-2)f(n-3)	if n 3
	=	n! f(0) = n! .

a_n+2 - 5a_n+1 + 6a_n	=	(-2ⁿ⁺² + 3ⁿ⁺²) -5(-2ⁿ⁺¹ + 3ⁿ⁺¹) + 6 (-2ⁿ + 3ⁿ)
	=	-2ⁿ (2² - 5 2+6) + 3ⁿ (3² - 5 3 + 6) = 0 .

6n	=	f_n+1 - 2f_n + 3f_{n - 4}
	=	(A(n+1)+B) - 2(An+B) + 3(A(n-4)+B)
	=	2An + (2B-11A)

5 3ⁿ	=	v_n+2-6v_n+1+9v_n
	=	C(n+2)²3ⁿ⁺²-6C(n+1)²3ⁿ⁺¹+9Cn²3ⁿ
	=	18C3ⁿ .

n2ⁿ+1 = v_n+1-v_n	=	2ⁿ⁺¹(B+C(n+1)) + D(n+1) - 2ⁿ(B+Cn) - Dn
	=	2ⁿ(Cn+B+2C) + D ,