Module 1 – Discrete Mathematics

Module 1
DISCRETE MATHEMATICS 1
Module 1 – Discrete Mathematics
 Module 1 – Discrete Mathematics 1.1

Introduction
Discrete mathematics is concerned with functions and relationships which are defined only for
the positive integers.

1.1 Factorials
Suppose you are organising a dinner party for six people and you are interested in the number
of different ways you can arrange the seating order of the guests (and yourself). One order may
be:

Adam Adam

yourself Blaise Drew Charlie

while another could be

Edwina Charlie Blaise Edwina

Drew yourself

Obviously there are many ways to fill the six seats at the table. Consider the positions at the
table numbered as shown below:

Position 1

Position 6 Position 2

Position 5 Position 3

Position 4

For your dinner party there are 6 different ways to fill Position 1 (Adam or Blaise or Charlie or
Drew or Edwina or yourself). Once a person has been allocated to Position 1, there are five
people from which an allocation to Position 2 can be made. Then there are four people left to
make a choice for Position 3 etc. until there is only one person left to be allocated to Position
6.
1.2 TPP7184 – Mathematics Tertiary Preparation Level D

The number of different seating arrangements for six people is:

five people to
choose from for
Position 2

6 5 4 3 2 1 i.e. there are 720 different ways to seat

the six people at the dinner table.

six people to 1 person to

choose from ‘choose from’
for Position 1 for Position 6

The mathematical expression for this sort of counting i.e. counting the number of ways to
arrange six objects without replacement is factorial six.

The symbol used is 6!

In general for any positive integer n,

n! = n (n – 1) (n – 2) … (1).

Note that 0! is defined to be 1 and 1! is defined to be 1.

On the ‘Casio fx – 82 LB fraction’ calculator the factorial key is the back function on the
Memory Recall key.

Make sure you can find the factorial key on your calculator.

When dealing with problems which involve counting you must use common sense. Often,
very simple mathematics is all that is required.

How many different six digit telephone numbers are there? (Assume zero cannot occupy the
first position.)

Your estimate? ..........................................................

Answer:

One way of doing this is to recognise that we are dealing with permutations and replacement is
allowed.
& 1, 2, 3, 4, 5, 6, 7, 8 or 9 '
No. of ways of selecting = 9 $ %
first digit " zero is excluded #
No. of ways of selecting = 10
second digit
…

No. of ways of selecting = 10

sixth digit
! Total number of permutations = 9 10 10 10 10 10
= 9 105 = 900 000
 Module 1 – Discrete Mathematics 1.3

Factorial key
x! = x (x – 1) (x – 2) … (1)

No. of Permutations
1 *y
n!
key nPr = ----- xy x
r!

nPr n Cr

No. of Combinations
n!
key nCr = -----------------------
r! ( n – r )!

Using factorials is very convenient for many instances which involve counting (generally
called combinatorics).

Combinations
Suppose you only want three of your five friends to come to dinner how many different
combinations of guests can you get? (As you will always be there don’t include yourself in
your calculation.)

Your estimate is: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

How did you do it? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

...........................................................

...........................................................
1.4 TPP7184 – Mathematics Tertiary Preparation Level D

Answer:

One way to determine the answer is to go through your friends and make up various
dinner party lists e.g. Adam, Blaise, Charlie (ABC)
Adam, Blaise, Drew (ABD)

…
Charlie, Drew, Edwina (CDE)

This can be represented in a tree diagram as:

See Note 1
C ABC
D ABD
E
ABE

B
D ACD
E
ACE
C
E ADE

E
D BCD
E BCE
A C
D E BDE
B E

C
D E CDE
E
D

E
E

1st guest 2nd guest 3rd guest

There are ten different possible combinations of 5 people taken 3 at a time.

Notes
1. Note how doing things systematically (i.e. following a strategy or pattern) is beneficial.
 Module 1 – Discrete Mathematics 1.5

The number of possible combinations of 5 things taken 3 at a time when order is not important
/ 50
is written as 5C3 or - . .
+ 3,

/ 50 5! 5 4 3 2 1 (as found above by listing all

5C
3 = - . = ----------------------------- = ------------------------------------------------- = 10
+ 3, ( 3! ) ( 5 – 3 )! (3 2 1) (2 1) the possible combinations)

In general, the number of possible combinations of n objects taken r at a time without

/ n0 n!
replacement is nC
r = - . = ----------------------------
+ r, ( r! ) ( n – r )!

Find the
nC key on your calculator. It is the back function on the
r
2 digit on the Casio shown on p. 1.3.

When considering combinations the order of selection is not important e.g. Charlie, Drew,
Edwina make the same list of dinner guests as Drew, Charlie, Edwina or Edwina, Drew,
Charlie etc. However it is often the case that the order is important e.g. number plates,
telephone numbers, preferential voting, word building games. When order is important there
are many more ways of selecting a subset of objects than when order is unimportant.

Permutations
Consider again five objects from which three are to be selected but this time the order is
important. If no replacement is allowed there are 5 ways of filling Position 1; 4 ways of filling
Position 2; and 3 ways of filling Position 3.

i.e. 5 4 3 = 60 different ways

The total number of different ways when order of selection is important is called the number
of permutations. The number of permutations of 5 things taken 3 at a time when order is
important is written as 5P3

5P 5! 5 4 3 2 1
3 = ------------------- = ---------------------------------------- = 60
( 5 – 3 )! (2 1)

and in general, the number of permutations of n objects taken r at a time without

n!
replacement is nPr = ------------------
( n – r )!

Find the
nP key on your calculator. It is the back function on the
r
1 digit on the Casio shown on p. 1.3.

Permutations and combinations also occur when replacement or repetition is allowed.

e.g. in six digit telephone numbers

292 654 is a different number to 296 254

1.6 TPP7184 – Mathematics Tertiary Preparation Level D

How many different six digit telephone numbers are there? (Assume zero cannot occupy the
first position.)

Your estimate? ..........................................................

Answer:

One way of doing this is to recognise that we are dealing with permutations and replacement is
allowed.

No. of ways of selecting = 9

first digit

No. of ways of selecting = 10

second digit
…

No. of ways of selecting = 10

sixth digit

! Total number of permutations = 9 10 10 10 10 10

= 9 105 = 900 000
 Module 1 – Discrete Mathematics 1.7

Example 1.1:

A club committee consists of 12 members. Under the constitution of the club, a minimum of
eight members is required for a quorum.

(i) In how many ways can a minimum quorum occur?

(ii) In how many ways can a quorum occur?

(iii) If a president, secretary and treasurer are to be elected from the committee members, how
many ways can this be achieved?

Solution:

(i) Order is unimportant, so we want the number of ways of selecting 8 members from 12
members.

/ 120
i.e. - . = 495 See Note 1
+ 8,

