MAT 210 Discrete Mathematics

Chapter 6. Basic Number Theory

Objective: to be able to
 define sequences and express them using summation notation or in recursive formula
 prove a conjecture using mathematical induction

6.1 Sequences & Summation

∞
Sequence: set/list of number in specific order, denoted {ak }k=1 , where ai is the ith term in the sequence.

Eg 1: a) 1 , 2, 3 , 4 ,… .={k }∞k=1 – a sequence of +ve integers with a1 = 1, a2 = 2, a3 = 3, a4 = 4, ….

So, the kth term, ak = k, k ≥ 1.

b) { 3 , 6 , 9 ,12 , … . }={3 k }∞k=1 – a sequence of non-negative multiples of 3 with b1 = 3(1), b2 = 3(2), b3 = 3(3),
b4 = 3(4), …. So, the kth term, bk = 3k, k ≥ 1.

c) { 2 , 5 ,8 , 11, … }={3 k −1}k=1 – an arithmetic sequence with the kth term, ck = 3k – 1, k ≥ 1.

∞

n ❑
d) If dn = (-1)n n(n+2), n  0, then { (−1 ) n (n+2)}n=0 – a sequence with the kth term, dk = (–1)kk(k+2), k ≥ 0.
So the first 5 terms of the sequence are 0, -3, 8, -15, 24.

e) Find the first 5 terms of the sequence with en+1 = 3n, n  0.

e1 = 30 = 1, e2 = 31 = 3, e3 = 32 = 9, e4 = 33 = 27, e5 = 34 = 81

n
∑ ai
SIGMA representation for Summations: we use the notation i=m to represent am + am+1 + am+2 + am+3 + … + an
– 1 + an. Variable i is a dummy variable called the index of summation, usually start from 0 or 1.

Eg 2: Write the appropriate summation notations.

5 5 6 4
=∑ i = 2
∑ j 2 = ∑ ( j−1)2 = ∑ (k +1)2
a) 12 + 22 + 32 + 42 + 52 i=1 j=1 j=2 k=0
n n n+2
∑ i= ∑ k= ∑ ( j−2 )
b) 1 + 2 + 3 + … + n = i=1 k=1 j=3
n
∑ (2i−1)
c) 1 + 3 + 5 + … + (2n – 1) = i=1
n
∑ (3 i+1 )
4 + 7 + 10 + … + (3n + 1) = i=1

d)

Eg 3. Find the sums.

6
∑ (2i−1)
a) i=3 = [2(3) – 1] + [2(4) – 1] + [2(5) – 1] + [2(6) – 1] = 5 + 7 + 9 + 11 = 32
6
∑ (2i−1 )
b)i=2 = (22 –1) + (23 – 1) + (24 – 1) + (25 – 1) + (26 – 1) =

1
MAT 210 Discrete Mathematics

8
∑ (−1)k (k+1)( k−3 )=(−1 )6(7 )(3)+(−1 )7( 8)( 4 )+(−1)8 (9)(5 )=
c) k=6

Eg 4. Given the sequence 4, 7, 10, 13, 16, ….. Find the nth term and give a sigma representation for the sum of the
first n terms.

We observe the pattern of the terms as follow:

i ai pattern
1 a1 = 4 4 = 3 + 1 = 3(1) + 1
2 a2 = 7 7 = 6 + 1 = 3(2) + 1
3 a3 = 10 10 = 9 + 1 = 3(3) + 1
4 a4 = 13 13 = 12 + 1 = 3(4) + 1
5 a5 = 16 16 = 15 + 1 = 3(5) + 1
: : :
n an ???
n
∑ 3 i+1
We see that an is the sum of n terms of 3 and 1, i.e., an = 3n + 1. Hence, Sn = 4 + 7 + 10 + … + (3n + 1) = i=1 .

Eg 5. Find a sigma representation of the sum of the first n terms of 4, 12, 36, 108, …..

The pattern of the terms is given below:

