COMP2101 Discrete Mathematics

Binomial Theorem and Master Theorem

1. Expand (2c 3d)
5
using the Binomial Theorem.

Solution


Required (2c 3d)
5

Let a = 2c, b = -3d, n = 5


= C(5,0)a
5
b
0
+ C(5,1)a
5-1
b
1
+ C(5,2)a
5-2
b
2
+ C(5,3)a
5-3
b
3
+ C(5,4)a
5-4
b
4
+ C(5,5)a
5-5
b
5

= 1a
5
b
0
+ 5a
4
b
1
+ 10a
3
b
2
+ 10a
2
b
3
+ 5a
1
b
4
+ 1a
0
b
5

By Substitution
= (2c)
5
(-3d)
0
+ 5(2c)
4
(-3d)
1
+ 10(2c)
3
(-3d)
2
+ 10(2c)
2
(-3d)
3
+ 5(2c)
1
(-3d)
4
+ (2c)
0
(-3d)
5

= (32c
5
) + 5(-48c
4
d) + 10(72c
3
d
2
) + 10(-108c
2
d
3
) + 5(162cd
4
) + (-243d
5
)
= 32c
5
240c
4
d + 720c
3
d
2
1080c
2
d
3
+ 810cd
4
243d
5


2. Use the Binomial Theorem to show that


Solution
We know that

We attempt to eliminate a
n-k
and to substitute values for the proof
Let a = 1, b = 2



As 1
x
= 1 for x Z



3. What is the row of Pascals triangle containing the binomial coefficients

Solution