A quorum is 8, 9, 10, 11 or 12 members. Again, the order is unimportant, so the total number
of ways a quorum can occur is

/ 120 / 120 / 120 / 120 / 120

- . + - . + - . + - . + - . = 495 + 220 + 66 + 12 + 1
+ 8 , + 9 , + 10, + 11, + 12,
= 794

(ii) We will assume that no committee member can hold more than one executive position.
The number of ways three people can be selected from 12 is
12 P = 1 320 See Note 2
3

Notes

12
1. The key strokes for / 0
nC
are 12 r 8 = and the display should read 495.
+ 8,
12!
(You can check this result by finding ---------- ).
8!4!

12 P nP
2. The keystrokes for are 12 r 3 = and the display should read 1 320.
3
12!
(You can check this result by finding -------- ).
9!
1.8 TPP7184 – Mathematics Tertiary Preparation Level D

Exercise Set 1.1

1. How many three letter permutations of MAP are there if

(i) Repetitions are allowed

(ii) Repetitions are not allowed

2. In some states of Australia car license plates are in the form of three single digit numbers
followed by three letters of the alphabet. How many different number plates are possible
using this system?

3. If there are ten applicants for four similar jobs in a company, how many different ways can
the positions be filled.

4. Six people are running for election for two positions on a committee. In how many ways
can the positions be filled?

/ 100 / 100
5. Show that - . = - .
+ 4, + 6,
6. A laboratory cage contains eight white mice and six brown mice. Find the number of ways
of choosing five mice from the cage if

(i) They can be of either colour

(ii) They must be of the same colour

(iii) Three must be white and two must be brown

 Module 1 – Discrete Mathematics 1.9

1.2 Binomial Theorem

Now that you have mastered factorials and combinations we can proceed to utilise them for
expansions of algebraic expressions.

Example 1.2:

Expand (x + 3)2

Now use your graphing package to draw the graph of y = f(x) =

(x + 3)2 and on the same screen draw the graph of your expansion.
If you have the correct expansion, your graphs will be coincidental.
Solution:

You should have got (x + 3) (x + 3)= x2 + 3x + 3x + 32 {using the Distributive Law}

= x2 + 6x + 32

Example 1.3:

Expand (x + a)4

Solution:

You should have got (x + a) (x + a) (x + a) (x + a)

= x4 + 4x3a + 6x2a2 + 4xa3 + a4

The RHS of this equation can be written as

1x4a0 + 4x3a1 + 6x2a2 + 4x1 a3 + 1x0a4

What is the pattern in the powers of x? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

What is the pattern in the powers of a? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

What do the indices of x and a sum to in each term? . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Answer: The power of x decreases by one for each term, while the power of a increases
by one for each term. The sum of the indices is 4 for every term.

Examine the coefficient of each term. What is the pattern? [Hint: Think in terms of
combinations.] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

...........................................................................

...........................................................................

...........................................................................
1.10 TPP7184 – Mathematics Tertiary Preparation Level D

Answer:

Term Coefficient Combination

$ 4%
1x4a0 1 " # 4 things taken 4 at a time
4!

$ 4%
4x3a1 4 " # 4 things taken 3 at a time
3!

$ 4%
6.2a2 6 " # 4 things taken 2 at a time
2!

$ 4%
4x1a3 4 " # 4 things taken 1 at a time
1!

$ 4%
1x0a4 1 " # 4 things taken 0 at a time
0!

■
Example 1.4:

Expand (x + y)3. Find patterns in the coefficients and powers of x and y in each term

Solution:

(x + y)3 = x3 + 3x2y + 3xy2 + y3 = 1x3y0 + 3x2y1 + 3xy2 + 1x0y3

Term Coefficient Combination

$ 3%
x3 1 " #
3!

$ 3%
3x2y 3 " #
2!

$ 3%
3xy2 3 " #
1!

$ 3%
y3 1 " #
0!

Coefficients of each term are combinations of 3 things taken 3, 2, 1, 0 at a time

Power of x decreases by one for each term

Power of y increases by one for each term
The sum of the indices of x and y is 3 for each term

■
 Module 1 – Discrete Mathematics 1.11

Example 1.5:

Write an expression for (x + a)5 using the same pattern as shown in Example 1.4 above.

...........................................................................

...........................................................................

Solution:

$ 5% $ 5% $ 5% $ 5% $ 5% $ 5%
(x + a)5 = " # x 5 a 0 + " # x 4 a 1 + " # x 3 a 2 + " # x 2 a 3 + " # x 1 a 4 + " # x 0 a 5
5! 4! 3! 2! 1! 0!

= x5 + 5x4a + 10x3a2 + 10x2a3 + 5xa4 + a5

Note that in each expansion e.g. (x + a)4 and (x + a)5 there is another pattern in the
coefficients.

