Chapter 1
Revision of Some Basic
Maths Concepts
1
Course Outline
• Mathematical Foundations
– Log function
– Exponentionals
• Proof By Induction
– Sum of squares
– Fibonacci numbers
• Proof By Counter Example
• Proof By Contradiction
• Recursion
• Recursion vs Iteration 2
Mathematical Foundations
– Needed for the analysis of algorithms complexities.
Series and summation:
(arithmetic series): 1 + 2 + 3 + ……. N = N(N+1)/2
(geometric series):
1 + r+ r2 + r3 +………rN-1 = (1- rN)/(1-r)
1/(1-r), r < 1, large N
Sum of squares:
1 + 22 + 32 +………N2 = N(N + 1)(2N + 1)/6
3
Properties of a log Function
logxa = b iff xb = a
(we will use base 2 mostly, but may use other bases
occasionally)
Will encounter log functions again and again! log n bits
needed to encode n messages.
log (ab ) = log a + log b logba = logca/ logcb
log (a/b ) = log a - log b alog n = nlog a
log ab = b log a
4
amn = (am )n = (an)m
am+n = am an
(2n)0.5 (n/e)n n (2n)0.5 (n/e)n + (1/12n)
5
Proof By Induction
• Prove that a property holds for input size 1
(base case)
• Assume that the property holds for input size
1,…n.
• Show that the property holds for input size
n+1.
Then, the property holds for all input sizes, n.
6
Prove that the sum of 1+2+…..+n = n(n+1)/2
1(1+1)/2 = 1
Thus the property holds for n = 1 (base case)
Assume that the property holds for n=1,…,m,
Thus 1 + 2 +…..+m = m(m+1)/2
We will show that the property holds for n = m + 1, that is
1 + 2 + ….. + m + m + 1 = (m+1)(m+2)/2
This means that the property holds for n=2 since we have
shown it for n=1
Again this means that the property holds for n=3 and then
7
for n=4 and so on.
Now we show that the property holds for
n = m + 1, that is
1 + 2 + ….. + m + m + 1 = (m+1)(m+2)/2
Assuming that 1 + 2 +…..+m = m(m+1)/2
1 + 2 +…..+m + (m+1) = m(m+1)/2 + (m+1)
= (m+1)(m/2 + 1)
= (m+1)(m+2)/2
8
Sum of Squares
Now we show that
1 + 22 + 32 +………n2 = n(n + 1)(2n + 1)/6
1(1+1)(2+1)/6 = 1
Thus the property holds for n = 1 (base case)
Assume that the property holds for n=1,..m, thus
1 + 22 + 32 +………m2 = m(m + 1)(2m + 1)/6
and show the property for m + 1, that is show that
1 + 22 + 32 +………m2 +(m+1)2 = (m+1)(m + 2)(2m +3)/6
9
1 + 22 + 32 +………m2 + (m+1)2
= m(m + 1)(2m + 1)/6 + (m+1)2
= (m+1)[m(2m+1)/6 +m+1]
= (m+1)[2m2 + m + 6m +6]/6
= (m+1)(m + 2)(2m + 3)/6
10
Fibonacci Numbers
Sequence of numbers, F0 F1 , F2 , F3 ,…….
F0 = 1, F1 = 1
Fi = Fi-1 + Fi-2
F2 = 2
F3 = 3
F4 = 5
F5 = 8 11
Prove that Fn+1 < (5/3)n+1
Base case: F2 = 2 < (5/3 )2
Let the property hold for 1,…k
Thus Fk+1 < (5/3)k+1 ? Fk < (5/3)k
Fk+2 = Fk + Fk+1 ,
< (5/3)k + (5/3)k+1
= (5/3)k (5/3 + 1)
< (5/3)k (5/3)2
12
Proof By Counter Example
• Want to prove something is not true!
• Give an example to show that it does not
hold!
• Example: Is FN N2 ?
No, F11 = 144 > 121!
• However, if you were to show that FN N2
then you would need to show for all N, and
not just one number. 13
Proof By Contradiction
• Suppose you want to prove something.
• Assume that what you want to prove does not
hold.
• Then show that you arrive at an impossibility.
• Example: The number of prime numbers is not
finite!
14
Suppose the number of primes is finite, k.
The primes are P1, P2 , … , Pk
The largest prime is Pk
Consider the number N = 1 * P1 * P2 * ….. * Pk
N is larger than Pk , thus N is not prime (hypothesis)
So N must be the product of some primes.
However, none of the primes P1, P2 , … , Pk divide
N exactly. So N is not a product of primes.
(contradiction) 15
Recursion
• A subroutine which calls itself, with different
parameters.
• Need to evaluate factorial(n)
factorial(n) = n.(n-1)…2.1
= n factorial(n-1)
• Suppose routine factorial(p) can find factorial of
p for all p < m. Then factorial(m+1) can be
calculated as follows:
factorial(m+1) = (m+1) factorial(m)
Anything missing?
16
Factorial(m)
{
If m = 1 Factorial(m) = 1
else Factorial(m) = m Factorial(m-1);
}
Basic rules of Recursion :
• There should be a base case for which the subroutine
does not call itself.
• For the general case: the subroutine does some
operations, calls itself, gets result and does some
operations with the result
• The subroutine should progressively move towards the
17
base case.
Printing numbers digit by digit
• We wish to print out a positive integer, n. Our routine
will have the heading printOut(n). Assume that the
only I/O routine available printDigit(m) will take a
single-digit number and outputs it.
void printOut( int n ) // Print nonnegative n
{
if( n >= 10 )
printOut( n / 10 );
printDigit( n % 10 );
}
See proof of algorithm correctness in the textbook. 18
Recursion Versus Iteration
• Factorial of n (n>0) can be iteratively computed
as follows:
factorial = 1
for j=1 to n
factorial factorial j
• Compare to the recursive version.
• In general, iteration is more efficient than
recursion because of maintenance of state
information. 19
Towers of Hanoi
• Source peg (A), Destination peg (C), Auxiliary
peg (B)
• At the start, k disks are on the source peg.
• Need to move all k disks to the destination peg
using the auxiliary peg, without ever keeping a
bigger disk on a smaller disk. 20
• We know how to move 1 disk from source to
destination.
• For two disks, move the top one to the auxiliary,
bottom one to the destination, then the first to the
destination.
• For three disks,
– move top two disks from source to auxiliary, using
destination.
– Then move the bottom one from the source to the
destination.
– Finally move the two disks from auxiliary to
21
destination using source.
• We know how to solve this for k=1
• Suppose we know how to solve this for k-1
disks.
• We will first move top k-1 disks from source to
auxiliary, using destination.
• Will move the bottom one from the source to
the destination.
• Will move the k-1 disks from auxiliary to
destination using source.
22
towerOfHanoi(k, source, auxiliary, destination)
{
If k=1 move disk from source to destination; (base
case)
else
{
towerOfHanoi(top k-1, source, destination,
auxiliary);
Move the kth disk from source to destination;
towerOfHanoi(k-1, auxiliary, source,
destination);
}
} 23