i ai Pattern
1 4 4 = 4 x 1 = 4 x 30
2 12 12 = 4 x 3 = 4 x 31
3 36 36 = 4 x 9 = 4 x 32
4 108 108 = 4 x 27 = 4 x 33
: : :
n an ???

n n
∑ 4 (3 i−1
) ∑ 4 (3 j−1 )
We can see that an = 4(3n – 1), we have that Sn = 4 + 12 + 36 + 108 + … + 4(3n – 1) = i=1 = j=1 .

Eg 6. Determine a sigma representation for the sum of the first n terms of 4, 16, 36, 64, …. Obtain a conjecture that
gives the n-th term in sigma representation.

The pattern of the terms is given below.

n n
∑ (2i )2=∑ 4 i2
Since an = (2n)2 = 4n2, we have that Sn = i=1 i=1 .

2
MAT 210 Discrete Mathematics

Observe that the value of each term of the sequence is given by:

n n
∑ (8 i−4 ) ∑ (8 i−4 )=4 n2
Hence, an = 4 + 12 + 20 + … + (8n – 4) = i=1 . Since an = 4n2, we conjecture that i=1 .

Eg 7. Obtain a conjecture for the sum 1 + 3 + 5 + 7 + 9 + … + (2n – 1).

Observe that
i Summation form, Si Other form
1 1=1 12
2 1+3=4 22
3 1+3+5=9 32
4 1 + 3 + 5 + 7 = 16 42
5 1 + 3 + 5 + 7 + 9 = 25 52
….
n 1 + 3 + 5 + 7 + 9 + … + (2n – 1) =? ?

n
∑ (2i−1)=n 2
From the above pattern, we conjecture that 1 + 3 + 5 + 7 + 9 + … + (2n – 1) = n2, i.e., i=1 .

Eg 8. Find a conjecture for the sum Sn = 1 + 21 + 22 + 23 + 24 + … + 2n – 1 .

Observe that
i Summation form of Si Other form
1 1=1 21 – 1
2 1 + 21 = 3 22 – 1
3 1 + 21 + 22 = 7 23 – 1
4 1 + 21 + 22 + 23 = 15 24 – 1
5 1 + 21 + 22 + 23 + 24 = 31 25 – 1
: : :
n 1 + 21 + 22 + 23 + 24 + … + 2n–1 2n – 1

From the above pattern, we conjecture that 1 + 21 + 22 + 23 + 24 + … + 2n – 1 = 2n – 1.

Eg 9. Find a conjecture for the sum Sn = 3 + 6 + 12 + 24 + 48 +…. + 3(2n – 1).

Observe the pattern below:

i Summation form of Si Other form
1 3=3 3 = 3(2 – 1) = 3(21 – 1)
2 3+6=9 9 = 3(4 – 1) = 3(22 – 1)
3 3 + 6 + 12 = 21 21= 3(8 – 1) = 3(23 – 1)
: : :
n 3 + 6 + 12 +…+ 3(2n – 1) = ? 3(2n – 1)

3
MAT 210 Discrete Mathematics

Hence, we conjecture that: 3 + 6 + 12 + 24 + 48 + …. + 3(2n – 1) = 3(2n – 1).

Exercise 6.1.
1. Write the first five terms for each of the following defined sequence.
a) an = 6n + 2, n ≥ 1 b) an = (3n + 1)(2n – 1), n ≥ 0 c) an = 1 – (1/n)2, n ≥ 1
d) a1 = 2, a2 = 3, an = an-1 + an-2 + 1, n ≥ 3 e) a1 = –2, a2 = 3, an = 2an-1 – an-2 + 1, n ≥ 3

5
∑ ai
2. Find i=2 for each sequence in Question 1.

3. Determine the fifth term for each of the following summation expression and obtain the sum of the first five
terms.
n n n
∑ 1+i
n
(i−2)2
∑ (2i−5) 2 ∑ (−1 ) (2 i)
i i+1
∑ i−2
a) i=1 b) i=1 i c) i=0 d) i=3 2