= +
n
k
k k n n
b a k n C b a
0
) , ( ) (

=
5
0
5 5
) 3 ( ) 2 )( , 5 ( ) 3 2 (
k
k k
d c k C d c

=
=
n
k
n k
k n C
0
3 ) , ( 2

= +
n
k
k k n n
b a k n C b a
0
) , ( ) (
n
n
k
k
n
n
k
k k n
n
n
k
k k n
k n C
k n C
b a b a k n C
3 ) , ( 2
) 2 1 ( 2 1 ) , (
) ( ) , (
0
0
0
=
+ =
+ =

=
=

9 0 ,
9
s s
|
|
.
|

\
|
k
k
,
9
9
,
8
9
,
7
9
,
6
9
,
5
9
,
4
9
,
3
9
,
2
9
,
1
9
,
0
9
|
|
.
|

\
|
|
|
.
|

\
|
|
|
.
|

\
|
|
|
.
|

\
|
|
|
.
|

\
|
|
|
.
|

\
|
|
|
.
|

\
|
|
|
.
|

\
|
|
|
.
|

\
|
|
|
.
|

\
|
i.e. 1 9 36 84 126 126 84 36 9 1
OR
Using Pascals Theorem
Pascals Identity states

or C(n+1,k) = C(n,k-1) + C(n,k) for 1 k n
Therefore
C(8+1,1) = C(8,1-1) + C(8,1) = 1+8 = 9
C(8+1,2) = C(8,2-1) + C(8,2) = 8+28 = 36
C(8+1,3) = C(8,3-1) + C(8,3) = 28+56 = 84
C(8+1,4) = C(8,4-1) + C(8,4) = 56+70 = 126
C(8+1,5) = C(8,5-1) + C(8,5) = 70+56 = 126
C(8+1,6) = C(8,6-1) + C(8,6) = 56+28 = 84
C(8+1,7) = C(8,7-1) + C(8,7) = 28+8 = 36
C(8+1,8) = C(8,8-1) + C(8,8) = 8+1 = 9

i.e. 1 9 36 84 126 126 84 36 9 1


4. Let a,b,c be integers such that a 1, b > 1 and c > 0. Let f: N R be functions
where N is the set of Natural numbers and R is the set of Real numbers such that
f(n) = cf(n/b) + a
b
c
By using the principles of Recurrence Relation, find a general formula for f(n)

Solution
f(n) = c f(n/b) + a
b
c .....1

Using equ. 1, As f(n/b) = c f(n/b / b) + a
b
c
= c f(n/b
2
) + a
b
c
Substituting for f(n/b)
= c [ c f(n/b
2
) + a
b
c ] + a
b
c

= c
2
f(n/b
2
) + a
b
c(c + 1) .....2

Using equ. 1, As f(n/b
2
) = c f(n/b
2
/ b) + a
b
c
= c f(n/b
3
) + a
b
c
Substituting for f(n/b
2
)
= c
2
[ c f(n/b
3
) + a
b
c ] + a
b
c(c + 1)

= c
3
f(n/b
3
) + a
b
c (c
2
+ c + 1) .....3

Using equ. 1, As f(n/b
3
) = c f(n/b
3
/ b) + a
b
c
= c f(n/b
4
) + a
b
c
|
|
.
|

\
|
+
|
|
.
|

\
|

=
|
|
.
|

\
|
+
k
n
k
n
k
n
1
1
Substituting for f(n/b
3
)
= c
3
[ c f(n/b
4
) + a
b
c ] + a
b
c (c
2
+ c + 1)

= c
4
f(n/b
4
) + a
b
c (c
3
+ c
2
+ c + 1) .....4

= c
4
f(n/b
4
) + a
b
(c
4
+ c
3
+ c
2
+ c) .....4

= ......

Given that k is a positive integer greater than 1
f(n) = c
k
f(n/b
k
) + a
b

=
k
i
i
c
1

OR
f(n) = c
k
f(n/b
k
) + a
b
c

=
1
0
k
i
i
c




5. For each of the following recurrences,
- Give an expression for the runtime T(n) if the recurrence can be solved with the Master
Theorem.
- Otherwise, indicate that the Master Theorem does not apply and state why the problem
cannot be solved by the Master Theorem.
In all cases, assume that T(n) = 1 for n 1.

(a) T(n) = 4T(n/2) + n

Solution
Consider the recurrence:
T(n) = aT(n/b) + f(n)
where a, b are constants and f(n) is an arbitrary function in n,
let the critical exponent, E = log
b
a

Given
T(n) = 4T(n/2) + n
The critical exponent, E
E = log
2
4 = 2
By examining the overhead function f(n) with n
E

f(n) = n and n
E
= n
2

Therefore
f(n) = n = O(n
E
) = O(n
2
)
We find that allows f(n) = O(n
E-
)
For definiteness, let = 0.5
E - = 2 - 0.5 = 1.5
It is clear that
f(n) = n = O(n
E-
) = O(n
1.5
)

As for some > 0, and f(n) = O(n
E-
)
Master Theorem Case 1 holds

We conclude that
the solution for the equation
T(n) = 4T(n/2) + n
is
T(n) = (n
E
) or T(n) = (n
log
b
a
)

T(n) = (n
log
2
4
)

T(n) = (n
2
)



(b) T(n) = 2
n
T(n/2) + n
n


Solution
T(n) = 2
n
T(n/2) + n
n
Does not apply
(a is not constant)



(c) T(n) = 2T(n/2) + n/log n

Solution
T(n) = 2T(n/2)+ n/log n Does not apply
(non-polynomial difference between f(n) and n
log
b
a
)



(d) f(n) = 3f(n/3) + n/2

Solution
Consider the recurrence:
f(n) = af(n/b) + g(n)
where a, b are constants and g(n) is an arbitrary function in n,
let the critical exponent, E = log
b
a

Given
f(n) = 3f(n/3) + n/2
The critical exponent, E
E = log
3
3 = 1
By examining the overhead function g(n) with n
E

g(n) = n/2 = n and n
E
= n
1

Therefore
g(n) = n = O(n
E
) = O(n)
and
g(n) = n = (n
E
) = (n)
We have
g(n) = (n
E
)

As g(n) = (n
E
)
Master Theorem Case 2 holds

We conclude that
the solution for the equation
f(n) = 3f(n/3) + n/2
is
f(n) = (g(n) log

n) or f(n) = (n
E
log

n) or f(n) = (n
log
b
a
log

n)

f(n) = (n log n)



(e) f(n) = 64f(n/8) n
2
log n

Solution
f(n) = 64f(n/8) n
2
log n Does not apply
(g(n) is not positive)



(f) f(n) = 16f(n/4) + n!

Solution
Consider the recurrence:
f(n) = af(n/b) + g(n)
where a, b are constants and f(n) is an arbitrary function in n,
let the critical exponent, E = log
b
a

Given
f(n) = 16f(n/4) + n!
The critical exponent, E
E = log
4
16 = 2
By examining the overhead function g(n) with n
E

g(n) = n! and n
E
= n
2

Therefore
g(n) = n! = (n
E
) = (n
2
)

Furthermore, we find that allows g(n) = O(n
E+
)
For definiteness, let = 0.5
E + = 2 + 0.5 = 2.5
It is clear that
g(n) = n! = (n
E+
) = (n
2.5
)

g(n) = (n
E+
),
As for some > 0, and g(n) = (n
E+
), but for some > 0, and g(n) = O(n
E+
)
Master Theorem Case 3 holds

We conclude that
the solution for the equation
f(n) = 16f(n/4) + n!
is
f(n) = (g(n))

f(n) = (n!)