• When the power of the expansion is odd, there is an even number of terms in the
expanded form and the coefficients of the two central terms are the same value
* $ 5% $ 5% +
( " # = " # ) and the coefficients of the terms on either side of the central terms are the
& 3! 2! '
* $ 5% $ 5% $ 5% $ 5% +
same value ( " # = " # and " # = " # )
& 4! 4! 5! 0! '
• When the power of the expansion is even, there is an odd number of terms in the expanded
form and the coefficient of the central term forms the ‘pivot’ for the symmetry of the
coefficients on either side.

* $ 4% $ 4% $ 4% $ 4% +
(" # = " # and " # = " #)
& 3! 1! 4! 0! '

$ n% $ n %
In general " # = " #
r! n – r!

The general expansion of (x + a)n where n is a positive integer is given by:

$ n% $ n % n–1 1 $ n % n–2 2 $ n % n–3 3

(x + a)n = " # x n a 0 + " # x a + " # x a + " # x a + ,
n! n – 1! n – 2! n – 3!

$ n% $ n% $ n% $ n%
+ " # x3 an – 3 + " # x2 an – 2 + " # x1an – 1 + " # x0 an
3! 2! 1! 0!
1.12 TPP7184 – Mathematics Tertiary Preparation Level D

which is exactly the same as

$ n% n 0 $ n% $ n% $ n%
(x + a)n = " # x a + " # xn – 1 a1 + " # xn – 2a2 + " # xn – 3 a3 + ,
0! 1! 2! 3!

$ n % 3 n–3 $ n % 2 n–2 $ n % 1 n–1 $ n%

" # x a + " # x a + " # x a + " # x0 an
n – 3! n – 2! n – 1! n!

This expression can be summarised succinctly using Sigma Notation

n
$ n% n – r r
- x + a .n = / " # x
r!
a
r=0

This is known as the Binomial Theorem. There is no need for you to learn the expanded
form of the Theorem. Think about the patterns and remember the Sigma Notation form only.
$ n%
The first term in the summation i.e. (r = 0) will be " # x n a 0 ; the other terms then follow
the pattern. 0!

The second term (i.e. r = 1) is

decrease of 1

Check that indices of x and a

$ n% n – 1 1 add to n.
" # x a increase of 1
1! (n – 1) + 1 = n ✓

increase of 1

The third term is

decrease of 1

$ n% n – 2 2
" # x a increase of 1 (n – 2) + 2 = n ✓
2!

increase of 1

$ n%
and so on until the last term is " # x0an n + 0 = n ✓
n!
 Module 1 – Discrete Mathematics 1.13

Exercise Set 1.2

1.

(a) Write down the first term in the expansion of (x + 4)6

(b) Write down the remaining terms in the form of the Binomial Theorem following the
pattern from (a)

(c) Calculate the coefficients on the calculator using the n Cr key

(d) Simplify the expanded terms

(e) Use your graphing package to draw the graph of (x + 4)6 and your expansion. [If the
graphs are not coincidental check your work.]

2.

(a) Write down the first term in the expansion of (x – 4)5 [Hint: Care is needed with the
negative 4]

(b) Write down the remaining terms in the form of the Binomial Theorem following the
pattern from (a)

(c) Calculate the coefficients

(d) Simplify the expanded terms

(e) Draw the graph of (x – 4)5 and your expansion. [If the graphs are not coincidental check
your work]

3. Expand

(a) (x + 1 0y)4

(b) (2x + y2)3

(c) (i) (x2 + 10 x2)5 (ii) Draw the graphs of (x2 + 1 0x2)5 and your expansion

(d) (i) (p – 2p3)6

4. Find the coefficient of x2 and x–1 in the following expansions

(a) (x2 + 1 0x)4

(b) (1 0x – x2)4

5. Use the Binomial Theorem to find (1.01)4 [Hint: Express 1.01 as (1 + 0.01)]
1.14 TPP7184 – Mathematics Tertiary Preparation Level D

1.3 Sequence and Series

Sequences
In the Revision Module we focussed on continuous functions that generally were defined for
all values of x. i.e. the set of real numbers was the domain of the function. In sequences, we
are dealing with functions which are defined only for the positive integer values of x.
Sequences take many forms and the one you are probably familiar with is the Fibonacci
sequence which occurs commonly in nature e.g. in the breeding of rabbits, the arrangement of
pine cones.

The Fibonacci sequence is obtained from an iterative process (i.e. one which builds upon itself
in a regular manner). Iterative processes are used widely in computing and mathematics and
often depend upon the definition of a recurrence relation. A sequence can be defined by its
recurrence relation i.e. the relationship between a term and its preceding terms or by its
functional relationship. Sequences are usually written as s(n) to avoid confusion with f(x)
which is usually used for continuous functions.

To start our work on sequences complete the following example.

 Module 1 – Discrete Mathematics 1.15

Example 1.6:

Complete the following table for the sequence s(n) = 2n, n = 1, 2, 3

n 1 2 3 4 5 … 10 … 20 … 100
s(n) = 2n 21 = 2 22 = 4 33 = 8 … … …

Draw the graph of the sequence, s(n) = 2n for 1 1 n 1 5 on the graph paper below.

s(n)
70
60

50
40

30

20
10

1 2 3 4 5 n
–10
–20

–30

–40
–50

–60
–70

You can check your graph by drawing f(x) = 2x for say 1 1 x 1 5

on your computer. But remember that for the sequence the points at
the integer x values are not joined and that it is defined for all the
positive integers.
■
1.16 TPP7184 – Mathematics Tertiary Preparation Level D

The sequence s(n) = 2n is an example of a divergent sequence i.e. There is no limit to the
size of s(n). (Look back at the values of s(n) for n = 5, 10, 20, 100)

A divergent sequence is one where, as n 234, s(n) 234 (or –4).

A convergent sequence is one where, as n 234, s(n) 2 some finite fixed number.

Sometimes sequences do not converge to a unique fixed number but oscillate between two
values. These sequences are not convergent.

Exercise Set 1.3

1. A sequence is defined by s(n) = (–1)n (n2 – 3). Find the first four terms and the 10th
and 20th term of the sequence.

2. Draw the graph of s(n) = (1 0 2)n

Does this sequence converge? If so, what is the limit of s(n) as n 234?

3. Consider s(n) = (–1)n.

Does this sequence converge? If so what is the limit of s(n) as n 234?

The Fibonacci sequence is obtained by starting with the numbers 1 and 1 and obtaining each
new term as the sum of the two preceding terms.

If we let the nth term in this sequence be un, complete the following:

u1 = 1 u2 = 1 u3 = 2 u4 = 3 u5 = …

u6 = … u12 = … u15 = …

The general term for the Fibonacci sequence is un and the recurrence relation is
See Note 1

un = un – 1 + un – 2 (given that u1 = 1 and u2 = 1)

Notes
1. The general term for any sequence is usually called un.
 Module 1 – Discrete Mathematics 1.17

Exercise Set 1.4

1. (a) Find the next 4 numbers in the following sequences

(i) 2, 4, 6, 8, 10, …

(ii) 0, 3, 8, 15, …

(iii) 1, 1 0 2, 1 0 4, 1 0 8, 1 0 16, …

Write down un, the general term for each sequence in (a)

Find u20, u100 and u1 000 for each sequence in (a)

2. (a) Find a recurrence relation for un for each of the following sequences.

(i) 1, 2, 3, 4, …

(ii) 10 10 10 10
2, 4, 8, 16, …

(iii) 1, –1, –3, –5, –7, …

(b) Determine if each sequence is convergent or divergent. If convergent find the limit of
s(n) as n 234.

Geometric Sequence
Consider the sequence whose general term un is given by

un = 1 0 2 un – 1

Then if u1 = 1
u2 = 10 5 u = 10 2 5 1 = 10 2
2 1
u3 = 10 5 u = 10 2 5 10 2 = (1 0 2)2
2 2
u4 = 10 5 u = 1 0 2 5 (1 0 2)2 = (1 0 2)3
2 3
…

un = 1 0 2 5 un – 1 = 1 0 2 5 (1 0 2)n – 2 = (1 0 2)n – 1

and we can write the function as s(n) = (1 0 2)n – 1

1.18 TPP7184 – Mathematics Tertiary Preparation Level D

This type of sequence is known as a geometric sequence and its general form is

u1 = a
u2 = ar
u3 = ar2
u4 = ar3
…

un = arn – 1

where a is the first term and r is the common ratio between succeeding terms. So in
the example above a = 1 and r = 1 0 2.

Geometric sequences are convergent if –1 < r < 1

If we add say the first four terms of a sequence the result is called the fourth partial sum and
is denoted by S4.

So the fourth partial sum for our example above is

S4 = 1 + 1 0 2 + (1 0 2)2 + (1 0 2)3 = 1.875

In general, the nth partial sum is

Sn = 1 + 1 0 2 + (1 0 2)2 + (1 0 2)3 + … + (1 0 2)n – 2 + ( 1 0 2) n – 1

Obviously if we want to find S20 the calculations would be very tedious. Fortunately, for
geometric sequences we can use a simple rule to find partial sums. See Note 1

a- rn – 1 .
Sn = ----------------------
r–1

Let’s try the rule on our example to find the fourth partial sum and the twentieth partial sum

1 - - 10 2 . 4 – 1 .
S4 = --------------------------------
10 2 – 1

1 - 10 16 – 1 .
= --------------------------
-
– 10 2
– 15 – 2
= 1 5 --------- 5 ------
16 1
= 1.875
1 - - 10 2 . 20 – 1 .
S20 = ----------------------------------
10 2 – 1
-

= 1.999998093

Notes
1. This rule was proved in Unit 11083.
 Module 1 – Discrete Mathematics 1.19

Now we know that s(n) = (1 0 2)n – 1 is convergent because it is a geometric sequence with
r = 1 0 2.

From examination of the partial sums above and the rule for Sn, it seems fairly reasonable to
say that the ‘infinite’ partial sum i.e. S4 = 2.

Generally we say the ‘sum to infinity of the geometric series’ and we write
a- rn – 1 . a
lim S n = lim --------------------- = S 4 = -----------
n24 n24 r – 1 1 –r

Note that we use the term series when we are considering the sum of an infinite number of
terms of a sequence.

You need to be careful to use the correct symbols for the functional
relationship for a sequence i.e. lower case s in s(n) and the partial
sums i.e. upper case s in Sn.

Exercise Set 1.5

1. Find the required partial sum for each sequence.

(a) S4 for s(n) = 0.1n

1
(b) S6 for s(n) = ----n-
2
(c) S10 for s(n) = e3n

(d) S5 for s(n) = (–1)n

2. For each of the sequences in question 1 above

(a) determine if it is convergent

(b) if it is convergent find its sum to infinity if possible

Series

The Binomial Theorem for expanding (x + a)n that you met earlier can be extended to the
case where n is not positive integer. The result of such a binomial explansion is a series (i.e.
the sum of the terms in a sequence).

Consider the expansion of (a + b)n where a and b are real numbers and n is a positive
integer.

Write out the binomial expansion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

...........................................................................
1.20 TPP7184 – Mathematics Tertiary Preparation Level D

Answer:

$ n% $ n% $ n% $ n% $ n%
(a + b)n = " # a n b 0 + " # a n – 1 b 1 + " # a n – 2 b 2 + " # a n – 3 b 3 + , + " # a 0 b n
0! 1! 2! 3! n!

Express the binomial coefficients as products and quotients, simplify and rewrite the expansion

...........................................................................

Answer:

n-n – 1 . n-n – 1.-n – 2 .

(a + b)n = an + nan – 1b1 + -------------------- a n – 2 b 2 + ------------------------------------- a n – 3 b 3 + , + b n
2 6

Express the divisors of each term, except the first and last, as factorials (Look for a pattern)

Answer:
na n – 1 b n - n – 1 . n-n – 1.-n – 2.
(a + b)n = an + ------------------ + -------------------- a n – 2 b 2 + ------------------------------------- a n – 3 b 3 + , + b n _____ !
1! 2! 3!
■

This is now a finite series with (n+1) terms. ________________________________ See Note 1

If we rewrite (a + b) as a $ 1 + ---% ,
b See Note 2
a!

n
* b +
then (a + b)n = ( a $ 1 + ---% )
& a! '

n
= a n $ 1 + ---%
b See Note 3
a!

b n
So to find (a + b)n we need only find $ 1 + ---% and then multiply by an.
a!

Notes
1. ‘finite’ because you can count the exact number of terms.

2. Taking a as a common factor out of (a + b).

3. Using the index rule (ab)m = ambm.

 Module 1 – Discrete Mathematics 1.21

b n
Let x = --- , then $ 1 + ---% = - 1 + x . n
b
a a!

and by using the form of equation ! we get

n . 1n – 1 x n- n – 1 . . 1n – 2x2 n- n – 1 .- n – 2 . . 1n – 3x3
- 1 + x . n = 1 n + ----------------------- + ------------------------------------------ + ------------------------------------------------------------ + , + x n
1! 2! 3!

nx n - n – 1 .x 2 n - n – 1 . - n – 2 .x 3
6 - 1 + x . n = 1 + ------ + ------------------------- + ------------------------------------------ + , + x n _____________ "
1! 2! 3!

So, in general, when n is a positive integer (1 + x)n can be written as a finite series and thus
has a finite sum.

There are interesting outcomes when n is not a positive integer. We will consider first when
n is a positive fraction, say n = 1 0 2. When n = 1 0 2. Equation " becomes

10 2 10 2 x 10 2 - 10 2 – 1 .x 2 10 2 - 10 2 – 1 . - 10 2 – 2 .x 3
-1 + x. = 1 + ----------
- + ----------------------------------- -+,
- + ----------------------------------------------------------
1! 2! 3!
10 2 x 10 2 5 – 10 2 x 2 10 2 5 – 10 2 5 – 3 0 2 x 3
- 5 ------------------------------
= 1 + ---------- -+,
- + ------------------------------------------------
1! 2! 3!
10 4 x 2 30 8 x 3
= 1 + 10 2 x – ------------- + ------------- +,
2! 3!

x x2 x3
= 1 + --- – ----- + ------ + ,
2 8 16

This is an infinite series, whose sum is finite providing –1 < x < 1 See Note 1

The condition –1 < x < 1 ensures that the later terms in the series get progressively smaller.

Now consider (1 + x)n when n = –1.

In this case, Equation " becomes

- – 1 .x - – 1 . - – 1 – 1 .x 2 - – 1 . - – 1 – 1 . - – 1 – 2 .x 3
- 1 + x . – 1 = 1 + -------------- + ---------------------------------- + ---------------------------------------------------- + , _____________ #
1! 2! 3!

i.e. - 1 + x . – 1 = 1 – x + x 2 – x 3 + x 4 – x 5 + ,

again we can see that if –1 < x < 1, this infinite series will have a finite sum.

Notes
1. infinite because you cannot count the exact number of terms.
1.22 TPP7184 – Mathematics Tertiary Preparation Level D

Example 1.7:

Use Equation # to write (1 – x)–1 as an infinite series in simplest form using sigma notation.

Solution:

(1 – x)–1 = (1+ –x)–1

- –1 . - –x . - –1 . - –1 –1 . - –x . 2 - –1 . - –1 –1 . - –1 –2 . - –x . 3
= 1 + ---------------------- + ------------------------------------------ + ------------------------------------------------------------ + ,
1! 2! 3!

= 1 + x + x2 + x3 + ,

= / xn
n=0

(1 – x)–1 is so common it is called THE geometric series. It occurs very frequently in

engineering, statistics etc. See Note 1

1
It has a finite sum ----------- when –1 < x < 1.
x–1

1 1
So when x = 1 0 2, 1 + x + x2 + x3 + , = ----------------
- = -------
- = 2
1 – 10 2 1
02

1
when x = 1 0 4, 1 + x + x2 + x3 + , = ----------------
- = 4
03
1 – 10 4

Notes
1. Compare this geometric series with the geometric sequence on page 1.17.
 Module 1 – Discrete Mathematics 1.23

1.4 Mathematical Induction

The principle of mathematical induction is used widely to prove statements where there are no
suitable theorems to support the proof. We can use it to prove the sum of a series is a certain
finite value, once we know the general form of the series.

Suppose you are asked to add the numbers from 1 to 1 000 – obviously a tedious task!

1 + 2 + 3 + 4 + 5 + … + 997 + 998 + 999 + 1 000 = ?

1 000 5 1 001
It turns out that this series sums to --------------------------------- = 500 500
2
n-n + 1 .
In general the sum of the first n positive integers is -------------------- .
2
To prove this statement (or any other) using induction we use the following procedure

1. Show that the statement is true for n = 1

2. Assume that the statement is true for any value of n, say k

3. Verify that, under the assumption in Step 2, the statement is true for the next value of n
i.e. for n = (k + 1)

If Step 3 is successful, then the statement must be true for n = 2, n = 3, n = k + 2,

n = k + 3, … etc (because k could be any number). i.e. we can conclude that the statement
is true for all n.

Example 1.8:
n-n + 1.
Prove that Sn = 1 + 2 + 3 + … + n = -------------------- See Note 1
2
Solution:

Step 1: Show statement is true for n = 1

n-n + 1. 1-1 + 1 .
When n = 1, Sn = S1 = 1 and -------------------- = -------------------- = 1
2 2
6 statement is true for n = 1

Step 2: Assume statement is true for n = k

n-n + 1 . k-k + 1.
When n = k, Sn = Sk = 1 + 2 + 3 + … + k and -------------------- = -------------------
2 2

k-k + 1.
6 the assumption is: 1 + 2 + 3 + … + k = ------------------- _____________ !
2

Notes
1. Again do not confuse s(n) and Sn. s(n) refers to the functional relationship which shows how each s value
depends on an n value while Sn is the sum of the first n terms of the sequence.
1.24 TPP7184 – Mathematics Tertiary Preparation Level D

Step 3: Verify the statement is true for n = (k + 1), using the assumption in Step 2

When n = (k + 1)

Sn = Sk + 1 = 1 + 2 + 3 + … + k + (k + 1) and

n-n + 1 . -k + 1.-k + 1 + 1. -k + 1.-k + 2 . _____________ "

-------------------- = ------------------------------------------- = ----------------------------------
2 2 2

k-k + 1.
Now 1 + 2 + 3 + … + k = ------------------- (From assumption in Step 2 i.e. equation !)
2

6 We can substitute in equation " for most of its LHS, (for the first k terms) and get

k-k + 1. k-k + 1. + 2-k + 1.

Sk + 1 = ------------------- + - k + 1 . = ----------------------------------------------
2 2
-k + 1.-k + 2.
= ---------------------------------- (Taking the common factor (RH) out)
2
= RHS of equation "

n-n + 1 .
Thus, Sn = 1 + 2 + 3 + … + n = -------------------- is true for any positive integer value of n.
2

Instead of starting at n = 1, some induction arguments start at another positive integer. The
steps involved are the same, except in Step 1 you show that the statement is true for your
selected starting point.

Example 1.9:

2 2 2 2 1
Show that S n = ----1- + ----2- + ----3- + , + ----n- = 1 – ----n-
3 3 3 3 3

Solution:

Step 1: Show statement is true for n = 1

2 2 1 1 2
When n = 1, S n = S 1 = ----1- = --- and 1 – ----n- = 1 – ----1- = ---
3 3 3 3 3
6 statement is true for n = 1

Step 2: Assume statement is true for n = k

2 2 2 2 1 1
When n = k, S n = S k = --- + ----2- + ----3- + , + -----k and 1 – ----n- = 1 – -----k
3 3 3 3 3 3

6 the assumption is:

2 2 2 2 1
--- + ----2- + ----3- + , + -----k = 1 – -----k _____________ !
3 3 3 3 3
 Module 1 – Discrete Mathematics 1.25

Step 3: Verify the statement is true for n = (k + 1), using the assumption in Step 2.

When n = (k + 1)

2 2 2 2 2 1 1
S n = S k + 1 = --- + ----2- + ----3- + , + -----k + --------------
- and 1 – ----n- = 1 – --------------
- ____ "
3 3 3 3 3-k + 1. 3 3-k + 1.

2 2 2 2 1
Using the assumption from Step 2, gives --- + ----2- + ----3- + , + ----k- = 1 – -----k
3 3 3 3 3

6 Substituting for most of LHS of equation " gives

1 2
Sk + 1 = 1 – -----k + --------------
-
3 3 + 1. - k

3 2
= 1 – --------------
-
-. + --------------
- See Note 1
3 k + 1 3 + 1.
- k

1
= 1 – --------------
-
3 + 1.
- k

= RHS of equation "

2 2 2 2 1
Thus, Sn = --- + ----2- + ----3- + , ----n- = 1 – ----n- for all positive integer values of n.
3 3 3 3 3

Notes
1 3
1. Make sure you can show that ----- = -------------------- .
3k 3- k + 1 .
1.26 TPP7184 – Mathematics Tertiary Preparation Level D

Exercise Set 1.6

Use the technique of mathematical induction to prove the following

1. 1
2 + (1 2)2 + (1 2)3 + … + (1 2)n = 1 – (1 2)n
1 – xn + 1
2. 1 + x + x2 + x3 + … + xn = -------------------- (if x ! 1)
1–x
(Compare this result with the formula for the partial sum of a geometric sequence)
n " n + 1 # " 2n + 1 #
3. The sum of the squares of the first n integers is -----------------------------------------
6

4. " s + t # + " s + 2t # + " s + 3t # + $ + " s + nt # = n ' s + ------------ t(

n+1
% 2 &
 Module 1 – Discrete Mathematics 1.27

Solutions to Exercise Sets

Solutions Exercise Set 1.1 page 1.8
1. (i) If repetitions are allowed there are 3 letters available for the first position, 3 letters
available for the second position and 3 letters available for the third position

) no. of permutations = 3 * 3 * 3 = 33 = 27

(ii) If repetitions are not allowed there are 3 letters available for the first position, 2
letters available for the second position and 1 letter available for the third position.

) no. of permutations = 3 * 2 * 1 = 6
3! 3! 3!
Note: nPr = 3P3 = ------------------- = ----- = ----- = 6
" 3 – 3 #! 0! 1

2. There are 10 single digits (0, 1, 2, 3, …, 9). There are 10 ways to fill the first position of
the numbers, 10 ways to occupy the second position and 10 ways to occupy the third
position.

) The numbers on the plates can be chosen in 10 * 10 * 10 = 103 = 1 000 ways.