4. Write the following expression in summation notation.

a) 1 + 2 + 22 + 23 + 24 + … + 2n b) 1(3) + 2(4) + 3(5) + … + n(n + 2)
c) 4 + 9 + 14 + 19 + … + (5j – 1)

5. Find the n-th term for the sequence (i) 3, 12, 48, 192, ….; (ii) 9, 27, 81, …..; (iii) 2, 8, 18, 32, …

6. Find the sum of the first n terms, Sn, in sigma representation.

a) 5, 8, 11, 14, 17, ….
b) 5, 10, 20, 40, ….
c) 3, 9, 21, 45, ….
d) 2, 8, 26, 47, ….
e) 7, 21, 49, 105, ….

6.2 Recursion
An implicit expression of sequences in terms of previous known term(s). For example, let a1 = 6, an = 3an-1 + 2, n ≥ 2
is a recursion. Another simple example is n! = n(n – 1)!.

A sequence that is not implicit is explicit. An implicit sequence may have explicit expression. All sequences in Eg 1
of Section 6.1are explicit.

Eg 1: Give the first 5 terms of the following recursive sequences and find an explicit expression if possible.
a) a1 = 3, an = an-1 + 5 for integer n  2
a1 = 3, a2 = a1 + 5 = 8, a3 = a2 + 5 = 13, a4 = a3 + 5 = 18, a5 =
So, the sequence is: 3, 8, 13, 18, … or 5(1) – 2, 5(2) – 2, 5(3) – 2, 5(4) – 2, …
An explicit expression is an = 5n – 2, n  1.

Alternately, we have: an = an-1 + 5

= an-2 + 5 + 5
= an-2 + 2(5)
= an-3 + 3(5)
=…
4
MAT 210 Discrete Mathematics

= a1 + (n – 1)(5) + 5
= 3 + 5n – 10 + 5
= 5n – 2, n ≥ 1.
b) b1 = 2, bn = 2bn-1 – 3 for integer n  2
b1 = 2, b2 = 2b1 – 3 = 2(2) – 3 = 1, b3 = 2b2 – 3 = 2(1) – 3 = –1, b4 = 2b3 – 3 = 2(–1) – 3 = –5, b5 = –13.
So, the sequence is: 2, 1, –1, –5, –13, …. Or 3 – 1, 3 – 2, 3 – 4, 3 – 8, 3 – 16,… or 3 – 20, 3 – 21, 3 – 22,
3 – 23, 3 – 24, …
An explicit expression is: 3 – 2n – 1, n 1.

Alternately, we have bn = 2bn-1 – 3

= 2(2bn-2 – 3) – 3
= 22bn-2 – 21(3) – 3
= 22(2bn-3 – 3) – 21(3) – 3
= 23bn-3 – 22(3) – 21(3) – 3
…
= 2n-1b1 – 2n-2(3) – 2n-3(3) – … – 22(3) – 21(3) – 3
= 2n-1(2) – 3(2n-2 + 2n-3 + … + 22 + 21 + 20)
= 2(2n-1) – 3(2n-1 – 1)
= 3 – 2n-1, n ≥ 1.

Eg 2: Find a recursive definition for the following sequences.

a) 10, 13, 16, …
a1 = 10, a2 = 13 = 10 + 3 = a1 + 3, a3 = 16 = 13 + 3 = a2 + 3, …
 a1 = 10, an = an – 1 + 3, n  2.

b) 2, 4, 16, 256, …
b1 = 2, b2 = 4 = 22 = (b1)2, b3 = 16 = 42 = (b2)2, b4 = 256 = 162 = (b3)2, ….
 b1 = 2, bn = (bn – 1)2, n  2.

c) Cn = 7n + 5, n  1
C1 = 12, C2 = 19 = 12 + 7 = C1 + 7, C3 = 26 = 19 + 7 = C2 + 7, ….
 C1 = 7, Cn = Cn – 1 + 7, n  2.
