Pascal’s Triangle You may have learned that the number of ways you can choose k different
items from a set of n items is often labelled nCk or, equivalently, Cn
k
or
n
k
.
In this question, you will prove some facts about Pascal’s triangle.
(See https://en.wikipedia.org/wiki/Pascal%27s_triangle for interesting background information.)
The only facts you may use in your proofs in this question are:
• ?k ? N, ?n ? Z
+, n = k ?
n – 1
k – 1
+
n – 1
k
=
n
k
(called Pascal’s identity)
• ?n ? N,
n
n
= 1.
• ?k, n ? Z, k < 0 ? k > n ?
n
k
= 0.
You may not use the formula
n
k
=
n!
(n – k)!k!
or any other external results that you may know.
(a) [3 marks] Prove using induction that the sum of the values in the row with index n of Pascal’s
triangle is 2n
. The first row has index 0. That is, prove:
?n ? N,
Xn
k=0
n
k
= 2n
.
(b) [3 marks] Prove using induction on n that:
?k, n ? N, n = k ?
Xn
i=k
i
k
=
n + 1
k + 1
.
Page 2/5
CSC165H1, Fall 2018 Problem Set 3
2.Binary Representation of Fractions In this question, we use the notation (x)2 to refer to
a binary representation of a number x. For example, 9 = (1001)2, where 9 is the decimal representation
of the number nine.
Let Q
(0,1) =
nm
n
| m, n ? Z
+ ? n > mo
be the set of all rational numbers between 0 and 1 (exclusive).
For any x ? Q
(0,1), its binary representation is of the form:
x = (0.b1b2b3 . . .)2
where ?i ? Z
+, bi ? {0, 1}, and x =
X8
i=1
bi
2
i
. The binary digits bi are called bits.
Note that when there are trailing zeros, one may choose not to write them. For example, 3
4
= (0.11)2.
Some rational numbers, however, may not have a finite binary representation. You are familiar with this
situation from decimal, where 1
6
= 0.16666… does not terminate.
We say that x = (0.b1b2b3 . . .)2 has a finite binary representation if and only if ?n ? Z
+, x = (0.b1b2b3 . . . bn)2,
where bi ? {0, 1}.
(a) [1 mark] What is the binary representation of 21
32
? Give the answer that uses the fewest bits. (Hint:
it has a finite binary representation.)
(b) [4 marks] Prove that 1
10
does not have a finite binary representation.
(c) [4 marks] Prove that for all x ? Q
(0,1), x has a finite binary representation if and only if x =
p
2
q
for
some positive integers p and q.
Page 3/5
CSC165H1, Fall 2018 Problem Set 3
3. [8 marks] Definitions of Asymptotic Notation. Using only the formal definitions of O, ? and T,
prove the following statements. You may not use other relationships that you have learned about O, ?
and T.
(a) [2 marks] 17n
4 – 21n
3 + 6n – 135 ? T(n
4
)
(b) [2 marks] 2
n – n
2 ? ?(2n
)
(c) [2 marks] log2 n – log10n ? ?(log12n)
(d) [2 marks] ?k ? N, nn
6? O(k
n
)
Page 4/5
CSC165H1, Fall 2018 Problem Set 3
4. Properties of Asymptotic Notation. Prove or disprove the following statements. Assume
all functions referred to in this question have domain N and range R
=0
.
(a) If f(n) ? ?(g(n)), then g(n) ? O(f(n)).
(b) [If f(n) + g(n) ? O(h(n)), then f(n) ? O(h(n)) and g(n) ? O(h(n)).
(c) If f(n) + g(n) ? ?(h(n)), then f(n) ? ?(h(n)) or g(n) ? ?(h(n)).
(d) [If f(n) + h(n) ? T(g(n) + h(n)), then f(n) ? T(g(n)).
(e) If f(n) is non-decreasing and f(n) = n
2
for odd n’s (but we do not know the values of
f(n) for even n’s), then f(n) ? T(n
2
)