Each of the sets of numbers can be followed by 3 letters from a possible

26 * 26 * 26 = 263 = 17 576 arrangement of letters.

) The total number of different license plates = 1 000 * 17 576 = 17 576 000

3. As the jobs are similar it does not matter which job goes to which person (i.e. order is not
important).
10!
) The positions can be filled in nC
r = 10C
4 = ----------- = 210
4!6!
4. If we assume order is important e.g. say the two positions are Secretary and Treasurer, then
Person 1 + Secretary and Person 2 + Treasurer will give a different committee from
Person 2 + Secretary and Person 1 + Treasurer etc.
6!
So the number of different committees = nPr = 6P2 = ----- = 30
4!
• If we assume order is not important e.g. the two positions on the committee
are as ‘regular’ committee members then the number of different committees
6!
= nCr = 6C2 = ----------- = 15
2!4!
1.28 TPP7184 – Mathematics Tertiary Preparation Level D

Solutions Exercise Set 1.1 cont.

' 10( 10! 10! ' 10( 10! 10!

5. , - = --------------------------- = ----------- and , - = --------------------------- = -----------
% 4& 4! " 10 – 4 #! 4!6! % 6& 6! " 10 – 6 #! 6!4!

' 10( ' 10( ' n( ' n (

) , - = , - and in general , - = , -
% 4& % 6& % r& % n – r&

6. (i) There are 14 mice altogether ) no. of ways of choosing any five
= nCr = 14C5 = 2 002

(ii) There are 8 white mice ) no. of ways of choosing five