OR
Cn-1 = 7(n – 1) + 5 = 7n – 2. So,
Cn – Cn-1 = 7n + 5 – (7n – 2) = 7 and
Cn = Cn-1 + 7, n  2.

d) Dn = 2(7n), n  1
D1 = 14, D2 = 98 = 7(14) = 7(D1), D3 = 686 = 7(98) = 7(D2), ….
 D1 = 14, Dn = 7(Dn – 1), n  2.
OR
Dn-1 = 2(7n-1). So
Dn – Dn-1 = 2(7n) – 2(7n-1) = 2(7n-1)(7 – 1) = 6[2(7n-1)] = 6Dn-1 and
Dn = 7Dn-1, n  2.

Q2: Give a recursive definition for Cn = 11n – 8, n  Z+.

5
MAT 210 Discrete Mathematics

Exercise 6.2
(a k )!
1. A sequence a1, a2, a3, …, an is defined recursively by ak+1 = ak −1 for integer k  2 with a1 = 1 and a2
4
∑ ai
= 3. Evaluate i=1 .

2
a n=
2. Given a recursive sequence
a n−1 and a = 2. Find a .
4 1

3. Find a recursive formula for the sequence 0.25, - 0.5, 1, -2, 4, -8, ….

4. Find a recursive definition for the sequence 5, 8, 13, 20, 29, 40, …..

3 −108
5. Given a recursive sequence: a n+1= an and a 4= . Find the first 3 terms of the sequence if n is a natural
5 125
number. Obtain an explicit expression for the sequence.

6. A sequence is defined as follow: Cn = 4n – 9 where n  Z+.

i) Write down the first four terms of the sequence.
ii) Find the recursive definition of the sequence.

7. Find a recursive formula for the following sequences.

i) an = 6n + 3, n ≥ 1
ii) an = 7 – 8n, n ≥ 1
iii) an = 3n-1 + 5, n ≥ 1
iv) an = 6(5n) + 1, n ≥ 1

8. Find an explicit expression for the following recursive sequences.

i) an = –3an-1, a0 = 2, n ≥ 1
ii) an = an-1 + n, a1 = 1, n ≥ 2

6.3 Mathematical Induction

Well Ordering Principle (Axiom)
Every nonempty set of nonnegative integers has a least element.

Principle of Mathematical Induction

Mathematical Induction is a proving technique used to prove any formula or statement in mathematics that uses
positive integers (in general).

It has a domino effect whereby if a domino started to fall, each successive domino will fall one after another. To
ensure this, we need to (1) make sure that the first domino will fall, and (2) if the kth domino falls, it will hit and
cause the (k+1)st domino to fall.

Theorem
Let P(n), n = 1, 2, 3, …be statements with the following properties.

6
MAT 210 Discrete Mathematics

1. Basis step. P(1) is a true statement.

2. Inductive step. If P(k) is a true statement, then P(k+1) is a true statement. [i.e. P(k) logically implies P(k+1) ]
Then, each of the statements P(1), P(2), P(3),… is also true, i.e., P(n) is true for all integers n ≥ 1.

In basis step, we need to show that P(1) is true. In inductive step, we first assume that P(k) is true and use this
assumption to prove that P(k+1) is true.

Eg 1: Use mathematical induction to prove that 1 + 2 + … + n = n(n+1)/2 for all +ve integer n.
n
∑ i= 12 n(n+1 )
P(n) : 1 + 2 + … + n = n(n+1)/2 for all +ve integer n OR P(n): i=1

1. Prove that P(1) is true.

1
1
∑ i=1 = (1+1)
LHS = i=1 , RHS 2 = 1. So, P(1) is true.
k
1
∑ i= 12 k (k +1 ) k ( k +1).
2. Assume that P(k) is true. So, assume i=1 OR assume 1 + 2 + … + k = 2
k +1
∑ i= 12 (k +1 )[(k +1 )+1 ]= 12 (k +1 )(k +2 )
Now prove that P(k+1) is true, i.e., need to show: i=1 .
1
= (k +1)( k +2)
Or show: 1 + 2 + … + k + (k+1) 2
k +1 k
∑ i=∑ i+(k +1 )
LHS = i=1 i=1 or LHS = (1 + 2 + … + k) + (k+1)
1
k ( k +1)+(k +1)
=2 -- by induction assumption

