using L-shaped pieces, where these pieces cover three squares at a time
as shown in fig. (n-positive integer).
69. Using Mathematical Induction prove that 3 + 3.5 + 3.5
2 + L + 3.5
n = 3
(5
n + 1 – 1)/4, where n is a nonnegative integer.
70. Using Mathematical induction prove that n! < n
n , where n > 1.
71. Show that 1
2 – 2
2 + 3
2 – L + (–1)
n –1
n
2 = (–1)
n–1 n(n+1)/2 where n > 0.
72. Determine which amounts of postage can be formed using 5-cent and
6-cent postage stamps. Prove your solution using mathematical
induction.
73. Show that n lines separate the plane into (
) /
n
n
2
2 2
+ +
regions if no two
of these lines are parallel and no three pass through a common point.
74. A computer network has 6 computers. Each computer is directly
connected to at least one of the other computers. Show that there are at
least 2 computers in the network that are directly connected to the same
number of other computers (using Pigeonhole principle).
75. Show that in a group of 5 people where any two people are either
friends/enemies, there are not necessarily three mutual friends or three
mutual enemies, using Pigeon-hole principle.
76. Use induction to prove that any integer composed of 3
n identical digits is
divisible by 3
n .
SHORT QUESTIONS AND ANSWERS
1. Define a set.
A set is a collection of objects.
2. Define “elements” of a set.
The objects comprising a set are called its elements or members.
3. Define a singleton.
A set having only one element is called a Singleton.
4. Define an empty set.
A set with no element at all is called the empty set.
Introduction
51