= nCr = 8C5 = 56

There are 6 brown mice ) no. of ways of choosing five

= nCr = 6C5 = 6

) no. of ways of choosing five mice of the same colour

= 56 + 6 = 62

(iii) There are 8C3 ways of picking the three white mice and each of these can be
associated with one selection of two brown mice. There are 6C2 ways of getting two
brown mice.

) Total no. of ways of choosing five white mice and two brown mice

= 8C3 * 6C2 = 56 * 15 = 840

 Module 1 – Discrete Mathematics 1.29

Solutions Exercise Set 1.2 page 1.13

1. (x + 4)6

(a) First term is 6C0x640 = x6

(b) (x + 4)6 = 6C0x640 + 6C1x541 + 6C2x442 + 6C3x343 + 6C4x244 + 6C5x145 + 6C6x046

(c) 6C = 1 ; 6C = 6 ; 6C = 15 ; 6C = 20;
0 1 2 3

6C = 15 ; 6C = 6 ; 6C = 1
4 5 6

(d) (x + 4)6 = x6 + 6x5.41 + 15x4.42 + 20x3.43 + 15x244 + 6x145 + 46

= x6 + 24x5 + 240x4 + 1 280x3 + 3 840x2 + 6 144x + 4 096

2. (a) (x – 4)5 = 5C0x5(–4)0