=
( )
k
(k +1 ) + 1
2
1
( k+1)(k +2)
=2 = RHS
n
∑ i= n2 (n+1 )
Hence, by mathematical induction, i=1 for n  Z+.

n
∑ (2i−1)=n 2
Eg 2: Use mathematical induction to prove that i=1 for all +ve integer n.
n
∑ (2i−1)=n 2
P(n): i=1 or P(n): 1 + 3 + 5 + … + (2n – 1) = n2

1. Prove that P(1) is true.

1
∑ (2i−1)
LHS = i=1 = 2(1) – 1 = 1. RHS= 12 = 1. So P(1) is true.

7
MAT 210 Discrete Mathematics

k
∑ (2i−1)=k 2
2. Assume that P(k) is true. So, assume i=1 OR assume 1 + 3 + 5 + … + (2k – 1) = k2.
k +1
∑ (2 i−1)=(k +1 )2
Now prove that P(k +1) is true, i.e., show: i=1 .
OR show: 1 + 3 + 5 + … + (2k – 1) + (2k +1) = (k +1)2.
k +1 k
∑ (2 i−1)=∑ (2 i−1)+[2(k +1)−1 ]
LHS = i=1 i=1 OR LHS = (1 + 3 + 5 + … + (2k – 1)) + (2k +1)
2
= k + 2k + 1 -- by induction assumption
= (k+1)2 = RHS.
n
∑ (2i−1)=n 2
Hence, by mathematical induction, i=1 for n  Z+.

Eg 3: Use mathematical induction to show that 1 + 2 + 22 + 23 +…+2n = 2n+1 – 1 for all non-ve integer n.

n
∑ 2i =2n+1−1
P(n): i =0 for n  0, n  Z OR P(n): 1 + 2 + 22 + 23 +…+2n = 2n+1 – 1
1. Prove that P(0) is true. (Note: the least value of n is 0)
0
∑ 2i =20 =1=2 0+1 −1
LHS = i =0 = RHS

k
∑ 2i =2k +1−1
2. Assume that P(k) is true. So, i =0 OR 1 + 2 + 22 + 23 +…+ 2k = 2k+1 – 1.
k +1
∑ 2i=2 k +2−1
Now prove that P(k+1) is true, i.e., show: i=0 . OR 1 + 2 + 22 + 23 +…+ 2k + 2k+1 = 2k+2 – 1.
k +1 k
∑ 2i=∑ 2i + 2k +1
LHS = i=0 i=0 OR LHS = (1 + 2 + 22 + 23 +…+ 2k) + 2k+1
k +1 k +1
=2 –1+2 -- by induction assumption
= 22k +1 – 1
= 2k + 2 – 1 = RHS
Hence, by mathematical induction, 1 + 2 + 22 + 23 +…+2n = 2n+1 – 1 for all non-ve integer n.

You can watch the following clip for better understanding.

https://www.youtube.com/watch?v=TqpNDiqsz7k

8
MAT 210 Discrete Mathematics

3
n( n+1)
Q1: Use mathematical induction to prove that 3 + 6 + 9 + 12 + … + 3n = 2 for all n  Z+.

n
∑ (5 i−3)= n2 (5 n−1)
Q2: Prove that i=1 for all n  Z+ by using mathematical induction.

9
MAT 210 Discrete Mathematics

1
n (n+1)( 4 n+5 )
Q3: Prove that 1(3) + 2(5) + 3(7) + … n(2n + 1) = 6 .

n
1 n
∑ i(i+1 =
) n+1
Q4: Use mathematical induction to prove that i=1 for all n  Z+.

10
MAT 210 Discrete Mathematics

Eg 4: Use mathematical induction to prove that 4n < n2 – 7 for all n  6.

P(n): 4n < n2 – 7 for all n  6

1. Prove that P(6) is true. (Note: the least value of n is 6)

LHS = 4(6) = 24 < 29 = 62 – 7 = RHS

2. Assume P(k) is true. So, 4k < k2 – 7.

Now prove that P(k+1) is true, i.e., 4(k+1) < (k+1)2 – 7.

LHS = 4k+ 4
< k2 – 7 + 4 -- by induction assumption
< k2 – 7 + 2k +1, since 4 < 2k + 1 for k  6
= (k+1)2 – 7 = RHS

Hence, by mathematical induction, 4n < n2 – 7 for all n  6.

Eg 5: Use mathematical induction to show that n3 – n is divisible by 3 whenever n is a +ve integer.

P(n): n3 – n is divisible by 3

1. Prove that P(1) is true.

P(1): 13 – 1 = 0 is divisible by 3 -- is a true statement

2. Assume that P(k) is true. So, k3 – k is divisible by 3.

Now prove that P(k+1) is true, i.e., (k+1)3 – (k+1) is divisible by 3.

(k+1)3 – (k+1) = k3 + 3k2 + 3k + 1 – k – 1
= k3 – k + 3(k2 + k)

By induction assumption, k3 – k is divisible by 3. Since 3(k2 + k) is divisible by 3, we have k3 – k + 3(k2 + k) is

divisible by 3.

Hence, by mathematical induction, n3 – n is divisible by 3.

Q5: Verify that n!  2n–1 for all +ve integer n.

11
MAT 210 Discrete Mathematics

Exercise 6.3
1. Use mathematical induction to prove that 5 + 7 + 9 + … + (2n + 3) = n(n + 4) for integer n ≥ 1. Hence, find the
value of 5 + 7 + 9 + … + 83.

n
(3 n−19 )
2. Use mathematical induction to prove that –8 – 5 – 2 + 1 + 4 + … + (3n – 11) = 2 for integer n ≥ 1. Hence
find the value of –8 – 5 – 2 + 1 + … + 124.

12
MAT 210 Discrete Mathematics

n
(5 n+7)
3. Use mathematical induction to prove that 6 + 11 + 16 + 21 + … + (5n + 1) = 2 for integer n ≥ 1.

n 15
∑ (6i−8)=n(3n−5) ∑ (6i−8).
4. Use mathematical induction to prove that i=1 for all integer n ≥ 1. Hence, find i=1

n
∑ 6i(i+2)=n(n+1 )(2 n+7 )
5. Use mathematical induction to prove that i=1 for all n  Z+. Hence, find 6(1)(3) + 6(2)(4)
+ 6(3)(5) + … + 6(19)(21).

13
MAT 210 Discrete Mathematics

n2
(n+1 )2
6. Use mathematical induction to prove that 13 + 23 + 33 + … + n3 = 4 .

n
∑ 2 (3 i−1 )=3n −1 .
7. Use mathematical induction to show that i=1

8. Given that 1 + 3 + 9 + 27 + … + 3n-1 = (3n –1)/2. Use mathematical induction to prove that the above statement is
true for all integers n > 1. Hence, find the value of 1 + 3 + 9 + … + 59, 049, where 59,049 = 310.

14
MAT 210 Discrete Mathematics

9. Use mathematical induction to prove that the following statement is true for all positive integers n.
1 1 1 1 n
+ + +.. .+ =
1(5) 5( 9) 9(13) (4 n−3 )(4 n+1) 4 n+1

10. Use mathematical induction to prove that 1(2)(3) + 2(3)(4) + … + n(n+1)(n+2) = n(n+1)(n+2)(n+3)/4.

11. Prove that 1 + 1/4 +1/9 + … + 1/n2 < 2 – 1/n whenever n is a positive integer greater than 1.

12. Prove that 2n+1  2n for all integer n ≥ 3.

13. Prove that 3n < n! whenever n is a positive integer greater than 6.

15