(b) (x – 4)5 = 5C0x5(–4)0 + 5C1x4(–4)1 + 5C2x3(–4)2 + 5C3x2(–4)3 + 5C4x1(–4)4 + 5C5x0(–4)5

(c) 5C = 1 ; 5C = 5 ; 5C = 10 ; 5C = 10;
0 1 2 3

5C = 5 ; 5C = 1
4 5

(d) (x – 4)5 = x5 + 5x4(–4)1 + 10x3(–4)2 + 10x2(–4)3 + 5x1(–4)4 + (–4)5

= x5 – 20x4 + 160x3 – 640x2 + 1 280x – 1 024

3. (a) (x + 1 y)4 = 4C0x4(1 y)0 + 4C1x3(1 y)1 + 4C2x2(1 y)2 + 4C3x1(1 y)3 + 4C4x0(1 y)4

4x 3 6x 2 4x 1
= x4 + -------- + -------
2
- + -----3- + ----4-
y y y y

(b) (2x + y2)3 = 3C0(2x)3(y2)0 + 3C1(2x)2(y2)1 + 3C2(2x)1(y2)2 + 3C4(2x)0(y2)3

= (2x)3 + 3(2x)2y2 + 3(2x)(y2)2 + (y2)3

= 8x3 + 3.4x2.y2 + 3.2x.y4 + y6

= 8x3 + 12x2y2 + 6xy4 + y6

1.30 TPP7184 – Mathematics Tertiary Preparation Level D

Solutions Exercise Set 1.2 cont.

3. (a) (i) (x2 + 1
x 2)
5 = 5C0(x2)5(1 x2)0 + 5C1(x2)4(1 x2)1 + 5C2(x2)3(1 x2)2

+ 5C3(x2)2(1 x2)3 + 5C4(x2)1(1 x2)4 + 5C5(x2)0(1 x2)5

= x10 + 5x8.1 x2 + 10x6.1 x4 + 10x4.1 x6 + 5x2.1 z8 + 1

z10 See Note 1

= x10 + 5x6 + 10x2 + 10

x2 + 5
x6 + 1
x10

(ii)
y

(b) (i) (p – 2p3)6 = 6C0 p6(–2p3)0 + 6C1 p5(–2p3)1 + 6C2 p4(–2p3)2

+ 6C3 p3(–2p3)3 + 6C4 p2(–2p3)4 + 6C5 p1(–2p3)5 + 6C6 p0(–2p3)6

= p6 + 6p5.(–2p3) + 15p4.(4p6) + 20p3.(–8p9) + 15p2.(16p12)

+ 6p.(–32p15) + 64p18

= p6 – 12p8 + 60p10 – 160p12 + 240p14 – 192p16 + 64p18

Notes
1. Use the index laws carefully.
 Module 1 – Discrete Mathematics 1.31

Solutions Exercise Set 1.2 cont.

4. (a) (x2 + 1
x)
4 = 4C0(x2)4(1 x)0 + 4C1(x2)3(1 x)1 + 4C2(x2)2(1 x)2 + 4C3(x2)1(1 x)3 + 4C4(x2)0(1 x)4

1 1 1 1
= x8 + 4x6. --- + 6x4. ----2- + 4x2. ----3- + ----4-
x x x x

4 1
= x8 + 4x5 + 6x2 + --- + ----4-
x x

) Coefficient of x2 is 6 and coefficient of x–1 is 4

(b) (1 x – x2)4 = (1 x)4 + 4(1 x)3(–x2)1 + 6(1 x)2(–x2)2 + 4(1 x)1(–x2)3 + (–x2)4

1 4x 2 6x 4 4x 6
= ----4- – -------
- + -------
- – -------- + x8
x x3 x2 x

1 4
= ----4- – --- + 6x2 – 4x5 + x8
x x

) Coefficient of x2 is 6 and coefficient of x–1 is –4

5. (1.01)4 = (1 + 0.01)4 = 14 + 4C113(0.01)1 + 4C212(0.01)2 + 4C311(0.01)3 + (0.01)4

= 1 + 4 * 0.01 + 6 * 0.0001 + 4 * 0.000001 + 0.00000001

= 1.040604

Checking: On the calculator (1.01)4 = 1.040604 ✓

1.32 TPP7184 – Mathematics Tertiary Preparation Level D

Solutions Exercise Set 1.3 page 1.16

1. s(n) = (–1)n(n2 – 3)

s(1) = (–1)1(12 – 3) = –1(1 – 3) = 2

s(2) = (–1)2(22 – 3) = 1(4 – 3) = 1
s(3) = (–1)3(32 – 3) = –1(9 – 3) = –6
s(4) = (–1)4(42 – 3) = 1(16 – 3) = 13

s(10) = (–1)10(102 – 3) = 1(100 – 3) = 97

s(20) = (–1)20(202 – 3) = 1(400 – 3) = 397

2. n 1 2 3 4 5 6 7
s(n) = (1 2)n 1
2
1
4
1
8
1
16
1
32
1
64
1
128

s(n)

0.4

0.3

0.2

0.1

n
−1 0
0 11 22 33 44 55 66 77 88 99 10
10 11
11

1
This sequence converges. e.g. 10
- / 0
when n = 10, s(n) = ------
2
1
when n = 100, s(n) = ---------
100
/ 0 etc.
2
) limit of s(n) as n + . = 0

3.
n 1 2 3 4 5 6
s(n) = (–1)n –1 +1 –1 +1 –1 +1 etc.

This sequence does not converge. It oscillates between –1 and 1.

 Module 1 – Discrete Mathematics 1.33

Solutions Exercise Set 1.4 page 1.17

1. (a) (i) 2, 4, 6, 8, 10, 12, 14, 16, 18, …

(ii) 0, 3, 8, 15, 24, 35, 48, 63, …

(iii) 1, 1 2, 1 4, 1 8, 1 16, 1 32, 1 64, 1 128, 1 256, …

(b) (i) un = 2n

(ii) un = n2 – 1
1
- or un = (1/2)n – 1
(iii) un = -----------
n
2 –1
(c) (i) u20 = 2 * 20 = 40 ; u100 = 2 * 100 = 200 ; u1 000 = 2 * 1 000 = 2 000

(ii) u20 = 202 – 1 = 399 ; u100 = 1002 – 1 = 9 999 ; u1 000 = 1 0002 – 1 = 999
1 1 1 1 1 1
(iii) u20 = -------------
- = ------
- ; u100 = ---------------
- = ------
- ; u1 000 = -------------------
- = ---------
2 –1
20 2 19 2 –1
100 2 99 2 1000 –1 2 999

2. (a) (i) 1, 2, 3, 4 … 0 un = un – 1 + 1 given u1 = 1

(ii) 1
2 , 1 4, 1 8, 1 16 … 0 un = 1
2 un – 1 given u1 = 1
2

(iii) 1, –1, –3, –5, –7 … 0 un = un – 1 – 2 given u1 = 1

(b) (i) Divergent

(ii) Convergent. Limit of s(n) as n + . is 0

(iii) Divergent
1.34 TPP7184 – Mathematics Tertiary Preparation Level D

Solutions Exercise Set 1.5 page 1.19

1. (a) For s(n) = 0.1n

S4 = s(1) + s(2) + s(3) + s(4)

= 0.11 + 0.12 + 0.13 + 0.14

= 0.1111
1
(b) For s(n) = ----n-
2
S6 = s(1) + s(2) + s(3) + s(4) + s(5) + s(6)
1 1 1 1 1 1
= ----1- + ----2- + ----3- + ----4- + ----5- + ----6-
2 2 2 2 2 2
63
= ------ = 0.984375
64

(c) For s(n) = e3n

S10 = s(1) + s(2) + … + s(9) + s(10)

= e3 * 1 + e3 * 2 + e3 * 3 + e3 * 4 + … + e3 * 9 + e3 * 10

= 1.124639986 * 1013

Make sure you correctly interpret the display of the calculator

which gives the result in scientific notation form.
(d) For s(n) = (–1)n

S5 = s(1) + s(2) + s(3) + s(4) + s(5)

= (–1)1 + (–1)2 + (–1)3 + (–1)4 + (–1)5

= –1 + 1 – 1 + 1 – 1

= –1
 Module 1 – Discrete Mathematics 1.35

Solutions Exercise Set 1.5 cont.

2. (a) (i) Convergent. As n + ., s(n) + 0

s(n) = 0.1n can be written as s(n) = 0.1 * 0.1n – 1

This gives the general term un = 0.1 * 0.1n – 1 and comparing with the
general geometric series un = arn – 1 we see a = 1 and r = 0.1
) as –1 < r < 1, s(n) converges and its sum to infinity
a 0.1 0.1 1
S. = ----------- = ---------------- = ------- = ---
1–r 1 – 0.1 0.9 9

(ii) Convergent. As n + ., s(n) + 0

1
s(n) = ----n- can be written as s(n) = 1
2 * (1 2)n – 1
2

Comparing with the general geometric series un = arn – 1 gives a = 1 2

and r = 1 2 ) as –1 < r < 1, s(n) converges and its sum to infinity
a 12
S. = ----------- = ---------------
- = 1
1–r 1 – 12

(iii) Divergent. As n + ., s(n) + .

(iv) Not convergent, s(n) oscillates between –1 and 1.

1.36 TPP7184 – Mathematics Tertiary Preparation Level D

Solutions Exercise Set 1.6 page 1.26

1. Prove 1
2 + (1 2)2 + (1 2)3 + … + (1 2)n = 1 – (1 2)n

Step 1: When n = 1, S1 = (1 2)1 = 1 2 and 1 – (1 2)n = 1 – (1 2)1 = 1

2
) statement is true for n = 1

Step 2: Assume true for any n = k

When n = k, Sk = 1 2 + (1 2)2 + (1 2)3 + … + (1 2)k = 1 – (1 2)k

Step 3: Using the assumption in Step 2 we need to show

1
2 + ( 2)
1 2 + (1 2)3 + … + (1 2)k + (1 2)k + 1 = 1 – (1 2)k + 1

From Step 2 we can substitute for most of LHS (for the first k terms).
(1 2) + (1 2)2 + (1 2)3 + … + (1 2)k + (1 2)k + 1 = 1 – (1 2)k + (1 2)k + 1

We now need to rearrange the RHS i.e. 1 – (1 2)k + (1 2)k + 1 into the form
1 – (1 2)k + 1 to prove the statement

1 – (1 2)k + (1 2)k + 1 = 1 – (1 2)k + (1 2)(1 2)k See Note 1

= (1 2)k 1 – 1 + 1
2 2 + 1

= (1 2)k 1 – 1 2 2 + 1

= 1 – (1 2)k + 1

) As the statement is true for n = k + 1, assuming it was true for any n = k

and it is true for n = 1, it is true for all n i.e. for all positive integers.

Notes
1. You may have used different algebraic manipulations to what is shown here.
 Module 1 – Discrete Mathematics 1.37

Solutions Exercise Set 1.6 cont.

1 – xn + 1
2. Prove 1 + x1 + x2 + x3 + … + xn = -------------------- (if x ! 1)
1–x

1 – xn + 1 1 – x1 + 1 1 – x2
Step 1: When n = 1, S1 = 1 + x and -------------------- = -------------------- = --------------
1–x 1–x 1–x

"1 – x#"1 + x #
= --------------------------------- = 1 + x
"1 – x#
) Statement is true for n = 1

Step 2: Assume true for any n = k

1 – xk + 1
When n = k, Sk = 1 + x + x2 + x3 + … + xk = --------------------
1–x
Step 3: Using the assumption in Step 2 we need to show
1 – x"k + 1# + 1
1 + x + x2 + x3 + … + xk + xk + 1 = -------------------------------
1–x
1 – xk + 1
From Step 2, we are assuming 1 + x + x2 + x3 + … + xk = --------------------
1–x
1 – xk + 1
) 1 + x + x2 + x3 + … + xk + xk + 1 = -------------------- + xk + 1 {Adding xk + 1 to each side}
1–x

1 – x"k + 1 # + 1
We now need to rearrange the RHS into the form ------------------------------- to prove the statement.
1–x

1 – xk + 1
RHS = -------------------- + xk + 1
1–x

1 – xk + 1 + xk + 1" 1 – x #
= ------------------------------------------------------- {Putting terms on common denominator of (1 – x)}
1–x

1 – xk + 1 + xk + 1 – xk + 1 + 1
= ---------------------------------------------------------------
1–x

1 – x"k + 1# + 1
= -------------------------------
1–x

Thus we have shown, by mathematical induction, that

1 – xn + 1
1 + x + x2 + x3 + … + xn = -------------------- (if x ! 1)
1–x
 1.38 TPP7184 – Mathematics Tertiary Preparation Level D

Solutions Exercise Set 1.6 cont.

n " n + 1 # " 2n + 1 #
3. Prove 12 + 22 + 32 + 42 + … + n2 = -----------------------------------------
6
n " n + 1 # " 2n + 1 # 1 " 1 + 1 # " 2 * 1 + 1 #
Step 1: When n = 1, S1 = 1 and ----------------------------------------- = -----------------------------------------------
6 6
1*2*3
= --------------------- = 1
6
) Statement is true for n = 1

Step 2: Assume true for any n = k

k " k + 1 # " 2k + 1 #
When n = k, Sk = 12 + 22 + 32 + 42 + … + k2 = ----------------------------------------
6
Step 3: Using the assumption in Step 2
k " k + 1 # " 2k + 1 #
Sk + 1 = 12 + 22 + 32 + 42 + … + k2 + (k + 1)2 = ---------------------------------------- + (k + 1)2
6

"k + 1#""k + 1# + 1#"2"k + 1# + 1#

We now need to rearrange the RHS into the form -----------------------------------------------------------------------------------
to prove the statement 6

k " k + 1 # " 2k + 1 # k " k + 1 # " 2k + 1 # + 6 " k + 1 # 2 {Putting terms on common

---------------------------------------- + (k + 1)2 = --------------------------------------------------------------------- denominator}
6 6

" k + 1 # 1 k " 2k + 1 # + 6 " k + 1 # 2 {Taking (k + 1) out as a

= ------------------------------------------------------------------------- common factor}
6

" k + 1 # 1 2k 2 + k + 6k + 6 2
= ---------------------------------------------------------------
6

" k + 1 # 1 2k 2 + 7k + 6 2
= ------------------------------------------------------
6

" k + 1 # " k + 2 # " 2k + 3 # {Factorising 2k2 + 7k + 6

= ------------------------------------------------------
6

" k + 1 # " " k + 1 # + 1 # " 2k + 2 + 1 #

= ------------------------------------------------------------------------------
6

" k + 1 #" " k + 1 # + 1 #" 2" k + 1 # + 1#

= -----------------------------------------------------------------------------------
6

) Using mathematical induction the statement is proved true for any positive integer.
 Module 1 – Discrete Mathematics 1.39

Solutions Exercise Set 1.6 cont.

4. Prove (s + 1t)(s + 2t) + (s + 3t) + … + (s + nt) = n ' s + ------------ t(

n+1
% 2 &

Step 1: When n = 1, S1 = s + t and n ' s + ------------ t( = 1 ' s + ------------ t( = s + t

n+1 1+1
% 2 & % 2 &
) Statement is true for n = 1

Step 2: Assume true for any n = k

When n = k, Sk = (s + t) + (s + 2t) + (s + 3t) + … + (s + kt) =

k ' s + ------------ t(
k+1
% 2 &

Step 3: Using the assumption in Step 2.

Sk + 1 = (s + t) + (s + 2t) + (s + 3t) + … + (s + kt) + (s + (k + 1)t)

= k ' s + ------------ t( + (s + (k + 1)t)

k+1
% 2 &

We now need to rearrange k ' s + ------------ t( + (s + (k + 1)t) into the form

k+1
% 2 &

"k + 1# + 1
(k + 1) ' s + -------------------------- t( to prove the statement.
% 2 &

k ' s + ------------ t( + (s + (k + 1)t)

k+1
% 2 &

= ks + k ' ------------( t + s + (k + 1)tl

k+1
% 2 &

= (k + 1) ' ---- + t( + s(k + 1)

kt
{Taking (k + 1) as a common factor out of 2 terms
%2 & and s as a common factor out of the other 2 terms}

7 kt + 2t 8
= (k + 1) 5 ---------------- + s 6
3 2 4

"k + 1# + 1
= (k + 1) ' s + -------------------------- t(
% 2 &

"k + 1# + 1
= (k + 1) ' s + -------------------------- t(
% 2 &

Thus we have proved, using mathematical induction, that the statement is true.
1.40 TPP7184 – Mathematics Tertiary Preparation Level D