Discretemaths Book

c
Discrete Mathematics Notes
David A. Santos
Philadelphia, PA May 29, 2002

Contents
Preface v
1 An Introduction to C++ 1
1.1 C++ Alphabet . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 Comments . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.2 Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.3 Keywords . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Predefined Types . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.1 Notation for Types . . . . . . . . . . . . . . . . . . . 5
1.3 Variables and Constants . . . . . . . . . . . . . . . . . . . . 7
1.3.1 Scalar Types . . . . . . . . . . . . . . . . . . . . . . 7
1.3.2 Aggregate Types . . . . . . . . . . . . . . . . . . . . 9
1.3.3 Constants . . . . . . . . . . . . . . . . . . . . . . . . 13
1.4 Input and Output . . . . . . . . . . . . . . . . . . . . . . . . 14
1.5 Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.5.1 Unary Operators . . . . . . . . . . . . . . . . . . . . 16
1.5.2 Arithmetical Binary Operators . . . . . . . . . . . . . 16
1.5.3 Assignment Operators . . . . . . . . . . . . . . . . . 19
1.5.4 Relational Operators . . . . . . . . . . . . . . . . . . 24
1.5.5 Logical Operators . . . . . . . . . . . . . . . . . . . 24
1.5.6 Conditional Operator . . . . . . . . . . . . . . . . . . 25
1.5.7 Comma Operator . . . . . . . . . . . . . . . . . . . . 26
1.6 Pointers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
1.7 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.7.1 main() Function . . . . . . . . . . . . . . . . . . . . 31
iii
iv CONTENTS
1.7.2 Function Calls . . . . . . . . . . . . . . . . . . . . . 32

1.7.3 Parameter Passing . . . . . . . . . . . . . . . . . . . 34
1.8 if{}else{} Statement . . . . . . . . . . . . . . . . . . . . . 37
1.9 switch{} Statement . . . . . . . . . . . . . . . . . . . . . . 40
1.10 for(){} Loop . . . . . . . . . . . . . . . . . . . . . . . . . . 42
1.11 while(){} Loop . . . . . . . . . . . . . . . . . . . . . . . . 44
1.12 Examples of Full Programmes . . . . . . . . . . . . . . . . 45
2 Essential Techniques 1
2.1 Reductio ad Absurdum . . . . . . . . . . . . . . . . . . . . . 1
2.2 Pigeonhole Principle . . . . . . . . . . . . . . . . . . . . . . 4
2.3 Inclusion-Exclusion . . . . . . . . . . . . . . . . . . . . . . . 10
2.4 Parity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3 Counting 19
3.1 Introductory Problems . . . . . . . . . . . . . . . . . . . . . 19
3.2 Two Basic Counting Principles . . . . . . . . . . . . . . . . 23
3.3 Permutations . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.4 Combinations . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.5 Distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.6 Combinatorial Identities . . . . . . . . . . . . . . . . . . . . 38
3.7 The Binomial Theorem . . . . . . . . . . . . . . . . . . . . . 40
3.8 Multinomial Theorem . . . . . . . . . . . . . . . . . . . . . . 57
4 Arithmetic 61
4.1 Division Algorithm . . . . . . . . . . . . . . . . . . . . . . . 61
4.2 The Decimal Scale . . . . . . . . . . . . . . . . . . . . . . . 66
4.3 Non-decimal Scales . . . . . . . . . . . . . . . . . . . . . . 73
4.4 Well-Ordering Principle . . . . . . . . . . . . . . . . . . . . 77
4.5 Mathematical Induction . . . . . . . . . . . . . . . . . . . . 80
4.6 Congruences . . . . . . . . . . . . . . . . . . . . . . . . . . 87
4.7 Miscellaneous Problems with Integers . . . . . . . . . . . . 94
5 Sums, Products, and Recursions 103

5.1 Telescopic cancellation . . . . . . . . . . . . . . . . . . . . 103
5.2 Arithmetic Sums . . . . . . . . . . . . . . . . . . . . . . . . 107
5.3 Geometric Sums . . . . . . . . . . . . . . . . . . . . . . . . 111
5.4 Fundamental Sums . . . . . . . . . . . . . . . . . . . . . . 114
CONTENTS v
5.5 First Order Recursions . . . . . . . . . . . . . . . . . . . . . 119

5.6 Second Order Recursions . . . . . . . . . . . . . . . . . . . 126
5.7 Applications of Recursions . . . . . . . . . . . . . . . . . . 128
vi CONTENTS
Preface
These notes started during the Spring of 2002

viii
Chapter 1
An Introduction to C++
1.1 C++ Alphabet

1 Definition The C++ alphabet is the collection of the following characters:
a b c d e f g h i j k l m n o p q r s t u v w x y z A B C D E F G
H I J K L M N O P Q R S T U V W X Y Z
+ - * / % \ " ’ # , . ; : ! ? ( ) [ ] { } < > ^ &
~ | _ 0 1 2 3 4 5 6 7 8 9
2 Definition A token is a string of characters recognised as meaningful by

the C++ grammar (set of rules of the C++ language). The source of these
characters is the C++ alphabet
The C++ tokens are: the keywords, the identifiers, the constants, the
string-literals, the operators, and the punctuators, which will be defined
shortly.
3 Definition White space is the name given to spaces (blanks), horizontal

and vertical tabs, newline characters and comments.
! White space does not belong to the C++ alphabet. Whitespace serves
to indicate where tokens start and end: beyond this, any surplus of whites-
pace is discarded.
1
2 Chapter 1
1.1.1 Comments
4 Definition A comment is an explanatory note for the humans reading the

C++ code and it is otherwise ignored by the compiler.
Comments in C++ may occur in one of two forms. They may begin with a
double slash and end in the same line where they started, as in
// This is a valid C++ comment.

// This is another valid C++ comment.
This is an invalid comment. It does not start with slashes.
Another way of writing comments, inherited from C, is by enclosing the

comment within an opening comment symbol /∗ (no space between the
slash and the asterisk) and a closing comment symbol ∗/. This method
allows the use of multiple lines, as in
/* ’Twas brillig, And the slithy toves did gyre and gimble
in the wabe. All mimsy were the borogoves and the mome raths
outgrabe. */
! Comments of the type / ∗ COMMENT ∗ / cannot be nested. The

code
/* Something /* will go */ awry */
will produce a compiler error. This is because the compiler matches the first
/∗ with the first ∗/ that it encounters, and so the second /∗ is viewed as part
of the outer comment.
5 Definition A punctuator of C++ is any of the following characters (or in

the case of the three successive dots ..., a group of characters):
[ ] ( ) { } , ; : ... * = #
C++ Alphabet 3
1.1.2 Blocks
6 Definition A block is a grouping delimited by a left brace { and a match-
ing right brace }. Any two blocks may be either disjoint or nested.
7 Example The following blocks are disjoint.

{ // opens block I
.............
} // closes block I { // opens block II
.............
} // closes block II
8 Example In the following example, blocks II and III are disjoint, and both
are nested into block I.
{// opens block I ................
{// opens block II
.................
}// closes block II
{// opens block III
..................
}// closes block III
................. }// closes block I
! Indentation, albeit ignored by the C++ compiler, is recommended when

dealing with nested blocks. Two disjoint blocks at the same level should
have the same indentation, a block nested into another should be indented
towards the right.
1.1.3 Keywords
9 Definition A C++ keyword is a string of characters having a predeter-
mined meaning in the C++ language.
A list of standard C++ keywords appears in table 1.1.

4 Chapter 1
and and_eq asm auto bitand

bitor bool break case catch
char class compl const const_cast
continue default delete do double
dynamic_cast else enum explicit export
extern false float for friend
goto if inline int long
mutable namespace new not not_eq
operator or or_eq private protected
public register reinterpret_cast return short
signed sizeof static static_cast struct
switch template this throw true
try typedef typeid typename union
unsigned using virtual void volatile
wchar_t while xor xor_eq
Table 1.1: Standard C++ Keywords.
! All standard C++ keywords are in lowercase letters.

1.2 Predefined Types
10 Definition A type is a set of values that can be associated with given
data items.
Some predefined types in C++ are:
• the type void. This type is effectively the empty set.
• the type bool. This type is the boolean type, which can only assume
the values true or false.
• the type char. This is the character type. Used to represent single
characters like those forming the C++ alphabet.
• the type wchar_t. This is the long character type.

Predefined Types 5
• the type string. This is the string type. Used to represent strings of
characters.
• the type int. This is the integer type. The range of the integers is
machine-dependent, but we can at least assure ourselves that inte-
gers in the interval [−231 ; 231 − 1] will be represented.
• the type float. This is the real number type. Its range is machine-
dependent, but we can at least assure ourselves that the interval
[3.4 × 10−38 ; 3.4 × 1038 ] will be represented.
• the type double. These are real numbers with double precision. Nor-
mally in the range [1.7 × 10−308 ; 1.7 × 10308 ].
The range of the int type can be modified by the keywords long or short.
For example, in some machines a long int is in the range [−263 ; 263 − 1].
! For the purposes of these notes we will restrict to numerical data of

type int for integers or double for real numbers.
1.2.1 Notation for Types

C++ distinguishes between decimal (base 10), octal (base 8), and hex-
adecimal (base 16) integers. To indicate the compiler the different type of
base desired, we use:
• (decimal integers) no prefix, the ten digits {0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
and an optional sign {+, −}.
• (octal integers) the prefix 0 (zero), the eight digits {0, 1, 2, 3, 4, 5, 6,
7}. The negative sign may not be used in some implementations.
• (hexadecimal integers) the prefix 0x (zero x) or 0X, the digits {0, 1,
2, 3, 4, 5, 6, 7, 8, 9, A, a, B, b, C, c, D, d, E, e, F, f}. The negative
sign may not be used in some implementations.
11 Example The following are decimal integers

234 -10101
The following are octal integers

6 Chapter 1
0234 0101 The following are hexadecimal integers

0X23A4F 0x10101
To indicate the compiler that we are using a real floating point (decimal)
number we use a decimal point, the ten digits {0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
the letters e or E to indicate a power of 10, and an optional sign {+, −}.
12 Example The following are floating point numbers

2. 2.34 -101.01e23 123.01E-23
! The compiler distinguishes between, say, “7” (no decimal point) and
“7.” (with a decimal point). “7” is an integer, “7.” is a floating point number.
To indicate the compiler that we are using a character type, we enclose

the character in single quotes.
13 Example The following are character types

’2’ ’A’ ’)’
Some characters cannot be found on the keyboard or have predetermined

meanings in the C++ grammar. In order to represent them we need a
backslash character. For example,
• ’\n’ denotes the newline character (to go to the beginning of the

next line),
• ’\t’ denotes a horizontal tab character,
• ’\v’ denotes a vertical tab character,
• ’\b’ denotes a backspace character,
• ’\a’ denotes the bell or audible alert character,
• ’\\ ’ denotes a backslash character,
• ’\’’ denotes the single quote character,
• ’\"’ denotes the double quote character,

Variables and Constants 7
• ’\?’ denotes the question mark character,
• ’\r’ denotes the carriage return (return to the beginning of the present
line) character,
• ’\0’ denotes the null character.
To indicate the compiler that we are using a string type, we enclose the
string in double quotes.
14 Example The following are string types ”A” ”Anthony” ”I break for
camels!”
! There is a distinction between ’A’ (a character type) and "A" (a string

type).
15 Example To produce the output

”What is your name silly?”, said the idiot.
we need to type
”\”What is your name silly\?\”,\nsaid the idiot.\n”
1.3 Variables and Constants

1.3.1 Scalar Types
16 Definition An identifier is a finite string of characters which:
• does not contain whitespace,
• does not form a keyword,
• is composed of letters, underscores, or digits only, and,
• whose first character is not a digit.
17 Example The following are valid C++ identifiers:

R_7 long_nose_size is_prime PI Pi _first_of_many Float
8 Chapter 1
Notice that since C++ is case sensitive, the identifiers PI and Pi are dis-
tinct.
18 Example The following are not valid as C++ identifiers:

freedom-of-thought //illegal character - 2_out_of_3
//begins with a digit float //keyword £amount
//illegal character £
19 Definition A variable is an instance of a type. It is a memory location

with a specific address and identifier.
Variables can be modified during the life programme. The type of the
variable specifies how much memory is allocated to the variable.
20 Definition A variable declaration is a statement with syntax

type identifier;
! The declaration of the variable allocates space for it and a specific

location for it in the computer memory. Thus a variable cannot be utilised
without first being declared.
C++ allows multiple variables of the same type to be declared on one line
by means of a comma. For instance, the code
int var_a; int var_b; double var_c;
is equivalent to the code

int var_a, var_b; double var_c;
It is possible to declare and initialise a variable at the same time, by
means of the syntax
type identifier = particular_value;
21 Example The following are examples of variable declarations.

int number_of_humps, a, b, c; double
age_of_camel, x, y; char sex_of_camel; bool
is_the_camel_married; string _name_of_camel;
22 Example The following are examples of variable declarations with

initialisations.
int number_of_humps = 3, a = -18, b = 018, c =
0xA32; double age_of_camel = 22.4, x = 1.e22, y = -1.2E-3;
char sex_of_camel = ’M’; bool is_the_camel_married =
true; string _name_of_camel = ”Kabubi”;
! A variable may not be declared multiple times in the same block.

Thus the following fragment will produce a compiler error.
int var_a;
int var_a, var_b; //ERROR multiple declaration of var_a
double var_b //ERROR multiple declaration of var_b
1.3.2 Aggregate Types

23 Definition A 1-dimensional array is an aggregate of homogeneous
types. A 1-dimensional array is declared with the following syntax:
type identifier[size];
Here size must be a positive integral constant.
! Array elements in C++ are indexed from 0.

24 Example The elements of the array
int a[3];
are a[0], a[1], and a[2].
! C++ does not check for array bounds. Invoking the non-existent “ele-
ments” a[3], a[4], say, of the array in example 24 will result in an error.
25 Example Here is an example of an initialisation of a 1-dimensional

array:
int a[4] = {2, 3, 4, 5};
10 Chapter 1
Thus a[0] is 2, a[1] is 3, a[2] is 4, and a[3] is 5.
26 Example If we come short of initialisers, then the array will be padded

with zeros. Thus in
int a[4] = {2, 3};
a[0] is 2, a[1] is 3, a[2] is 0, and a[3] is 0. However, if we put more

initialisers than the size of the array, we will get an error.
27 Example The second form of initialisation allows us to drop the size of

the array in an initialisation. Thus, the code
int a[2] = {2, 3};
is equivalent to the code

int a[] = {2, 3};
! We may not omit the size of the array if we are simply declaring the
array. Thus
int a[]; //ERROR
will result in error. The compiler does not know how much space to allocate
to the array.
28 Definition A 2-dimensional array is declared with the following syntax:

type identifier[size_1][size_2];
Here size_1 size_2 must be positive integral constants.
29 Example The elements of the array

int b[2][3]; are b[0][0], b[0][1], b[0][2], b[1][0]—, b[1][1], b[1][2].
30 Example Here is an example of an initialisation of a 2-dimensional

array:
int b[3][5] = {
{1, 2, 3, 4,5}, //initialises the first row
{6, 7, 8, 9, 10}, //initialises the second row
{11, 12, 13, 14, 15} //initialises the third row

};
Hence, say, b[0][1] is 2, b[1][1] is 7 and b[2][4] is 15.
! If we initialise all the elements of the array, we may omit the internal
braces. Thus the above initialisation is equivalent to
int b[3][5] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,
14, 15};
The first method of initialisation, however, is preferable.
31 Example If
int t[2][3] = {{1, 2}, {3}};
then t[0][2], t[1][1], t[1][2] are all 0.
If the braces delimiting the rows are omitted, a totally different answer may
be obtained.
32 Example In
int t[2][3] = {1, 2, 3};
t[0][0] is 1, t[0][1] is 2, t[0][2] is 3, and t[1][0], t[0][1], t[0][2]

are all 0.
! To prevent any kind of ambiguity from ensuing, prefer the initialisation

style which includes all the braces.
33 Definition A structure is an aggregate of heterogeneous types. The

declaration of a structure has syntax
struct struct_tag {type_1 identifier_1;
type_2 identifier_2;
.
.
.
12 Chapter 1
type_N identifier_N;
}s_instance_1, s_instance_2, ..., s_instance_M;
It is not necessary to attach a tag to the structure.
34 Example Here is an example of a structure declaration

struct Prince { string country;
int rank;
string name;
double dollar_worth;
} Charles, Abdullah, Cuahtemoc;
35 Example Here is an example of an tagless structure declaration

struct {string last_name;
char sex;
int age;
double income;
} Peter, Paul, Mary;
We initialise a given structure the way we initialise arrays, thus for

instance
Paul = {”Whatever”, ’M’, 66, 75001.03};
To access individual fields of a given structure we use the dot . operator.

Thus for instance, we can provide the following initialisations in the above
structure.
Peter.last_name = ”Seager”; Peter.sex = ’M’;
Mary.last_name =”I_dont_remember”; Mary.sex = ’F’;
36 Example We do not need to declare all instances of a given structure

when the structure is declared. Instance declaration can be postponed to
later in the code.

struct terrorist{
...
};
. . . struct terrorist Osama_and_his_Momma,
Ramzi_Rabid_Dog_Yousef;
1.3.3 Constants
37 Definition Constants are tokens representing fixed numeric or charac-

ter values throughout the life of a programme.
C++ constants may be anonymous constants (without identifiers) or con-

stants with identifiers.
38 Example The following are anonymous constants.

12 //int 1.2 //double ’A’ //char "A"
//string 012 //octal int 0x12 //hexadecimal int 1.2e3
//double
A constant with identifier must be declared and initialised at declaration

time. A constant declaration is a statement of the form
const type identifier = fixed_value;
39 Example The following are valid constant declarations

const double conversion_factor = 2.2; const int
weeks_in_a_year = 52; const char sex_of_camel = ’M’; const string
middle_name = ”Anthony”;
! We cannot declare a constant and provide a value for it afterwards.

The following code is illegal.
const double conversion_factor; conversion_factor = 2.2;
//ERROR illegal code
14 Chapter 1
1.4 Input and Output

We will make use of the stream cout for output and the stream cin for
input. These are not commands of C++ properly, they belong to a special
file (the iostream header file).
40 Definition The syntax of the output stream is as follows:

cout << stuff_to_output ;
! The arrowheads << point towards cout, suggesting that stuff_to_output

is going “out.”
41 Example If we want to output the string

Camels of the World: Unite!
we type
cout << ”Camels of the World: Unite!”;
42 Example If we want to output the two separate lines

Camels of the World: Unite!
we type
cout << ”Camels of the World:\nUnite!”;
43 Example The output of the fragment

int a = 5, b = 1; cout << ”The sum a + b ” << a + b <<
”is.”;
is
The sum of a + b 6is.
Notice that there is no space between the “6” and the “i”. Notice that
we did not need quotes around a +b—, since we wanted the computer to
calculate this sum, rather than to output the string a + b.
44 Example A double quote “ character must have a matching double

quote character on the same line. Unmatched double quotes produce
Operators 15
errors.
cout << ”Camels of the World: //ERROR.
Unite!”; //Unmatched double quote.
45 Definition The syntax of the input stream is as follows:

cin >> stuff_to_input ;
Any data to be input must first be declared.
! The arrowheads >> point towards stuff_to_input, suggesting that

what goes “in” is the stuff_to_input.
46 Example The fragment

int a; string b; cout << ”Enter your number of camels: ”;
cin >> a; cout << ”Enter the name of your favourite camel: ”; cin
>> b;
asks the user for an integer variable to be input (which we enter through,
say, the keyboard, and then press ENTER), and then for a string of charac-
ters to be input. The computer does not know that data has been entered
until the ENTER key is pressed.
47 Example The code fragment

int a; cout << ”Enter your number of camels: ”; cin >> a;
cout << ”Enter the name of your favourite camel: ”; cin >> b;
will cause a compiler error. The variable b is called for input, but it has not
been declared.
1.5 Operators
48 Definition An operator is a character, or string of characters, used to
perform an action on some entities. These entities are called the operands.
16 Chapter 1
49 Definition The priority or precedence of an operator is the order by

which it is applied to its operands. Parentheses ( ) are usually used to
coerce precedence among operators. When two or more operators of
the same precedence are in an expression, we define the associativity
to be the order which determines which of the operators will be executed
first. Left-associative operators are executed from left to right and right-
associative operators are executed from right to left.
There are 55 operators in ISO C++, with 18 layers of precedence (17 is the
highest level of precedence, 0 the lowest). Table 1.2 lists some of them.
We will now discuss the operators which we will most use.
1.5.1 Unary Operators

These are the the unary + (plus) sign and the unary − (minus) sign. They
are used to indicate the sign of an integer, a floating point quantity, or the
exponent of the power of 10 in a floating point quantity.
1.5.2 Arithmetical Binary Operators

The usual binary operations of arithmetic may be performed on integers
and floating point numbers: addition, subtraction, multiplication and divi-
sion have the symbols + − ∗ /, and have algebraic precedence rules. As
expected, division by 0 will cause an error.
Integral division, however, truncates the decimal part of the quotient.
For example, 16/3 yields 5 and 20/3 yields 6. If at least one of the
operands is negative, the result is compiler-dependent. Some compilers
choose a/b == ba/bc whilst others choose a/b == da/be. For example,
on some compilers 16/ − 3 == −6 and on others, 16/ − 3 == −5. If we
wish to obtain a decimal value for 16/3 then we must cast at least one of
the numbers into a double.
16.0/3 // or else 16/3.0 // or
else 16.0/3.0 // or else double(16)/3 // or
else 16/double(3) // or else double(16)/double(3)
Operators 17
Symbol Meaning Precedence Associativity

[] Array Index 16 Left
(type) type casting 16 Left
sizeof size in bytes 16 Left
++ Post-increment 16 Right
-- Post-decrement 16 Right
++ Pre-increment 15 Right
-- Pre-decrement 15 Right
- Unary Minus 15 Right
+ Unary Plus 15 Right
! Boolean NOT 15 Right
* Contents of 15 Right
& Address of 15 Right
* Product 13 Left
/ Division 13 Left
% Remainder 13 Left
+ Addition 12 Left
- Subtraction 12 Left
< Less than 10 Left
<= Less than or equal 10 Left
> Greater than 10 Left
>= Greater than or equal 10 Left
== Equal to 9 Left
!= Not equal to 9 Left
&& Boolean AND 5 Left
|| Boolean OR 4 Left
? : Conditional 3 Right
= Assignment 2 Right
+= Sum Assignment 2 Right
*= Product Assignment 2 Right
-= Difference Assignment 2 Right
/= Quotient Assignment 2 Right
%= Remainder Assignment 2 Right
, Comma Operator 0 Left
Table 1.2: Some C++ Operators.

18 Chapter 1
50 Example An integer variable initialised as a float, will truncate the

decimal part, losing this information forever. The fragment
int a = 3.14;
cout << ”a = ”
<< a
<< ’\n’ ;
float b;
b = a - 0.14;
cout << ”b = ”
<< b;
will print
a = 3 b = 2.86
There is a further operand on integers: % (read “mod” or “modulo”). Here

a % b gives the remainder of a upon division by b. Again, if at least one of
the operands is negative, the result is compiler dependent, but we always
have
(a/b) ∗ b + a%b is identical to a.
The % operator has the same level of precedence as multiplication or divi-
sion, and it is left-associative.
51 Example 17 % 7 yields 3 since 17 = 2 ∗ 7 + 3. 17 % 5 yields 2 since

17 = 3 ∗ 5 + 2. 17 % 18 yields 17 since 17 = 0 ∗ 18 + 17.
52 Example What will the fragment

int a;
a = 5 * 30 / 4 % 7 + 17 % 4 * 2;
cout << ”a = ” << a;
print?
Solution: Simplify each term:
5 ∗ 30/4%7 = (5 ∗ 30)/4%7 = (150/4)%7 = 37%7 = 2
and
17%4 ∗ 2 = (17%4) ∗ 2 = 1 ∗ 2 = 2.
Operators 19
Therefore the fragment will print a = 4.
1.5.3 Assignment Operators

53 Definition The assignment operator = is used to indicate that what is to
the left of it acquires the value to the right of it.

int a = 4; cout << ”a = ” << a << ”.”; a = a + 19; cout <<
”\na = ” << a << ” now.”;
will print
a = 4. a = 23 now.

int a = 4; cout << ”a = ” << a << ”.”; a = a + 19; cout <<
”a = ” << a << ”.”; a = 2*a - 1; cout << ”a = ” << a << ”.”;
will print
a = 4. a = 23. a = 45.
! The assignment operator = does not test for equality. To test for equal-
ity, C++ uses the equality comparison operator ==.
56 Example The following code exchanges two declared variables.

temporary_variable = first_variable; first_variable =
second_variable; second_variable = temporary_variable;
! The following code fragment will not work. Why?

// False swapping: will not work!
x = y;
y = x;
20 Chapter 1
57 Example The following code fragment swaps variables a and b without

the need to introduce a temporary variable
a = a + b;
b = a - b;
a = a - b;
58 Definition An lvalue (left-value) is a storage area (memory location)

bound to a variable during the programme execution.
59 Definition An rvalue (right-value) is the encoded value stored in the lo-

cation associated with the variable.
60 Example Algebraic combinations of variables containing operators

cannot occur on the left hand side of an assignment operator, i.e., are not
lvalues. Thus
int x = 4, y; //OK, x and y are lvalues x + 1 = 5;
//ERROR, x + 1 is not an lvalue x + y = x //ERROR, x + y is
not an lvalue
61 Example The = operator has right associativity, meaning that in a

statement containing several = operators, we start by reading the
rightmost one. The following multiple assignment assigns the constant 3
to each of i, j, k.
int i = 1, j = 2, k = 4; // i is 1, j is 2, k is 4 i =
j = k = 3; //Now i, j, k are all 3.
62 Example Multiple assignments, however, cannot occur in declarations.

The following code is incorrect.
int i = j = k = 3; //ERROR, multiple assignment in
declaration.
The correct declaration is

Operators 21
int i = 3, j = 3, k = 3;
C++ has several combined assignment operators:

a += expression; // means a = a + expression; a -=
expression; // means a = a - expression; a *= expression; // means
a = a * expression; a /= expression; // means a = a / expression;
a %= expression; // means a = a % expression;
! There is no whitespace between the two consecutive characters form-

ing combined assignment operators.
63 Example The value of k changes as indicated in the commented code.

int k = 9; k += 10; // k becomes 19 k -=
3; // k becomes 16 k /= 8; // k becomes 2
64 Example What is the value of x after executing the following piece of

code?
int x = 1, y = 3, z = 5; x += y -= z *= -2;
Solution: Since assignment operators are right-associative, first, the value

of z becomes z == 5 ∗ (−2) == −10. Next, y == 3 − (−10) == 13. Finally,
x == 1 + 13 == 14.
65 Example Though a variable may not be declared more than once in

any given block, the same identifier for a variable can be used in different
blocks. If two blocks are nested, a new declaration in the inner block
hides the declaration in the outer block. If two blocks are disjoint,
declarations are independent of one another. In the following three
blocks, there are three declarations of the variable a.
{//opens block I int a = 1; //the a of block I
{//opens block II
int a = 2; //hides the a in block I
a *= 8; //the a in block II now becomes 16
}//closes block II
a += 4; //the a in block I becomes 5
22 Chapter 1
{//opens block III

a += 2;//the a in block I is visible, and becomes 7
int a = -9;//hides the a’s in blocks I and II
a *= 2;//the a in block III now becomes -18
}//closes block III
a -= 8; //the a in block I becomes -1. }//closes block I
Two rather peculiar operators of C++ are the ++ pre-increment/post-

increment and the −− pre-decrement/postdecrement operators.
The post-increment and post-decrement operators work as follows. Sup-
pose x is a numerical real number variable and x++ (or x−− ) is encoun-
tered. Then the operation where x++ (or x−−) was involved is performed
first, and upon leaving the statement, the value of x is increased (de-
creased in the case of −−) by 1. These operators have higher precedence
than the arithmetic operators.
66 Example Find the values of a, b, c, and d after execution of the

following code.
int a, b , c = 3, d = -7; a = c++ * d ; // line 1 b =
(c++) + d++; //line 2 a *= a++; //line 3
Solution: On line 1, c == 3, d == −7 and so a == −21. Observe that c

now is incremented to 4 upon leaving the statement. On line 2, c == 4 and
d == −7, so b == −3. Observe that upon leaving line 3, c == 5 and d ==
−6. On line 3, a == −21, and it becomes a == (−21) ∗ (−21) == 441. a is
incremented upon leaving the statement, and finally, a == 442. Therefore
a == 442, b == −3, c == 5, d == −6.
67 Example Post-increment operators may not be on the left hand side of

an assignment operator, i.e., are not lvalues. The following code will
produce a compiler error.
int a = 8; a++ *= 9; // ERROR
This is because the above is interpreted as a + 1 *= 9;, and a + 1 is not

a memory location. Notice that the written expression is not equivalent to
int a = 8;
Operators 23
a *= 9;
a++;
which is a perfectly legitimate expression.
68 Example Similarly, an expression like 3++; will produce a compiler er-

ror.
69 Example Oddly enough, pre-increment operators are lvalues. An ex-

pression like ++a *= 9; is interpreted as ++a; a *= 9;.
70 Example Find the final value of a after execution of the fragment

int a = 8; (++a)++;
Solution: First the value of a is increased to 9, and upon leaving the state-
ment is increased to 10. Thus a == 10.
71 Example The following code will produce a compiler error. Why?

int a = 8; ++a++;
Solution: Since the post-increment operator has higher precedence than

the pre-increment operator, the fragment ++a++ is equivalent to ++(a++).
This means that this code is equivalent to the following.
int a = 8; a++ = (a++) + 1; Since post-increment operators cannot be
on the left hand side of an assignment, the compiler will produce an error.
C++ code can get really perverse due to the fact that most of times
white space is ignored. Consider the following example.
72 Example Find the values of a, b, c after execution of the fragment int

a, b = 2, c = 9; a = b+++c;
Solution: We have three + signs in a row. Thus there is an increment

operator and an addition (and why not an increment operator and a unary
+?). Is the increment operator pre-increment or post-increment? That is,
do we have (b++) + c or b + (++c)? The compiler will choose (b++) +
c, processing as many characters as can possibly be combined into an
operator token. So we end up with a == 11, b == 3, c == 9.
24 Chapter 1
! C++ grammar does not define the order of evaluations of expressions

involving multiple increment and decrement operators, and hence, the use
in expressions like the following should be avoided.
int x, n = 6; x = ++n * (--n) + ++n; //UGLY! avoid writing
code like this
1.5.4 Relational Operators

The relational operators <, <=, >, >=, ==, ! = evaluate to 1 if the relation
is true and to 0 if the relation is false. The operator != is read “not equal
to.”
73 Example In the fragment
int x = 1, y = 4, z, w, a;
z = x < y ;
w = (x + 5) <= y;
a = y != 5;
z becomes 1 since x < y is true. w becomes 0 since (x + 5) < = y is

false. Finally, a becomes 1 since y!=5 is true.
1.5.5 Logical Operators

The logical negation operator ! gives output according to the following
rules:
!1 gives 0 !0 gives 1
The logical AND operator && gives output according to the following rules:
1 && 1 gives 1 1 && 0 gives 0 0 && 1 gives 0 0 && 0 gives 0
Notice the similarity between this operator and regular multiplication by 0.

The logical OR operator || gives output according to the following
rules:
1 || 1 gives 1 1 || 0 gives 1 0 || 1 gives 1 0 || 0 gives 0

Operators 25
Notice the similarity between this operator and regular addition to 0.

A value different from 0 will be interpreted as 1 by these operators.
74 Example The fragment of code

int a = -1, b = 3, x, y, z, w, r, s; x = a && b; y = (a +
1) || b; z = (a + 1) && (b - 3); w = (a!=b) && (a <= 0); r = (a <
b) || (y==0); s = !b;
will produce x==1, y==1, z==0, w==1, r==1, and s==0.
1.5.6 Conditional Operator
C++’s only ternary operator is the conditional operator ?: which has the
following syntax
test ? alternative_1 : alternative_2
and evaluates as follows. test is evaluated first. If it is true, then the whole
expression becomes alternative_1, and alternative_2 is not evaluated
at all. If test is false, alternative_1 is skipped, and the whole expression
becomes alternative_2.
int a = 3, b = 6, c;
c = (a==b) ? (a + 1) : (b - 8);
c becomes -2, since a==b is false and so the conditional expression as-
sumes the second alternative b-8.

int_1 >= int_2 ? int_1 : int_2
gives the maximum of int_1 and int_2.
26 Chapter 1
1.5.7 Comma Operator

The comma , operator takes its arguments and evaluates them from left
to right and returns the value of the rightmost expression.
int a = 1, b;
b = (a += 1, a += 2, a + 5);
the comma operator first evaluates a+=1 which makes a == 2. The next
expression a+=2 is evaluated and so a == 4. Finally, the last expression
a + 5 is evaluated becoming a + 5 == 9. Hence b == 9.
1.6 Pointers
C++ allows the address of a variable to be accessed through the contents
of another variable.
78 Definition A pointer is a variable which contains the address of another

variable.
Pointers are declared by means of the following syntax:

type *identifier;
This creates a variable, identifier, which holds the address (“points to”)
of another variable of the same type.
! The above declaration is equivalent to the following, where the * is

closer to the type rather than identifier:
type* identifier;
and to the following, where there is whitespace around *:

type * identifier;
Pointers 27
We will prefer the first way of declaring pointers, as the latter two forms
suggests to some, quite erroneously, that the * distributes over the
identifiers. In fact, if more than one pointer is declared on the same
statement, each identifier must be given an *. For example, in
type *identifier_1, identifier_2; type *identifier_3,
*identifier_4;
identifier_2 is not a pointer, but both identifier_3 and identifier_4,

are pointers.
When a pointer is declared of a given type, its initialisation is with the
address of a previously declared variable of the same type. Pointers are
initialised as follows:
type identifier_2; ...... ...... type *identifier_1 =
&identifier_2;
If a pointer is first declared and then an address assigned to it, the

syntax is as follows:
type *identifier _1, identifier_2;

identifier_1 = &identifier_2;
! Memory locations are allocated at compile time, and thus are fixed.
Therefore, a variable which is not declared as a pointer cannot be given the
address of another variable, since a variable may be modified.
79 Example There are some mistakes in the following code: float a, *b

= &a, *c, d; // OK, b points to an existing
object a int *k = &j, j, q;//ERROR, k is pointing to something
undeclared char *x, y, z; c = &d; //OK, *c and d are of the same
type. *x = &q; //ERROR, *x and q are not of the same type y = &z;
//ERROR, a non-pointer variable cannot hold an address
If a variable points to a second variable, we may access the contents of

the second variable indirectly, by means of the dereference (“contents of”)
operator asterisk *.
28 Chapter 1
80 Example Consider the following code.

int x, *y = &x; // y holds the address of x x = 10;
// *y == x == 10 *y += *y; // x == *y == 20
81 Example What is the error with the following piece of code?

float *p ; *p = 2.2;
Solution: p has not been initialised, it is not pointing to any variable, and
hence, it cannot modify the contents of this variable by inserting the value
2.2.
1.7 Functions
Fragments of code that need to be recycled can be put into functions.
In mathematics, a function is composed of 5 elements: (1) a name, (2) a
rule, (3) the name of a typical input, (4) a domain, and (5) a target set.
Thus a function has the form
A → B
f: ,
x 7→ f(x)
where f is the name of the function, x the name of a typical input,

x 7→ f(x) the assignment rule, A is the domain, and B is the target set
(range). In C++ an analogous situation arises. The declaration of a
function f has the form
target_set f(domain).
The domains and target set must come from an available type.
82 Definition A function declaration has the form

type function_identifier(type var_1, type var_2, ..., type
var_N);
83 Example An example of a function declaration is

double Area_of_Triangle(double s_1, double s_2, double
s_3);
Functions 29
The same can also be accomplished with the declaration

double Area_of_Triangle(double , double , double );
the parameters s_1, s_2, s_3, being dummy.
84 Example Another example of a function declaration (with initialisation)

is
bool g_camel(string name = ”Kabubi”, double height, int
humps = 1);
85 Example A perfectly legal function is

void nothing();
which receives no input and returns no output.
86 Definition A function definition has syntax

type function_identifier(type var_1, type var_2, ..., type
var_N)
{
body_of_function
return some_value ;
}
The return is optional.
87 Example Here is a function which determines the maximum of three

integers a, b, c.
int maximum_of_3(int a, int b, int c)
{
return (a >= b ? a : b) >= c ? (a >= b ? a : b) : c;
}
88 Example Here is a function which determines whether three given

lengths can form a triangle
bool is_triangle(double a, double b, double c)
{
30 Chapter 1
return !(a + b <= c || a + c <= b || b + c <= a);

}
It returns 1 (true) if the lengths do form a triangle and 0 (false) otherwise.
89 Example Here is a function which finds the area of a triangle upon

been fed the lengths a, b, c, of its three sides.
double Area_of_Triangle(double a, double b, double c) {
return .25*sqrt((a + b + c)*(b + c - a)*(c + a - b)*(a + b - c));
}
It uses Heron’s formula

1p
Area =
p
s(s − a)(s − b)(s − c) = (a + b + c)(b + c − a)(c + a − b)(a + b − c),
4
where
a+b+c
s=
2
is the semi-perimeter of the triangle. It also uses the square root function
sqrt(), which is found in the cmath header file.
90 Example Here is a function which prompts the user to enter the radius
of a circle
void prompt_radius()
{
cout << ”Please enter the radius of a circle: ”;
}
91 Example Here is a function which reads the radius of a circle entered

by a user
double read_radius()
{ double r;
cin >> r;
return r;
}
Functions 31
92 Example Here is a function which finds the area of a circle upon been
fed its radius
double Area_of_Circle(double radius)
{
const double PI = 3.14159;
return PI*radius*radius;
}
93 Example Here is a function which prints the area of a circle upon been
fed with it.
void print_area_of_circle(double Area)
{
cout << ”Area of circle is ” << Area;
}
1.7.1 main() Function

All C++ programmes must have a function main(){}. Its definition is
int main(int argc, char *argv[])
{
body
return 0;
}
The value 0 returned by main(){} means that everything has gone well.
The optional programme parameters argc and *argv[] are run from the
command line.
94 Example The smallest syntactically correct C++ programme, is

int main()
{
return 0;
}
32 Chapter 1
This is a completely useless programme, as it does nothing.
1.7.2 Function Calls

Functions called within the body of main(){} must be declared before
they are called. This can be accomplished in two ways.
• We can define the functions before main(){}.
• We can declare the functions before main(){} and then define them
after main(){}.
An example is in order. Suppose we want to write a programme that calls

the user to input the radius of a circle and then outputs the area of the
circle (in square units). We will use the functions of examples 90 through
93 in order to illustrate both
95 Example Here is the programme, using the first style.

void prompt_radius() {
} double read_radius() {
double r;
cin >> r;
return r;
} double Area_of_Circle(double radius) {
} void print_area_of_circle(double Area) {
} int main() {
prompt_radius();
print_area_of_circle(Area_of_Circle(read_radius()));
return 0;
}
96 Example The second style yields the following code.

void prompt_radius(); double Area_of_Circle(double
Functions 33
radius); double read_radius(); double Area_of_Circle(double

radius); void print_area_of_circle(double Area); int main() {
prompt_radius();
print_area_of_circle(Area_of_Circle(read_radius()));
return 0;
} void prompt_radius() {
} double read_radius() {
double r;
cin >> r;
return r;
} double Area_of_Circle(double radius) {
} void print_area_of_circle(double Area) {
}
For the (tiny) C++ programmes that we will see in these notes we will
prefer the first style of writing programmes.

int foo(int a){return 2*a;} int main() { int b, c = 7; b =
foo(c); cout << ”b = ” << b << ” and c = ” << c; return 0; }
will print b = 14 and c = 7.
98 Example The scope rules seen in example 65 hold within the bodies of
functions. The fragment
int a = 17, b = -3; int foo(int c)
{
int b;
b = 2*c + a;
cout << ”II: within foo, a = ” << a << ”, b = ”
<< b << ”, and c = ” << c << ’\n’;
return b;
}
34 Chapter 1
void faa(void)
{
int c = b*a;
cout << ”III: within faa, a = ” << a << ”, b = ”
<< b << ”, and c = ” << c << ’\n’;
}
int main() { int a = -5, c = 7; a = foo(c); cout <<”I: within
main, a = ” << a << ”, b = ”
<< b << ”, and c = ” << c << ’\n’;
faa(); return 0; }
will print
II: within foo, a = 17, b = 31, and c = 7 I: within main,
a = 31, b = -3, and c = 7 III: within faa, a = 17, b = -3, and c =
-51
1.7.3 Parameter Passing

In example 65 we saw how blocks can hide information from other blocks.
Thus if a variable is to be processes by different functions, it must be
external to these functions and it must be declared before these functions
are defined.
99 Definition When a variable is passed to a function, a new copy of the

original variable is made and it is this copy what the function processes.
The original value is unaffected. This is called passing by value.

int f(int a){a += a; return a;} int main() {
int i = 3;
cout << ”f(i) = ”<< f(i) << ” and i = ” << i;
return 0;
}
Functions 35
will print f(i) = 6 and i = 3, that is, even though the value of i suffered
changes within f(), it was not altered by f().
We see then that simply passing the value of a variable to a function does
not change the contents of the variable. In order to change the contents
of the variable, we must pass the address of the variable rather than it
contents. This is called passing by reference.

int foo(int a) { a = 5;
cout << ”Within foo, a = ” << a << ’\n’;
return 0;
} int faa(int *x) { *x = 5;
cout << ”Within faa, a = ” << *x << ’\n’;
return 0;
} int main() {
int a = 18;
cout << ”Printing I in main, a = ” << a << ’\n’;
foo(a);
cout << ”Printing II in main, a = ” << a << ’\n’;
faa(&a);
cout << ”Printing III in main, a = ” << a << ’\n’;
return 0;
}
will print
Printing I in main, a = 18 Within foo, a = 5 Printing II
in main, a = 18 Within faa, a = 5 Printing III in main, a = 5
102 Example The code following code fragment contains two functions
which purportedly exchange the values of two variables.
int swap_bad(int x, int y) {
int temp;
temp = x;
x = y;
y = temp;
36 Chapter 1
cout << ”Within swap_bad first_var = ” << x << ” and second_var

= ” << y << ’\n’;
return 0;
} int swap_good(int *x, int *y) {
int temp;
temp = *x;
*x = *y;
*y = temp;
cout << ”Within swap_good first_var = ” << *x << ” and
second_var = ” << *y << ’\n’;
return 0;
} int main() {
int first_var = 1, second_var = 2;
cout << ”I: in main first_var = ”
<< first_var
<< ” and second_var = ”
<< second_var << ’\n’;
swap_bad(first_var, second_var);
cout << ”II: in main first_var = ”
<< first_var
swap_good(&first_var, &second_var);
cout << ”III: in main first_var = ”
<< first_var
return 0;
}
will print
I: In main first_var = 1 and second_var = 2 Within
swap_bad first_var = 2 and second_var = 1 II: In main first_var =
1 and second_var = 2 Within swap_good first_var = 2 and second_var
= 1 III: In main first_var = 2 and second_var = 1
if{}else{} Statement 37
1.8 if{}else{} Statement

103 Definition The if...else control statement has the following syntax
if (expression)
{statement_1;}
else
{statement_2;}
and evaluates as follows. If expression is true then statement_1 is

executed. Otherwise statement_2 is executed.
104 Example In the following programme segment

int a = 3;
if (a < 1 || a > 4)
b = 5;
else
b = 4;
the value of b will be 4, since the test produces a true result.
105 Example The following programme segment

int a = 0;
if (a=0)
cout << ”Aha!”;
will not print anything. a=0 is not a test, it is an assignment, and so this is
equivalent to if(0). The programmer perhaps meant to write
int a = 0;
if (a==0)
cout << ”Aha!”;
This is a fairly common programming error. Again, the programme

segment
int a = 45;
if (0 < a < 5) //ERROR
38 Chapter 1
cout << ”The number is in the right range.”;

else
cout << ”The number is not in the right range.”;
will erroneously print The number is in the right range. This is

because the compiler will first evaluate 0<a giving 1, then it will evaluate
1< 5 giving 1 again. Thus the test evaluates to true. The intended code is
rather
int a = 45;
if (0 < a && a < 5)
cout << ”The number is in the right range.”;
else
cout << ”The number is not in the right range.”;
106 Example The logical AND and the logical OR have a short-circuiting
property that it is at times rather useful. If the first argument in a && b is
0, then b is not evaluated and the output of a && b is 0 no matter what b
might be. Similarly, if the first argument in a || b is 1, then b is not
evaluated and the output of a || b is 1 no matter what b might be. For
example, the programme segment
int a = -3, b = 0;
if ((a + 3) && a/b)
will not cause division by 0, as the test will be short-circuited because a+3
evaluates to 0.
107 Example Care must be exercised with the grouping. C++ ignores
indentation. The fragment
int a = 4, b = 5;
if (a < 3)
b = 7;
a = a + b;
cout << ”a = ” << a;
if{}else{} Statement 39
will print a = 9, whereas the fragment

int a = 4, b = 5;
if (a < 3)
{b = 7;
a = a + b;}
cout << ”a = ” << a;
will print a = 4.
! In the case of nested if...else constructs, an else matches the

most recent if in the same block that does not have its own else, unless
coerced by means of braces to do otherwise.
108 Example What is the value of c at the end of the following code
fragment?
int a=0,b=1,c=2;
if(a) if(b) c=3;
else c=4;
Solution: First notice that both ifs are in the same block and hence the
else belongs to the nearest if, that is, to if(c) k=3;. Thus this fragment
can be written as
int a=0,b=1,c=2;
if(a) {if(b) c=3; else c=4;}
Now the test in if(a) is false, hence control is passed after the brace.
This means that c has not changed at all, and hence c==2.
109 Example What is the value of c at the end of the following code
fragment?
int a=0,b=1,c=2;
if(a) {if(b) c=3;}
else c=4;
40 Chapter 1
Solution: In this case the else does not to belong to the same block as
if(b), but it is in the same block as if(a), and so it belongs to it. The
test in if(a) evaluates to false and hence control is passed to the else.
This makes c==4.
1.9 switch{} Statement

C++ provides a way to avoid repeated if...else statements.
110 Definition The switch statement has the syntax

switch(condition)
{
case constant_1: option_1; break;
case constant_2: option_2; break;
.
.
.
case constant_N: option_N; break;
default : default_option; break;
}
Here condition must be of int or char type, or a related type that can be
converted into one of these two. The cases must all be different. If one of
the cases is met, its option is executed and the control is passed to the
closing brace. If break; does not appear in a case, the next case will be
executed. The default statement is optional, and only one default
statement is allowed.

int a = 2, b = 2;
switch(b)
{
case 1: a = -1; break;
case 2: a = 0; break;
}
cout << ”a = ” << a;
switch{} Statement 41
will print a = 0.

int a = 2, b = 2;
switch(b)
{
case 2: a = 0;
}
cout << ”a = ” << a;
will print a = 1. This is because case 2: is met, it assigns 0 to a. Since

there is no break; control is passed to the next case, which assigns 1 to
a.

int a = 2, b = 0;
switch(b)
{
}
cout << ”a = ” << a;
will print a = 2, as there is no case for b equaling 0, so the body of the

switch statement does not modify a.

int a = 2, b = 0;
switch(b)
{
42 Chapter 1
default: a = 27;
}
cout << ”a = ” << a;
will print a = 27.

int a = 3, b = 1, c = 1;
switch(c)
{
case (a - b): a = -1; break;
default: a = 27;
}
cout << ”a = ” << a;
is incorrect. This is because a - b is not a constant.

int a = 3, b = 2,;
switch(b)
{
case (1||2): a = -1; break;
default: a = 27;
}
cout << ”a = ” << a;
will print a = 27. This is because 1||2 evaluates to 1.
1.10 for(){} Loop

117 Definition The for() loop has syntax
for(initial_condition; test_condition ; loop_changes )
{body of loop}
for(){} Loop 43
Any of the parts in a for loop may be omitted. Here we start with the initial
condition. It if meets the test condition, the body of the loop is executed
and then the loop changes. This procedure goes on until the test
condition evaluates to false.
118 Example The code
int a = 2, b = 5, i;
for(i = 3; i < 8; i += 2, b--)
{//opens body of for
a += b;
cout << ”a is ”
<< a
<< ”, b is ”
<< b << ”, and i is ”
<< i << ’\n’;
}//closes body of for
will print
a is 7, b is 5, and i is 3 a is 11, b is 4, and i is 5 a
is 14, b is 3, and i is 7
We start with i == 3. We test whether i < 8, which is true. The body of
the loop is executed and we get a == 7. The loop changes are executed
and we get i == 5 and b == 4. We test again i < 8, which is true. The
body of the loop is executed and we get a == 11. The loop changes are
executed and we get i == 7 and b == 3. We test whether i < 8, which is
true. The body of the loop is executed and we get a == 14. The loop
changes are executed and we get i == 9 and b == 2. We test whether
i < 8, which is false. We stop.
119 Example The code in example 118 could have been written as
int a = 2, b = 5;
for(int i = 3; i < 8; i += 2, b--)
{//opens body of for
a += b;
cout << ”a is ”
<< a
44 Chapter 1
<< ”, b is ”
<< b << ”, and i is ”
<< i << ’\n’;
}//closes body of for
This fragment will execute as in 118, but there is a subtle difference. In

118 the variable i is available for later use, as it is not local to the block in
the for loop. In this second case, some compilers will not make i
available for later use.
120 Example Here is a rudimentary calculation of n!.

long int n;
cout << ”Enter a positive integer: ” ;
cin >> n;
int factorial = 1;
for(int i=1; i <= n; i++) factorial = factorial*i;
cout << n <<”! is ” << factorial << ’\n’;
Since these numbers grow rather fast and memory space is scarce, my
system is only able to calculate up to 16! accurately.
1.11 while(){} Loop

121 Definition The while() loop has syntax
while(test)
{body_of_loop}
The commands in the body of the loop will be executed as long as the
test evaluates to true.

int a = 10, b = 4;
while(a - b)
{
a--; b++;
cout << ”a is ” << a << ” and b is ” << b << ’\n’;
Examples of Full Programmes 45
will print
a is 9 and b is 5 a is 8 and b is 6 a is 7 and b is 7
! Had we written
int a = 10, b = 3;
while(a - b)
{
a--; b++;
cout << ”a is ” << a << ” and b is ” << b << ’\n’;
}
we would have obtained an infinite loop. In general while(1) will produce

an infinite loop.
123 Example for( ; ; ) produces an infinite loop.
1.12 Examples of Full Programmes

We are now ready to write complete C++ programmes. The programmes
here are rather elementary and do not exploit the full capabilities of the
C++ language. I wrote these programmes in a hurry, so if you discover
bugs, please tell me. Remember that in a cout line there must be
matching double quotes. If they don’t match in the presentation here, it is
because of the idiosyncracies of LaTeX. I will improve these programmes
some time in the future.
124 Example Write a programme that reverses the digits of a positive

integer. The programme must prompt the user for a series of integers,
one integer at the time. The programme will stop when the user enters a
negative integer or 0.
Solution: We use use to our advantage that division of a positive integer

will truncate the decimal part of a quotient, and so, effectively,
46 Chapter 1
copy_int_input/10 truncates the last digit of copy_int_input. We create

the following functions: (1) a function that prompts the user for input or to
stop, (2) a function reading the input, (3) a function reversing the digits of
the integer. The programme will then will resemble the one below.
//digit_reversal.cpp
#include <iostream> using namespace std; void prompt_user()
{//opens prompt_user
cout << ”\nLet\’s reverse the digits of a positive integer.\n”;
cout << ”Enter a positive integer.\n”;
cout << ”Enter 0 or a negative integer to stop: ”;
}//closes prompt_user
int read_input()
{//opens read_input
int a;
cin >> a;
if(a <=0) {//opens if
cout << ”You have decided to quit. Good Bye.\n”;
return 0;
}//closes if
else return a;
}//closes read_input
int reverse(int b)
{//opens reverse
int x = 0;
while (b)
{//opens while
x = x *10 + b % 10; //x accumulates the truncated digit
b = b/10; //truncates a digit of the input integer
}//closes while
return x;
}//closes reverse
int main()
{//opens main
prompt_user();
int input_var = read_input();
while(input_var)
{//opens while
cout << input_var
<< ” reversed is ”
<< reverse(input_var);
prompt_user();
input_var = read_input();
}//closes while
return 0;
} //closes main
The directive \#include <iostream> loads the input-output class library,

where the stream cout is defined. It instructs the compiler to replace the
line #include <iostream> with the contents of the header file iostream.h
Each #include directive requires its own line. For example, you cannot
write \#include <iostream> using.
The statement using namespace std; localises the name of the
directives and functions making reference to them easier. All statements
must end in semicolon.
125 Example Recall that a positive integer p > 1 is a prime if its only
positive integral divisors are 1 and p itself. The series of primes goes thus
like 2, 3, 5, 7, 11, 13, 17, 19, 23, . . .. Write a programme determining whether
a given integer is a prime.
Solution: Our input will only accept positive integers. Observe that 2 is
the only even prime. Thus we test the input integer to see whether it is 1 (
which is neither prime nor composite), 2 (which is a prime), or an even
number greater than 2 (in which case the number is composite). If neither
of these applies, then the number, call it p, is odd and greater than 1. We
then divide p by every odd integer up to p − 2. If p is not divisible by any
of these integers, then p must be prime. Observe that this algorithm
makes about p/2 tests. In the Number Theory Chapter we will see that
√
the same algorithm used here only requires about p tests.
//rudimentary_primality.cpp
#include <iostream> using namespace std; void prompt_user()
{//opens prompt_user
cout << ”\nLet\’s test the primality of a positive integer.\n”;
cout << ”Enter a positive integer.\n”;
cout << ”Enter 0 or a negative integer to stop: ”;
}//closes prompt_user int read_input() {//opens read_input
48 Chapter 1
int a;
cin >> a;
if(a <=0){cout << ”You have decided to quit. Good Bye.\n”;
return 0;}
else if (a==1) {cout << a
<< ” is neither prime nor composite.\n”;
return a;}
else if (a==2) {cout << a << ” is prime.\n”; return a;}
else if (a%2 == 0) {cout << a << ” is an even
number.\n” ; return a; }
else return a;
}//closes read_input void primality_test(int p) {//opens
primality_test
if(p%2!=0) {// opens if(p%2!=0)
bool flag = true;
for(int i=3; i < p; i += 2) if (p%i ==0) {flag = false;
break;}
if (flag) cout << p << ” is prime.\n” << ’\n’;
else cout << p
<< ” is not prime.”
<< ” Its smallest prime factor is ”
<< i << ’\n’;
}//closes if(p%2!=0)
}//closes primality_test int main() {//opens main prompt_user();
int input_var = read_input(); while(input_var)
{//opens while
primality_test(input_var);
prompt_user();
input_var = read_input();
}//closes while
return 0; }//closes main
126 Example The programme

#include <iostream> #include <cstdlib> #include <ctime>
using namespace std; void prompt_user() {//opens prompt_user
cout << ”\nLet\’s play PAPER, ROCK, or SCISSORS.\n”;
cout << ”Enter \’P\’, \’R’, or \’S\’.\n”;
cout << ”Enter \’Q\’ to stop: ”;
}//closes prompt_user char user_input() {//opens user_input

char a;
bool flag;
do{ cin >> a;
flag=false;
if(!(a ==’P’ || a == ’p’ || a == ’R’ || a == ’r’ || a ==
’S’ || a == ’s’ ||
a == ’Q’ || a == ’q’)){flag = !flag; cout <<”Unrecognised
choice. Try again.\n”; prompt_user();}
else break;
}
while(flag);
if(a == ’Q’ || a == ’q’ ) {cout << ”You have decided to quit.
Good Bye.\n”; exit(1);}
else switch(a)
{case ’p’: return ’P’; break;
case ’P’: return ’P’; break;
case ’r’: return ’R’; break;
case ’R’: return ’R’; break;
case ’s’: return ’S’; break;
case ’S’: return ’S’; break;
}
}//closes user_input char computer_input()
{//opens computer_input
srand(time(NULL));
switch((rand() % 3))
{
case 0: return ’P’; break;
case 1: return ’R’; break;
case 2: return ’S’; break;
}
}//closes computer_input
void decide_winner(char computer, char user) { if(computer==user)
{cout << ”Computer picked ” << user << ” too! It is a
tie!\n”;}
else if ((user == ’P’ && computer == ’S’)
|| (user == ’S’ && computer== ’R’)
|| (user==’R’ && computer== ’P’) )
50 Chapter 1
cout << ”Computer picked ” << computer << ”

against your ” << user << ”. Computer wins.”;
else cout << ”Computer picked ” << computer << ”
against your ” << user << ”. User wins.”;
}
int main()
{//opens main
int user_choice, comp_choice;

while(1)
{prompt_user();
comp_choice = computer_input();
user_choice = user_input();
decide_winner(comp_choice, user_choice);
}
return 0;
}//closes main
simulates the game “PAPER, ROCK, SCISSORS.” The user plays against
the computer, which prompts him for an option of these three and
produces its random choice (the computer does not cheat!). The function
rand() resides in the header file cstdlib and produces a pseudo-random
integer. In order to further randomise the computer choice, we put a
time-dependent seed via the instruction srand(time(NULL));. Since we
only have three choices, we reduce num_equiv_comp modulo 3 to produce
a random integer in the set {0, 1, 2}.
127 Example Write a programme where the user inputs three numerical
real number coefficients a, b, and c and then solves the equation
ax2 + bx + c. If the equation is quadratic, it must provide for the cases
when the roots are complex. If the equation is linear, it must tell the user
that it is a linear equation. If the equation is degenerate, it must tell the
user so.
Solution: One possible solution is the following.

//solving_quadratics.cpp
#include <iostream>
#include <cmath>
using namespace std;
int main()
{ //opens main
double a, b, c, discriminant;
cout << ”Enter a first coefficient: ”;
cin >> a;
cout << ”\nEnter a second coefficient: ”;
cin >> b;
cout << ”\nEnter a third coefficient: ”;
cin >> c;
discriminant = b*b - 4*a*c;
if (a==0 && b==0)
cout << ”\nThe equation axˆ2 + bx + c = 0 is
degenerate.” << ’\n’;
else if (a==0 && b!=0)
{ //opens linear
linear.”;
cout << ”\nIt has a unique root x = ” << -c/b <<
’\n’;
} //closes linear
else
{ //opens quadratic
quadratic.”;
if (discriminant < 0)
{ //opens complex
cout << ”\nIt has two complex roots: x_1 = ”
<< -b/(2*a)
52 Chapter 1
<< ” + i”
<< sqrt(-discriminant)/(2*a);
cout << ” and x_2 = ”
<< -b/(2*a)
<< ” - i”
<< sqrt(-discriminant)/(2*a) << ’\n’;
} //closes complex
else
{ //opens real
cout << ”\nIt has two real roots: x_1 = ”
<< (-b + sqrt(discriminant))/(2*a);
cout << ” and x_2 = ”
<< (-b - sqrt(discriminant))/(2*a) <<
’\n’ ;
} //closes real
} //closes quadratic
return 0;
} //closes main
We had to recur to the header file cmath which contains the square root
function. Observe that since we had to use several blocks, we
commented each brace. This is a good practice in general.
128 Example Write a programme where the user inputs three real
numbers a, b, and c and tells whether these numbers form the lengths of
a triangle. If a triangle can be formed with the given input, then it will find
its area by means of Heron’s formula
Area = s(s − a)(s − b)(s − c),

p
where
a+b+c
s=
2
is the semi-perimeter of the triangle. If at a given point the user enters a
non-positive number, the programme should stop then.
Solution: One possible solution is

#include <iostream>
#include <cmath>
int main()
{ //opens main
double a, b, c;
cout << ”Enter a first length: ”;
cin >> a;
if (a<=0) {cout << ”Bad input.\n”; exit(1);}
cout << ”\nEnter a second length: ”;
cin >> b;
if (b<=0) {cout << ”Bad input.\n”; exit(1);}
cout << ”\nEnter a third length: ”;
cin >> c;
if (b<=0) {cout << ”Bad input.\n”; exit(1);}
if (a + b <= c || a + c <= b || b + c <= a)
cout << ”Sorry, these don’t form a triangle.\n”;
else
{//opens area computation
double s = (a + b + c)/2;
cout << ”The area of the triangle is ”
<< sqrt(s*(s - a)*(s - b)*(s - c))
<< ” square units.\n”;
} //closes area computation
return 0;
} //closes main
Here the instruction exit(1) causes normal programme termination

when this instruction is reached.
129 Example The following programme converts a decimal hindu-arabic

numeral between 1 and 3999 to a roman numeral.
//arabic_to_roman.cpp
#include <iostream>
#include <string>
int main()
{ //opens main
int input_int;
54 Chapter 1
cout << ”Enter a decimal hindu-arabic number between 1

and 3999: ”;
cin >> input_int;
while(input_int < 1 || input_int > 3999)
{ //opens input-prompting while
cout << ”Sorry, wrong input, try again.\n”;
cout << ”Enter a decimal hindu-arabic number between 1
and 3999: ”;
cin >> input_int;
}//closes input-prompting while
int copy_input = input_int, a[] = {1000, 900, 500, 400,
100, 90, 50, 40, 10, 9, 5, 4, 1}, r_position = 0;
string roman_conv = ””, r[] = {”M”, ”CM”,
”D”,”CD”,”C”,”XC”,”L”,”XL”,”X”,”IX”,”V”,”IV”,”I”};
for(int a_position = 0; a_position<=12; a_position++,
r_position++)
{while(input_int >= a[a_position]){input_int -= a[a_position];
roman_conv += r[r_position]; }}
cout << ”The roman conversion of ” << copy_input << ” is: ”
<< roman_conv << ’\n’;
return 0;
} //closes main
130 Example A locker room contains 100 lockers, numbered 1 through

100. Initially all are open. An attendant performs a number of operations
T2 , T3 , . . . , T100 whereby with the operation Tk , 2 ≤ k ≤ 100, the condition of
being locked or unlocked is changed for all those lockers and only those
lockers whose numbers are multiples of k. Write C++ code to determine
which lockers remain open.
Solution: Here is one possible solution. Later on in the Number Theory

chapter we will see that only the lockers whose numbers are perfect
squares remain open.
//locker_problem.cpp
#include <iostream>
int main()
{ //opens main
bool locker[101];
//setting every locker open == true.
for(int i = 1; i <= 100; i++) locker[i] = true;
for(int j = 2; j <=100; j++)
{for(int k = 1; k <= 100; k++) if(k % j == 0) locker[k] =
!locker[k]; }
for(int l = 1; l <= 100 ; l++ ) if(locker[l]) cout << ”Locker ”
<< l << ” remains open.\n ”;
return 0;
} //closes main
56 Chapter 1
Chapter 2
Essential Techniques
2.1 Reductio ad Absurdum

In this section we will see examples of proofs by contradiction. That is, in
trying to prove a premise, we assume that its negation is true and deduce
incompatible statements from this.
√ 1
131 Example Show, without using a calculator, that 6 − 35 < .
10
√ 1 1 √ √
Solution: Assume that 6 − 35 ≥. Then 6 − ≥ 35 or 59 ≥ 10 35.
10 10
Squaring both sides we obtain 3841 ≥ 3500, which is clearly nonsense.
√ 1
Thus it must be the case that 6 − 35 < .
10
132 Example Let a1 , a2 , . . . , an be an arbitrary permutation of the

numbers 1, 2, . . . , n, where n is an odd number. Prove that the product
(a1 − 1)(a2 − 2) · · · (an − n)
is even.
Solution: First observe that the sum of an odd number of odd integers is
odd. It is enough to prove that some difference ak − k is even. Assume
1
2 Chapter 2
contrariwise that all the differences ak − k are odd. Clearly
S = (a1 − 1) + (a2 − 2) + · · · + (an − n) = 0,
since the ak ’s are a reordering of 1, 2, . . . , n. S is an odd number of

summands of odd integers adding to the even integer 0. This is
impossible. Our initial assumption that all the ak − k are odd is wrong, so
one of these is even and hence the product is even.
√
133 Example Prove that 2 is irrational.
Solution: For this proof, we will accept as fact that any positive integer
greater than 1 can be factorised uniquely as the product of primes (up to
the order of the factors).
√ a
Assume that 2 = , with positive integers a, b. This yields 2b2 = a2 .
b
Now both a2 and b2 have an even number of prime factors. So 2b2 has an
odd numbers of primes in its factorisation and a2 has an even number of
primes in its factorisation. This is a contradiction.
134 Example Let a, b be real numbers and assume that for all numbers
> 0 the following inequality holds:
a < b + .
Prove that a ≤ b.
a−b
Solution: Assume contrariwise that a > b. Hence > 0. Since the
2
inequality a < b + holds for every > 0 in particular it holds for
a−b
= . This implies that
2
a−b
a<b+ or a < b.
2
Thus starting with the assumption that a > b we reach the incompatible
conclusion that a < b. The original assumption must be wrong. We
therefore conclude that a ≤ b.
135 Example Show that there are infinitely many prime numbers.
Reductio ad Absurdum 3
Solution: We need to assume for this proof that any integer greater than 1
is either a prime or a product of primes. The following beautiful proof
goes back to Euclid.
Assume that {p1 , p2 , . . . , pn } is a list that exhauts all the primes. Consider
the numberN = p1 p2 · · · pn + 1. This is a positive integer, clearly greater
than 1. Observe that none of the primes on the list {p1 , p2 , . . . , pn } divides
N, since division by any of these primes leaves a remainder of 1. Since N
is larger than any of the primes on this list, it is either a prime or divisible
by a prime outside this list. Thus we have shown that the assumption that
any finite list of primes leads to the existence of a prime outside this list.
This implies that the number of primes is infinite.
136 Example Let n > 1 be a composite integer. Prove that n has a prime
factor p ≤ n.
Solution: Since n is composite, n can be written

√ as n =√ab where both
a > 1, b >√ 1 are
√ integers. Now, if both a > n and b > n then
n=√ ab > n n = n, a contradiction. Thus one of √ these factors must be
≤ n and a fortiori it must have a prime factor ≤ n.
The preceding result can be used to test √ for primality. For example, to
show that 101 is prime, we compute b 101c = 10. By the preceding
problem, either 101 is prime or it is divisible by 2, 3, 5, or 7 (the primes
smaller than 10). Since neither of these primes divides 101, we conclude
that 101 is prime.
Ad Pleniorem Scientiam
137 Problem The product of 34 integers is equal to 1. Show that their sum
cannot be 0.
138 Problem Let a1 , a2 , . . . , a2000 be natural numbers such that

1 1 1
+ + ··· + = 1.
a1 a2 a2000
Prove that at least one of the ak ’s is even.
(Hint: Clear denominators.)

4 Chapter 2
139 Problem Prove that log2 3 is irrational.
140 Problem A palindrome is an integer whose decimal expansion is

symmetric, e.g. 1, 2, 11, 121, 15677651 (but not 010, 0110) are palindromes.
Prove that there is no positive palindrome which is divisible by 10.
141 Problem In 4ABC, ∠A > ∠B. Prove that BC > AC.
√
142 Problem Let 0 < α < 1. Prove that α > α.
143 Problem Let α = 0.999 . . . √

where there are at least 2000 nines. Prove
that the decimal expansion of α also starts with at least 2000 nines.
144 Problem Prove that a quadratic equation ax2 + bx + c = 0, a 6= 0 has

at most two solutions.
145 Problem Prove that if ax2 + bx + c = 0 has real solutions and if

a > 0, b > 0, c > 0 then both solutions must be negative.
146 Problem Let a, b, c be odd integers. Prove that ax2 + bx + c = 0

cannot have a rational root.
2.2 Pigeonhole Principle

The Pigeonhole Principle states that if n + 1 pigeons fly to n holes, there
must be a pigeonhole containing at least two pigeons. This apparently
trivial principle is very powerful. Thus in any group of 13 people, there are
always two who have their birthday on the same month, and if the
average human head has two million hairs, there are at least three people
in NYC with the same number of hairs on their head.
The Pigeonhole Principle is useful in proving existence problems, that is,
we show that something exists without actually identifying it concretely.
Let us see some more examples.
Pigeonhole Principle 5
147 Example (P UTNAM 1978) Let A be any set of twenty integers chosen
from the arithmetic progression 1, 4, . . . , 100. Prove that there must be two
distinct integers in A whose sum is 104.
Solution: We partition the thirty four elements of this progression into

nineteen groups
{1}, {52}, {4, 100}, {7, 97}, {10, 94}, . . . , {49, 55}.
Since we are choosing twenty integers and we have nineteen sets, by the
Pigeonhole Principle there must be two integers that belong to one of the
pairs, which add to 104.
148 Example Show that amongst any seven distinct positive integers not
exceeding 126, one can find two of them, say a and b, which satisfy
b < a ≤ 2b.
Solution: Split the numbers {1, 2, 3, . . . , 126} into the six sets
{1, 2}, {3, 4, 5, 6}, {7, 8, . . . , 13, 14}, {15, 16, . . . , 29, 30},
{31, 32, . . . , 61, 62} and {63, 64, . . . , 126}.
By the Pigeonhole Principle, two of the seven numbers must lie in one of
the six sets, and obviously, any such two will satisfy the stated inequality.
149 Example No matter which fifty five integers may be selected from
{1, 2, . . . , 100},
prove that one must select some two that differ by 10.
Solution: First observe that if we choose n + 1 integers from any string of

2n consecutive integers, there will always be some two that differ by n.
This is because we can pair the 2n consecutive integers
{a + 1, a + 2, a + 3, . . . , a + 2n}
into the n pairs
{a + 1, a + n + 1}, {a + 2, a + n + 2}, . . . , {a + n, a + 2n},
6 Chapter 2
and if n + 1 integers are chosen from this, there must be two that belong
to the same group.
So now group the one hundred integers as follows:
{1, 2, . . . 20}, {21, 22, . . . , 40},
{41, 42, . . . , 60}, {61, 62, . . . , 80}

and
{81, 82, . . . , 100}.
If we select fifty five integers, we must perforce choose eleven from some
group. From that group, by the above observation (let n = 10), there must
be two that differ by 10.
150 Example (A HSME 1994) Label one disc “1”, two discs “2”, three discs
“3”, . . . , fifty discs ‘‘50”. Put these 1 + 2 + 3 + · · · + 50 = 1275 labeled discs
in a box. Discs are then drawn from the box at random without
replacement. What is the minimum number of discs that must me drawn
in order to guarantee drawing at least ten discs with the same label?
Solution: If we draw all the 1 + 2 + · · · + 9 = 45 labelled “1”, . . . , “9” and

any nine from each of the discs “10”, . . . , “50”, we have drawn
45 + 9 · 41 = 414 discs. The 415-th disc drawn will assure at least ten
discs from a label.
151 Example (I MO 1964) Seventeen people correspond by mail with one

another—each one with all the rest. In their letters only three different
topics are discussed. Each pair of correspondents deals with only one of
these topics. Prove that there at least three people who write to each
other about the same topic.
Solution: Choose a particular person of the group, say Charlie. He

corresponds with sixteen others. By the Pigeonhole Principle, Charlie
must write to at least six of the people of one topic, say topic I. If any pair
of these six people corresponds on topic I, then Charlie and this pair do
the trick, and we are done. Otherwise, these six correspond amongst
themselves only on topics II or III. Choose a particular person from this
group of six, say Eric. By the Pigeonhole Principle, there must be three of
the five remaining that correspond with Eric in one of the topics, say topic
II. If amongst these three there is a pair that corresponds with each other
on topic II, then Eric and this pair correspond on topic II, and we are
done. Otherwise, these three people only correspond with one another
on topic III, and we are done again.
152 Example Given any set of ten natural numbers between 1 and 99
inclusive, prove that there are two disjoint nonempty subsets of the set
with equal sums of their elements.
Solution: There are 210 − 1 = 1023 non-empty subsets that one can form
with a given 10-element set. To each of these subsets we associate the
sum of its elements. The maximum value that any such sum can achieve
is 90 + 91 + · · · + 99 = 945 < 1023. Therefore, there must be at least two
different subsets that have the same sum.
153 Example Given any 9 integers whose prime factors lie in the set
{3, 7, 11} prove that there must be two whose product is a square.
Solution: For an integer to be a square, all the exponents of its prime

factorisation must be even. Any integer in the given set has a prime
factorisation of the form 3a 7b 11c . Now each triplet (a, b, c) has one of the
following 8 parity patterns: (even, even, even), (even, even, odd), (even,
odd, even), (even, odd, odd), (odd, even, even), (odd, even, odd), (odd,
odd, even), (odd, odd, odd). In a group of 9 such integers, there must be
two with the same parity patterns in the exponents. Take these two. Their
product is a square, since the sum of each corresponding exponent will
be even.
154 Problem Prove that among n integers, there are always two whose
difference is always divisible by n.
155 Problem (A HSME 1991) A circular table has exactly sixty chairs
around it. There are N people seated at this table in such a way that the
next person to be seated must sit next to someone. What is the smallest
possible value of N?
8 Chapter 2
Answer: 20.
156 Problem Show that if any five points are all in, or √
on, a square of side
1, then some pair of them will be at most at distance 2/2.
157 Problem (H UNGARIAN M ATH O LYMPIAD, 1947) Prove that amongst

six people in a room there are at least three who know one another, or at
least three who do not know one another.
158 Problem Show that in any sum of nonnegative real numbers there is
always one number which is at least the average of the numbers and that
there is always one member that it is at most the average of the numbers.
159 Problem We call a set “sum free” if no two elements of the set add up
to a third element of the set. What is the maximum size of a sum free
subset of {1, 2, . . . , 2n − 1}.
Hint: Observe that the set {n + 1, n + 2, . . . , 2n − 1} of n + 1 elements is

sum free. Show that any subset with n + 2 elements is not sum free.
160 Problem (M MPC 1992) Suppose that the letters of the English
alphabet are listed in an arbitrary order.
1. Prove that there must be four consecutive consonants.
2. Give a list to show that there need not be five consecutive

consonants.
3. Suppose that all the letters are arranged in a circle. Prove that there
must be five consecutive consonants.
161 Problem (S TANFORD 1953) Bob has ten pockets and forty four silver
dollars. He wants to put his dollars into his pockets so distributed that
each pocket contains a different number of dollars.
1. Can he do so?
2. Generalise the problem, considering p pockets and n dollars. The

problem is most interesting when
(p − 1)(p − 2)
n= .
2
Why?
162 Problem Let M be a seventeen-digit positive integer and let N be the

number obtained from M by writing the same digits in reversed order.
Prove that at least one digit in the decimal representation of the number
M + N is even.
163 Problem No matter which fifty five integers may be selected from
{1, 2, . . . , 100},
prove that you must select some two that differ by 9, some two that differ
by 10, some two that differ by 12, and some two that differ by 13, but that
you need not have any two that differ by 11.
164 Problem Let mn + 1 different real numbers be given. Prove that there
is either an increasing sequence with at least n + 1 members, or a
decreasing sequence with at least m + 1 members.
165 Problem If the points of the plane are coloured with three colours,
show that there will always exist two points of the same colour which are
one unit apart.
166 Problem Show that if the points of the plane are coloured with two
colours, there will always exist an equilateral triangle with all its vertices of
the same colour. There is, however, a colouring of the points of the plane
with two colours for which no equilateral triangle of side 1 has all its
vertices of the same colour.
167 Problem (U SAMO 1979) Nine mathematicians meet at an

international conference and discover that amongst any three of them, at
least two speak a common language. If each of the mathematicians can
speak at most three languages, prove that there are at least three of the
mathematicians who can speak the same language.
10 Chapter 2
168 Problem (U SAMO 1982) In a party with 1982 persons, amongst any
group of four there is at least one person who knows each of the other
three. What is the minimum number of people in the party who know
everyone else?
169 Problem (U SAMO 1985) There are n people at a party. Prove that
there are two people such that, of the remaining n − 2 people, there are
at least [n/2] − 1 of them, each of whom knows both or else knows
neither of the two. Assume that “knowing” is a symmetrical relationship.
170 Problem (U SAMO 1986) During a certain lecture, each of five

mathematicians fell asleep exactly twice. For each pair of these
mathematicians, there was some moment when both were sleeping
simultaneously. Prove that, at some moment, some three were sleeping
simultaneously.
2.3 Inclusion-Exclusion
In the Venn diagram below, we mark by R1 the number of elements which
are simultaneously in both sets (i.e., in A ∩ B), by R2 the number of
elements which are in AA but not in B (i.e., in A \ B),
B and by R3 the number
of elements which are B but not in A (i.e., in B \ A). $.4in]

R2 R1 R3
Figure 2.1: Two-set Inclusion-Exclusion
Let |X| denote the number of elements of the set X. Now clearly
R1 + R2 + R3 = |A ∪ B|. This gives the Inclusion-Exclusion Formula for two
sets
[ \
(2.1) |A B| = |A| + |B| − |A B|
Inclusion-Exclusion 11
171 Example Of 40 people, 28 smoke and 16 chew tobacco. It is also

known that 10 both smoke and chew. How many among the 40 neither
smoke nor chew?
Solution: Let A denote the set of smokers and B the set of chewers. Then
|A ∪ B| = |A| + |B| − |A ∩ B| = 28 + 16 − 10 = 34,
meaning that there are 34 people that either smoke or chew (or possibly
both). Therefore the number of people that neither smoke nor chew is
40 − 34 = 6.
Aliter: We fill up the Venn diagram below as follows. Since |A ∩ B| = 8, we
put an 10 in the intersection. Then we put a 28 − 10 = 18 in the part that
A does not overlap B and a 16 − 10 = 6 in the part of B that does not
overlap A. We have accounted for 10 + 186+ 6 = 34 people that are in at
least one of the set. The remaining
A 40 − 34 B= 6 are outside the sets.$.4in]
18 8 6
172 Definition We use φ(n), the Euler phi function to denote the number
of integers k, 1 ≤ k ≤ n which are relatively prime to n.
173 Example How many integer between 1 and 1000 inclusive, do not
share a common factor with 1000, that is, are relatively prime to 1000?
Solution: This problem is asking for φ(1000). Observe that 1000 = 23 53 ,

and thus from the 1000 integer we must weed out those that have a factor
of 2 or of 5 in their prime factorisation. If A2 denotes the set of those
integers divisible by 2 in the interval [1, 1000] then clearly
1000
|A2 | = b c = 500. Similarly, if A5 denotes the set of those integers
2
1000 1000
divisible by 5 then |A5 | = b c = 200. Also |A2 ∩ A5 | = b c = 100.
5 10
This means that there are |A2 ∪ A5 | = 500 + 200 − 100 = 600 integers in
the interval [1, 100] sharing at least a factor with 1000, thus there are
1000 − 600 = 400 integers in [1, 1000] that do not share a factor prime
factor with 1000.
12 Chapter 2
We define φ(1) = 1. Let n > 1 with prime factorisation n = pα1 1 pα2 2 · · · pαk k .
Then it is possible to show by a generalised Inclusion-Exclusion
argument that

φ(n) = n 1 − p11 1 − p12 · · · 1 − p1k
(2.2)
= (pα1 1 − p1α1 −1 )(pα2 2 − pα2 2 −1 ) · · · (pαk k − pαk k −1 )
Thus for example φ(1000) = φ(23 53 ) = (23 − 22 )(53 − 52 ) = 400.$.4in]

We now derive the Inclusion-Exclusion formula for three sets. Using the
associativity and distributivity of unions of sets, we see that
|A ∪ B ∪ C| = |A ∪ (B ∪ C)|
= |A| + |B ∪ C| − |A ∩ (B ∪ C)|
= |A| + |B ∪ C| − |(A ∩ B) ∪ (A ∩ C)|
= |A| + |B| + |C| − |B ∩ C|
− (|A ∩ B| + |A ∩ C| − |(A ∩ B) ∩ (A ∩ C)|)
= |A| + |B| + |C| − |B ∩ C|
− (|A ∩ B| + |A ∩ C| − |A ∩ B ∩ C|)
= |A| + |B| + |C| − |A ∩ B| − |B ∩ C| − |C ∩ A|
+|A ∩ B ∩ C|.
This gives the Inclusion-Exclusion Formula for three sets. See also figure
1.2.
|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |B ∩ C|
(2.3)
−|C ∩ A| + |A ∩ B ∩ C|
Observe that in the Venn diagram below there are 8 disjoint regions (the 7
that form A ∪ B ∪ C and the outside region, devoid of any element
belonging to A ∪ B ∪ C).$.6in]
174 Example In how many ways can one decompose the set
{1, 2, 3, . . . , 100} into subsets A, B, C satisfying
A ∪ B ∪ C = {1, 2, 3, . . . , 100} and A ∩ B ∩ C = ∅
Solution: The conditions of the problem stipulate that both the region
outside the circles in diagram 1.2 and R3 will be empty. We are thus left
with 6 regions to distribute 100 numbers. To each of the 100 numbers we
may thus assign one of 6 labels. The number of sets thus required is 6100 .
Inclusion-Exclusion 13
175 Example How many integers between 1 and 600 inclusive are not
divisible by neither 3, nor 5, nor 7?
Solution: Let Ak denote the numbers in [1, 600] which are divisible by
k = 3, 5, 7. Then
|A3 | = b 600
3
c = 200,
600
|A5 | = b 5 c = 120,
|A7 | = b 600
7
c = 85,
600
|A15 | = b 15 c = 40
|A21 | = b 600
21
c = 28
600
|A35 | = b 35 c = 17
600
|A105 | = b 105 c = 5
By Inclusion-Exclusion there are 200 + 120 + 85 − 28 − 21 − 17 + 5 = 325
integers in [1, 600] divisible by at least one of 3, 5, or 7. Those not
divisible by these numbers are a total of 600 − 325 = 275.
176 Example In a group of 30 people, 8 speak English, 12 speak Spanish

and 10 speak French. It is known that 5 speak English and Spanish, 5
Spanish and French, and 7 English and French. The number of people
speaking all three languages is 3. How many do not speak any of these
languages?
Solution: Let A be the set of all English speakers, B the set of Spanish
speakers and C the set of French speakers in our group. We fill up the
following Venn diagram successively. In the intersection of all three we
put 8. In the region common to A and B which is not filled up we put
5 − 2 = 3. In the region common to A and C which is not already filled up
we put 5 − 3 = 2. In the region common to B and C which is not already
filled up, we put 7 − 3 = 4. In the remaining part of A we put
8 − 2 − 3 − 2 = 1, in the remaining part of B we put 12 − 4 − 3 − 2 = 3, and
in the remaining part of C we put 10 − 2 − 3 − 4 = 1. Each of the mutually
disjoint regions comprise a total of 1 + 2 + 3 + 4 + 1 + 2 + 3 = 16 persons.
Those outside these three sets are then 30 − 16 = 14.$.4in]
177 Problem How many integers between 1 and 3012 are divisible by 5 or
7 but not by both numbers?
14 Chapter 2
178 Problem Would you believe a market investigator who reports that of
1000 people, 816 like candy, 723 ice cream, 645 cake, while 562 like both
candy and ice cream, 463 like both candy and cake, 470 like both ice
cream and cake, while 310 like all three?
179 Problem (Lewis Carroll) In a very hotly fought battle, at least 70% of
the combatants lost an eye, at least 75% an ear, at least 80% an arm, and
at least 85% a leg. What can be said about the percentage that lost all
four members?
180 Problem (I MO 1966) In a mathematical contest, three problems, A, B,

C, were posed. Amongst the participants there were twenty-five students
who solved at least one problem each. Of all the contestants who did not
solve problem A, the number who solved problem B was twice the number
who solved problem C. The number of students who solved only problem
A was one more than the number of students who solved problem A and
at least one other problem. Of all the students who solved just one
problem, half did not solve A. How many students solved only problem B?
181 Problem A group of students took exams in French, English, and

Maths. Of them, 92 passed French, 72 English, and 63 Maths. It is also
known that at most 65 passed French and English, at most 54 French and
Maths, and at most 48 English and Maths. Find the largest possible
number of students that could have passed all three subjects.
182 Problem How many integers between 1 and 49000 inclusive are not
divisible by 3, 5 or 7?
183 Problem How many integers from 1 to 1 000 000 inclusive are neither
perfect squares, perfect cubes, nor perfect fourth powers?
184 Problem Compute φ(120), φ(500) and φ(700).
185 Problem Let x, y be real numbers. Prove that
x + y = min(x, y) + max(x, y)
Parity 15
186 Problem Let x, y, z be real numbers. Prove that
max(x, y, z) = x + y + z − min(x, y) − min(y, z) − min(z, x) + min(x, y, z)
2.4 Parity
187 Example Two diametrically opposite corners of a chess board are
deleted. Show that it is impossible to tile the remaining 62 squares with 31
dominoes.
Solution: Each domino covers one red square and one black squares.
But diametrically opposite corners are of the same colour, hence this
tiling is impossible.
188 Example All the dominoes in a set are laid out in a chain according to
the rules of the game. If one end of the chain is a 6, what is at the other
end?
Solution: At the other end there must be a 6 also. Each number of spots
must occur in a pair, so that we may put them end to end. Since there are
eight 6’s, this last 6 pairs off with the one at the beginning of the chain.
189 Definition The midpoint of the line joining (x, y) to (x1 , y1 ) is the point

x + x1 y + y 1
, .
2 2
190 Example The numbers 1, 2, . . . , 10 are written in a row. Show that no

matter what choice of sign ± is put in between them, the sum will never
be 0.
Solution: The sum 1 + 2 + · · · + 10 = 55, an odd integer. Since parity is

not affected by the choice of sign, for any choice of sign ±1 ± 2 ± · · · ± 10
will never be even, in particular it will never be 0.
191 Definition A lattice point (m, n) on the plane is one having integer
coordinates.
16 Chapter 2
192 Example Five lattice points are chosen at random. Prove that one
can always find two so that the midpoint of the line joining them is also a
lattice point.
Solution: There are four parity patterns: (even, even), (even, odd), (odd,
odd), (odd, even). By the Pigeonhole Principle among five lattice points
there must be two having the same parity pattern. Choose these two. It is
clear that their midpoint is an integer.
For the following examples we will need to know the names of the
following tetrominoes. $.4in]
L-tetromino T- Straight- Skew-
$.4in] tetromino$.4in]tetromino$.4in]
tetromino$.4in]
Show that an 8 × 8 chessboard cannot be tiles with 15 straight
tetrominoes and one L-tetromino.
Solution: Colour rows 1, 3, 5, 7 black and colour rows 2, 4, 6, and 8 red.

A straight tetromino will always cover an even number of red boxes and
the L-tetromino will always cover an odd number of red squares. If the
tiling were possible, then we would be covering an odd number of red
squares, a contradiction.
193 Problem Twenty-five boys and girls are seated at a round table. Show
that both neighbours of at least one student are girls.
194 Problem A closed path is made of 2001 line segments. Prove that
there is no line, not passing through a vertex of the path, intersecting
each of the segments of the path.
195 Problem The numbers 1, 2, . . . , 2001 are written on a blackboard. One

starts erasing any two of them and replacing the deleted ones with their
difference. Will a situation arise where all the numbers on the blackboard
be 0?
196 Problem Show that a 10 × 10 chessboard cannot be tiled with 25

straight tetrominoes.
Parity 17
197 Problem Show that an 8 × 8 chess board cannot be tiled with 15

T-tetrominoes and one square tetromino.
18 Chapter 2
Chapter 3
Counting
3.1 Introductory Problems

198 Example n equally spaced points 1, 2, . . . , n are marked on a
circumference. If 15 directly opposite to 49, how many points are there
total?
Solution: Points 16, 17, . . . , 48 are 33 in total and are on the same side of
the diameter joining 15 to 49. For each of these points there is a
corresponding diametrically opposite point. There are thus a total of
2 · 33 + 2 = 68 points.
199 Example How many factors of 295 are larger than 1, 000, 000?
Solution: The 96 factors of 295 are 1, 2, 22 , . . . , 295 . Observe that

210 = 1024 and so 220 = 1048576. Hence
219 = 524288 < 1000000 < 1048576 = 220 . The factors greater than
1,000,000 are thus 220 , 221 , . . . 295 . This makes for 96 − 20 = 76 factors.
200 Example How many positive divisors does 28 39 52 have? What is the
sum of these divisors?
Solution: We will assume that the positive integers may be factorised in a
19
20 Chapter 3
unique manner as the product of primes. Expanding the product
(1 + 2 + 22 + · · · + 28 )(1 + 3 + 32 + · · · + 39 )(1 + 5 + 52 )
each factor of 28 39 52 appears and only the factors of this number appear.
There are then, as many factors as terms in this product. This means that
there are (1 + 8)(1 + 9)(1 + 3) = 320 factors.
The sum of the divisors of this number may be obtained by adding up
each geometric series in parentheses. The desired sum is then
29 − 1 310 − 1 53 − 1
· · = 467689684.
2−1 3−1 5−1
The argument works in general. If n = pa1 1 · pa2 2 · · · pas s , where the p’s are
distinct primes and if d(n), σ(n) denote, respectively, the nunber of
positive divisors of n and the sum of these positive divisors of n, then
(3.1) d(n) = (a1 + 1)(a2 + 1) · · · (as + 1)
and
p1a1 +1 − 1 p2a2 +1 − 1 pas +1 − 1

(3.2) σ(n) = · ··· s
p1 − 1 p2 − 1 ps − 1
201 Example A locker room has 100 lockers. Initially, all the lockers are
closed. Person 1 enters, and opens all the lockers which are even and
then leaves. Person 2 enters and opens all the lockers that have numbers
which are multiples of 3, closing those lockers which were already
opened, and then leaves. Person 3 enters and changes the status of the
lockers (from opened to closed and viceversa) on all the lockers which
have numbers which are multiples of 4. This goes on till Person 99 enters
and changes the status of locker 100. Which lockers remained closed?
Solution: Consider locker n which is initially closed. Assume n has t

divisors greater than 1, 1 < d1 < d2 < · · · < dt−1 < dt = n. Person d1 − 1
opens the locker, Person d2 − 1 closes it, Person d3 − 1 opens the locker,
etc. Thus locker n remains closed if and only if n has an even number of
divisors greater than 1. If we add 1 to the number of divisors, we see that
Introductory Problems 21
locker n remains closed if and only if n has an odd number of divisors.

But from (5.1) d(n) will be odd if and only if n is a perfect square. Thus
the lockers that remain closed are the ones with a perfect square number:
lockers 1, 4, 9, 16, 25, 36, 49, 64, 81, and 100.
202 Example How many positive integers have (i) 2 digits? (ii) 3 digits?
(iii) 4 digits?
Solution: There are 99 integers in the range 1, 2, . . . , 99. Of those, 9 have

1 digit so there are 99 − 9 = 90 positive integers with two digits. Similarly,
there are 999 − 99 = 900 positive integers with three digits and
9999 − 999 = 9000 positive integers with four digits.
203 Example To write a book 1890 digits were utilised. How many pages
does the book have?
Solution: A total of
1 · 9 + 2 · 90 = 189
digits are used to write pages 1 to 99, inclusive. We have of
1890 − 189 = 1701 digits at our disposition which is enough for
1701/3 = 567 extra pages (starting from page 100). The book has
99 + 567 = 666 pages.
204 Example All the natural numbers, starting with 1, are listed
consecutively
123456789101112131415161718192021 . . .
Which digit occupies the 1002nd place?
Solution: When the number 99 is written down, we have used

1 · 9 + 2 · 90 = 189
digits. If we were able to write 999, we would have used
1 · 9 + 2 · 90 + 3 · 900 = 2889
digits, which is more than 1002 digits. The 1002nd digit must be among
the three-digit positive integers. We have 1002 − 189 = 813 digits at our
22 Chapter 3
disposal, from which we can make b 813

3
c = 271 three-digit integers, from
100 to 270. When the 0 in 270 is written, we have used
189 + 3 · 271 = 1002 digits. The 1002nd digit is the 0 in 270.
205 Example (A HSME 1994) When n standard six-sided dice are rolled,
the probability of obtaining a sum of 1994 is greater than zero and is the
same as the probability of obtaining a sum of S. What is the smallest
possible value of S?
Solution: Since the probability of obtaining the sum 1994 is positive, there
1994
are n ≥ b c = 333 dice. Let x1 + x2 + · · · + xn = 1994 be the sum of
6
the faces of the n dice adding to 1994. We are given that
(7 − x1 ) + (7 − x2 ) + · · · + (7 − xn ) = S
or 7n − 1994 = S. The minimal sum will be achieved with the minimum

dice, so putting n = 333 we obtain the minimal S = 7(333) − 1994 = 337.
206 Example (A IME 1993) How many ordered four-tupels of integers

(a, b, c, d) with 0 < a < b < c < d < 500 satisfy a + d = b + c and
bc − ad = 93?
Solution: Since a + d = b + c, we can write the four-tuple (a, b, c, d) as

(a, a + x, a + y, a + x + y), with integers x, y, 0 < x < y. Now,
93 = bc − ad = (a + x)(a + y) − a(a + x + y) = xy.
This gives (x, y) = (1, 93) or (x, y) = (3, 31). In the first case
(a, b, c, d) = (a, a + 1, a + 93, a + 94)
is in the desired range for 1 ≤ a ≤ 405 and in the second case
(a, b, c, d) = (a, a + 3, a + 31, a + 34)
is in the desired range for 1 ≤ a ≤ 465. The two sets of four-tuples are
disjoint, and so the sought number is 870.
Two Basic Counting Principles 23
207 Problem Find d(1260) and σ(1260).
208 Problem The integers from 1 to 1000 are written on a circle. Starting
with 1, each 15th is marked (that is, 1, 16, 31, etc. are marked). This
operation is repeated until a number is marked again. How many integers
remain unmarked
Answer: 800
209 Problem All the positive integers are written in succession.

123456789101112131415161718192021222324 . . .
Which digit occupies the 206790th place?
Answer: 4
210 Problem Four comrades are racing down a dusty staircase. Oli goes
down two steps at a time, Gooh three, Phree four, and Nyck five. If the
only steps with all four’s footprints are at the top and at the bottom, how
many steps have just one footprint?
211 Problem (A HSME 1992) For how many integers between 1 and 100
does
x2 + x − n
factor into the product of two linear factors with integer coefficients?
212 Problem (A HSME 1989) Five people are sitting at a round table. Let
f ≥ 0 be the number of people sitting next to at least one female and
m ≥ 0 be the number of people sitting next to at least one male. Find the
number of possible ordered pairs (f, m).
Answer: 8
3.2 Two Basic Counting Principles

We denote by (E) the cardinality (number of elements) of the set E. For
example if E = {x ∈ Z : |x| ≤ 3} then (E) = 7, since x ∈ E if and only if
24 Chapter 3
x = −3, −2, −1, 0, 1, 2 or 3.

The Addition Principle: If Em ∩ En = ∅ (the sets are pairwise disjoint)
(E1 ∪ E2 ∪ · · · ∪ Ek ) = (E1 ) + (E2 ) + · · · + (Ek ).
213 Example Find the number of lattice points (x, y) that satisfy
|x| + |y| ≤ 3.
Solution: E = {(x, y) : x ∈ Z, y ∈ Z, |x| + |y| ≤ 3}. Then E can be

decomposed into the pairwise disjoint sets Ek , where
Ek = {(x, y) : x ∈ Z, y ∈ Z, |x| + |y| = k} and k = 0, 1, 2, 3. Now
1. b0 = {(0, 0)}
E1 = {(−1, 0), (1, 0), (0, −1), (0, 1)}
E2 = {(−2, 0), (2, 0), (0, −2), (0, 2), (−1, −1), (−1, 1), (1, −1)(1, 1)}
E3 = {(−1, −2), (−1, 2), (1, −2), (1, 2)}
Hence
(E) = E0 ∪ E1 ∪ E2 ∪ E3 )
= (E0 ) + (E1 ) + (E2 ) + (E3 )
= 1 + 4 + 8 + 4 = 17.
k
Y
The Cartesian Product Ei = E1 × E2 × · · · × Ek is the collection of
i=1
ordered k-tuples {(e1 , e2 , . . . , ek ) : ei ∈ Ei }.
k
Y
The Multiplication Principle: Let Ei = {(e1 , e2 , . . . , ek ) : ei ∈ Ei } be
i=1
the Cartesian product of the sets Ei . Then
k
! k
Y Y
Ei = (Ei ).
i=1 i=1
214 Example A license plate is to be made according to the following

provision: it has four characters, the first two characters can be any letter
of the English alphabet and the last two characters can be any digit. How
many different license plates can be made?
Solution: The number of different license plates is the number of different

four-tuples (Letter 1 , Letter 2 , Digit 1 , Digit 2 ). The first letter can be
chosen in 26 ways, the second letter can be chosen in 26 ways, the first
digit can be chosen in 10 ways and the last digit can be chosen in 10
ways. By the multiplication principle, the number of different four-tuples is
26 · 26 · 10 · 10 = 67600.
215 Example How many positive integers have 4 digits? None of the
integers is to have 0 as its leftmost digit.
Solution: Each four-digit integer 1000a + 100b + 10c + d can be

considered as an ordered four-tuple (a, b, c, d) with a ∈ {1, 2, . . . , 9} and
b, c, d ∈ {0, 1, 2, . . . , 9}. By the multiplication principle, the number of such
four-tuples is 9 · 10 · 10 · 10 = 9000.
216 Example A palindrome is an integer whose decimal expansion is

symmetric, e.g. 1, 2, 11, 121, 15677651 (but not 010, 0110) are palindromes.
How many positive palindromes are there with (i) 4 digits?, (ii) 5 digits?
Solution: Each four-digit palindrome 1000a + 100b + 10b + a can be

considered as an ordered four-tuple (a, b, b, a) with a ∈ {1, 2, . . . , 9} and
b ∈ {0, 1, 2, . . . , 9}. By the multiplication principle, the number of such
four-tuples is 9 · 10 = 90. Similarly, each five-digit palindrome
10000a + 1000b + 100c + 10b + a can be considered as an ordered
five-tuple (a, b, c, b, a) with a ∈ {1, 2, . . . , 9} and b, c ∈ {0, 1, 2, . . . , 9}.
Again, by the multiplication principle, the number of such five-tuples is
9 · 10 · 10 = 900.
217 Example How many different n-digit positive integers do not have the
digit 5?
Solution: The first (leftmost) digit, can be one of the 8 digits

{1, 2, 3, 4, 6, 7, 8, 9}. The remaining n − 1 digits can be one of 9 digits
{0, 1, 2, 3, 4, 6, 7, 8, 9}. The number of such integers is thus 8 · 9n−1 .
218 Example Prove that a set with n elements has 2n different subsets
(including the empty set and the set itself).
26 Chapter 3
Solution: We motivate the idea of the proof for the case when n = 3.
Suppose S = {a, b, c} is a set with three elements. Which each subset of
the set we associate a dyadic (0-1) ternary sequence writing 0 if the
element is not in the set, and 1 if the element belongs to the set. So with
the set ∅ we associate the sequence 000
the set {a} we associate the sequence 100
the set {b} we associate the sequence 010
the set {c} we associate the sequence 001
the set {a, b} we associate the sequence 110
the set {a, c} we associate the sequence 101
the set {b, c} we associate the sequence 011
the set {a, b, c} we associate the sequence 111
In the general case, we may supposed the elements of the set to be
ordered as (x1 , x2 , . . . , xn ). To each subset T of the set, we associate a
dyadic sequence as above, writing 1 if xi ∈ T and 0 if xi 6∈ T . For each of
n positions we have two choices, and so the total elements of subsets is
· · 2} = 2n .
2| ·{z
n 2 0s
219 Example Out of nine different pairs of shoes, in how many ways could
I choose a right shoe and a left shoe, which do not form a pair?
Solution: The left shoe can be chosen in 9 ways, the right shoe can be
chosen in 8 ways, so as not to pair up with the first. The total number of
ways is thus 9 · 8 = 72.
Aliter: There are 9 · 9 = 81 ways of choosing a left shoe and a right shoe.
Of those, 9 pairs match, so the required number of ways is 81 − 9 = 72.
Sometimes we need to combine both the addition and the multiplication
principle.
220 Example There are five Golden retrievers, six Irish setters, and eight
Poodles at the pound. In how many ways can two dogs be chosen if they
are not the same kind?
Solution: Notice that the order in which the dogs are chosen is
unimportant. One Golden retriever and one Irish setter can be chosen in
5 · 6 = 30 ways. One Golden retriever and one Poodle can be chosen in
5 · 8 = 40 ways. One Irish setter and one Poodle can be chosen in
6 · 8 = 48 ways. The total number of ways of choosing a pair that are not
of the same breed is thus 30 + 40 + 48 = 118.
221 Example How many triplets (a, b, c) with a, b, c ∈ {1, 2, . . . , 101}

simultaneously satisfy a < b and a < c?
Solution: We condition on a, which can take any of the values

a = 1, 2, . . . , 100. Given a, b can be any of the 101 − a values in
{a + 1, a + 2, . . . , 101}. Similarly, c can be any of the 101 − a values in
{a + 1, a + 2, . . . , 101}. Given a then, b and c may be chosen in
(101 − a)(101 − a) = (101 − a)2 ways. The number of triplets is therefore
by formula (4.5),
100
X 100(100 + 1)(2(100) + 1)
(101−a)2 = 1002 +992 +982 +· · ·+12 = = 338350.
a=1
6
222 Example (P UTNAM 1987) The sequence of digits

12345678910111213141516171819202122 . . .
is obtained by writing the positive integers in order. If the 10n digit of this
sequence occurs in the part in which the m-digit numbers are placed,
define f : N → N by f(n) = m. For example f(2) = 2, because the
hundredth digit enters the sequence in the placement of the two-digit
integer 55. Find, with proof, f(1987).
Solution: There are 9 · 10j−1 j-digit positive integers. The total number of
digits in numbers with at most r digits is the arithmetic-geometric sum
j
X 10r − 1
g(r) = j · 9 · 10j−1 = r10r − .
j=1
9
10r − 1
As 0 < < 10r , we get
9
(r − 1)10r < g(r) < r10r .
28 Chapter 3
Thus g(1983) < 1983 · 101983 < 104 101983 = 101987 and
g(1984) > 1983 · 101984 > 103 101984 = 101987 . Therefore f(1987) = 1984.
223 Problem Let E = {(x, y) : x ∈ Z, y ∈ Z, x2 + y2 ≤ 6}. Find (E).
224 Problem Prove that there are 9 · 10n−1 integers with n ≥ 1 digits.
225 Problem How many positive palindromes are there with n digits?
n−1 n−2
Answer: 9 · 10 2 if n is odd, and 9 · 10 2 if n is even.
226 Problem Find the 1984-th and the 2000-th palindrome.
3.3 Permutations
Each of the arrangements which can be made by taking some or all of a
number of things is called a permutation. Thus the permutations which
can be made by taking the numbers {1, 2, 3, 4} two at the time are twelve
in number, namely,
12, 13, 14, 23, 24, 34,
21, 31, 41, 32, 43.
Their number can be easily calculated without having to enumerate them.
For by the product rule we can choose the first number in 4 ways and the
second number in three ways (we have already selected one number,
leaving us with 3). This gives 4 · 3 = 12 ways.
227 Example How many distinct four-letter words can be made with the
letters of the set {t, i, c, k} if (i) the letters are not to be repeated?, (ii) if the
letters can be repeated?
Solution: (i) The first letter can be any one of any 4. After choosing the
first letter, we have 3 choices for the second letter, 2 for the third, and 1
for the fourth. The total number of such words is thus 4 · 3 · 2 · 1 = 24.
Permutations 29
(ii) The first letter can be chosen in 4 ways. Since we are allowed to
repeat letters, the second letter can be also any of 4, etc. The total
number of words thus formed is 44 .
228 Example How many distinct six-digit integers that are multiples of 5
can be formed from the list of digits {1, 2, 3, 4, 5, 6} (i) if we don’t allow
repetition, (ii) if we allow repetition?
Solution: The last digit must perforce be 5. There remain five digits to fill
the remaining 5 spots, and these can be filled in 5! = 120 different ways.
(ii) Again the last digit must be five. The other five spots can be filled with
any of the 6 digits, so we have 65 = 7776.
229 Example In how many ways can one decompose the set
{1, 2, 3, . . . , 100} into subsets A, B, C satisfying
A ∪ B ∪ C = {1, 2, 3, . . . , 100} and A ∩ B ∩ C = ∅
Solution: The conditions of the problem stipulate that both the region
outside the circles and R3 in diagram below will be empty. We are thus left
with 6 regions to distribute 100 numbers.
C To each of the 100 numbers we
may thus assign one of 6 labels. TheR number of sets thus required is 6100 .
$1in]
4
R6 R7
R3
A R2 R1 B
R5
230 Example (A IME 1993) How many even integers between 4000 and
7000 have four different digits?
Solution: We condition of the first digit, which can be 4, 5, or 6. If the

number starts with 4, in order to satisfy the conditions of the problem, we
much choose the last digit from the set {0, 2, 6, 8}, and so we have 4
choices for the last digit. Once this last digit is chosen, we have 8 choices
for the penultimate digit and 7 choices for the antepenultimate digit. There
are thus 4 · 8 · 7 = 224 even numbers which have their digits distinct and
start with a 4. Similarly, there are 224 even numbers will all digits distinct
and starting with a 6. When they start with a 5, we have 5 choices for the
30 Chapter 3
last digit, 8 for the penultimate and 7 for the antepenultimate. This gives
280 ways. The total number sought is therefore 224 + 224 + 280 = 728.
231 Example Seven different beads are arranged in a circular necklace.

In how many different ways can they be arranged?
Solution: Let the beads be A, B, C, D, E, F, G. If the beads were in a row,

we would have 7! = 7 · 6 · 5 · 4 · 3 · 2 · 1 arrangements, but because these
beads are arranged in a circle, where there is no beginning and no end,
different linear permutations may produced identical circular
permutations. For example, the 7 permutations
ABCDEFG, BCDEFGA, CDEFGAB, DEFGABC, EFGABCD, FGABCDE, GABCDEF
are identical when arranged in a circle. Since we may choose any of the
beads as the first bead, the sought numbers of arrangements is
7!/7 = 6! = 720.
232 Problem If repetitions are forbidden, (i) how many three-digit

numbers can be formed from the set {2, 3, 5, 6, 7, 9}, (ii) how many of these
numbers are less than 400?, (iii) how many of the set of all three digit
numbers formed are even?, (iii) how many are odd?, (iv) how many are
multiples of 5?
Answer: 120, 40, 40, 80, 20
233 Problem In how many ways can three students and two professors sit
in a row? In how many ways can they sit in a row if the students and the
professors are to sit within themselves (that is, we have a row of just
students and just professors, or viceversa)? In how many ways can they
sit if only the professors are to sit together (that is, the two professor are
always next to one another)?
Answer: 120, 24, 48
234 Problem Three Mathematics majors and two Computer Science

majors sit around a round table. In how many ways can they do so if the
Mathematics majors insist in sitting next to each other?
Permutations 31
Answer: 12
235 Problem How many different license plates are there involving three
letters and four digits if the three letters must appear together either at the
beginning or at the end of the plate?
Answer: 104 263 2! = 351520000
236 Problem In how many ways can a committe of k people be chosen

from ten people if k can be any of 1, 2, 3, . . . 10?
Answer 210 − 1 = 1023
237 Problem Find the number of ways in which five different English
books, six French books, three German books, and seven Russian books
can be arranged together on a shelf so that all books of the same
language are together.
Answer: 3!4!5!6!7!
238 Problem How many ways are there to seat ten boys and ten girls
around a circular table?
Answer: 19!
239 Problem A child has blocks of six different colours. If the child selects
one block of each colour, in how many ways can these be arranged in a
line?
240 Problem How many ten-digit multiples of five are there if no digit is to
be repeated?
Answer: 8 · 8! + 9!
241 Problem Find the number of seven-digit palindromes none of whose

digits are used more than twice.
Answer: 4536
32 Chapter 3
3.4 Combinations
Each of the groups or selections which can be made by taking some or all
of a number of things is called a combination.
The combinations which can be made by taking the numbers {1, 2, 3, 4}
two at the time are six in number, namely,
12, 13, 14, 23, 24, 34.
This number can be obtained without enumerating these possibilities. For

there are four ways of choosing the first number and three ways of
obtaining the second number. Thus there are twelve ways of choosing a
first and then a second number. Now, we are not interested in the order
since, for example, {12} is as good as {21}. We must then divide by the
number of ways of permuting these repeats, namely, 2!. Therefore the
total number of combinations is 4 · 3/2! = 6.
Observe that in forming combinations we are not interested in the
possible orders of the selections, as we are in permutations. We denote
the number of combinations of n objects taken k at the time by nk , read

“n choose k.” With regards to order, we can choose k objects in
n(n − 1)(n − 2) · · · (n − k + 1),
as there are n ways of choosing the first object, n − 1 ways of choosing

the second, etc.. But these k objects chosen can be arranged in k! ways
amongst themselves, and hence we conclude that

n n(n − 1)(n − 2) · · · (n − k + 1)
(3.3) =
k k!
(n − k)!
If we multiply the above fraction by , we can easily see that
(n − k)!

n n!
(3.4) =
k k!(n − k)!
We now give some examples of the use of combinations.
242 Example How many different committees of seven people can be

formed from twenty people?
Combinations 33
Solution: There are 20 20·19·18·17·16·15·14

7
= 1·2·3·4·5·6·7
= 77520.
243 Example How many different committees of seven people, with a

given chairman, can be formed from twenty people?
Solution: We can choose the seven people in 20 ways. Of the seven, the

7
chairman can be chosen in 7 ways. Thus there are 7 20

7
= 542640.
Aliter: Choose the chairman first. This can be done in 20 ways. Out of the
nineteen remaining people, we must now choose six. This can be done in
19
= 1·2·3·4·5·6 = 27132 ways. The total number of ways desired is
19·18·17·16·15·14
6
hence 20 19

6
= 542640.
244 Example How many different committees of seven people, with a

chairman and a secretary (the chairman is different from the secretary)
can be formed from twenty people?
Solution: Choose the seven people first. This can be done in 20 ways.

7
Out of the seven, the choose the chairman first in 7 ways and then the
secretary in 6 ways. The total number of ways is therefore
7 · 6 20
7
= 3255840.
Aliter: If one chooses the chairman first, then the secretary and finally, the
remaining five members of the committee, one obtains
20 · 19 185
= 3255840 as before.
Now let a1 < a2 < · · · < an . It is easy to see that nk counts the numjber

of k-strings ai1 ai2 · · · aik which are increasing, since any such string
consists of different elements. Analogously, nk counts the number of
strings of b1 > b2 > · · · > bn which are decreasing.
245 Example (A HSME 1990) How many of the numbers
100, 101, . . . , 999,
have three different digits in increasing or in decreasing order?
Solution: Fir a string of three-digit numbers to be decreasing, the digits

must come from {0, 1, 2, . . . , 9} thus there are 10
3
= 120 three-digit
numbers with all its digits in decreasing order. If the string of three-digit
numbers is increasing, the digits have to come from {1, 2, . . . , 9}, thus
34 Chapter 3
there are 93 = 84 three-digit numbers with all the digits increasing. The

asked total is hence 120 + 84 = 204.
246 Example There are twenty students in a class. In how many ways
can the twenty students take five different tests if the four of the students
are to take each test?
Solution: We can choose the four students who are going to take thefirst
test in 20
4
. From the remaining ones, we can choose students in 16 4
to
take the second test. The third test can be taken in 4 ways, the fourth
12

in 84 and the fifth in 44 ways. The required number of ways is thus

20 16 12 8 4 20!
= 4 = 7332965640000.
4 4 4 4 4 4!
247 Example In how many ways can a woman choose three or more
lovers from seven eligible suitors?
Solution: She might choose three in 73 ways, four in 74 ways, etc.. The

total number of ways is

7 7 7 7 7
+ + + + = 99.
3 4 5 6 7
248 Example How many times is the digit 3 listed in the numbers 1 to
1000?
Solution: We count those numbers that have exactly one 3, exactly two 3s
and exactly three 3s. There is only one numberin the range 1—1000 that
has 3 three times, namely 333. Suppose xyz, where x, y, z are digits, is to
have
the digit 3 exactly twice. We can choose these two positions in
3
2
= 3 ways. The third position can be filled with any of the remaining
nine digits. Thus there are 9 · 3 = 27 numbers in the range 1—1000 that
contain the digit 3 exactly twice. Similarly, there are 92 31 = 243 numbers
that use the digit 3 exactly once. This means that the digit 3 appears
3 · 1 + 2 · 27 + 1 · 243 = 300 times.
Combinations 35
249 Example (A HSME 1994) Nine chairs in a row are to be occupied by

six students and Professors Alpha, Beta and Gamma. These three
professors arrive before the six students and decide to choose their
chairs so that each professor will be between two students. In how many
ways can Professors Alpha, Beta and Gamma choose their chairs?
Solution: Align the six students first. There are five spaces between
them. A professor will be between two students if and only if he occupies
one of these five spaces. Thus we must choose three spaces out of five,
which can be done in 53 = 10 different ways. Since the order of the
professors can be permuted, the final answer is 10 × 3! = 60.
250 Example In how many ways can a deck of playing cards can be
arranged if no two hearts are adjacent?
Solution: We align the 39 cards which are not hearts first. There are
thirty-eight spaces between them, and one extra space before the first
card and another extra space after the last card, giving a total
of 40
spaces where the hearts can be placed. There are thus 13 ways of
40
choosing the places where the hearts can go. Since we are interested in
arrangements, we can arrange the hearts in 13! ways and the none
hearts in 39! ways. The total number of arrangements is thus 40

13
13!39!.
251 Example Given a positive integer n find the number of integer

quadruples (a, b, c, d) with 0 ≤ a ≤ b ≤ c ≤ d ≤ n.
Solution: By letting (a 0 , b 0 , c 0 , d 0 ) = (a, b + 1, c + 2, d + 3) we establish a

one-to-one correspondence between the vectors
(a, b, c, d), 0 ≤ a ≤ b ≤ c ≤ d and the vectors
(a 0 , b 0 , c 0 , d 0 ), 0 ≤ a 0 < b 0 < c 0 < d 0 ≤ n + 3.
To count this last set we choose four different numbers from the set
{0, 1, 2, . . . , n + 3}. This can be done in 4 ways.
n+4
252 Problem (A HSME 1989) Mr. and Mrs. Zeta want to name baby Zeta
so that its monogram (first, middle, and last initials) will be in alphabetical
order with no letters repeated. How many such monograms are possible?
36 Chapter 3
253 Problem In how many ways can you pack twelve books into four
parcels if one parcel has one book, another parcel has five books, and
another has two books, and another has four books?
Answer: 12 11
6 4
1 5 2 4
254 Problem In how many ways can a person invite three of his six
friends to lunch every day for twenty days if he has the option of inviting
the same or different friends from previous days?
6 20
Answer:

3
255 Problem A committee is to be chosen from a set of nine women and

five men. In how many ways can one form a committee that has three
men and three women?
Answer: 9
5
3 3
256 Problem In how many ways can the following prizes be given away to
a class of twenty students: first and second Latin, first and second
Mathematics, first Science, and first French?
Answer: 57760000
257 Problem How many integers less than 10000 can be made with the
eight digits 0, 1, 2, 3, 4, 5, 6, 7?
Answer: 4095
258 Problem In how many ways can seven persons form a ring? In how
many ways can seven Englishmen and seven Americans sit down at a
round table, no two Americans being together?
Answer: 720; 3628800
259 Problem From three guavas, four peaches, and two oranges, how
many selections of fruit can be made, taking at least one of each kind?
Distributions 37
Answer:

3 3 3 4 4 4 4 2 2
+ + + + + + = 315
1 2 3 1 2 3 4 1 2
260 Problem (A IME 1984) A gardener plants three maple trees, four oak
trees and five birch trees in a row. He plants them in random order, each
arrangement being equally likely. Let m/n in lowest terms be the
probability that no two birch trees are next to each other. Find m + n.
Answer: 106.
3.5 Distributions
261 Theorem Let n be a positive integer. The number of positive solutions
to
x1 + x 2 + · · · + x r = n
is
n−1
.
r−1
262 Example In how many ways can 100 be written as the sum of four
(positive) summands?
263 Corollary Let n be a positive integer. The number of non-negative

solutions to
x1 + x 2 + · · · + x r = n
is
n+r−1
.
r−1
264 Problem There are thirty students in a class. In how many ways can
the class elect a President and a Vice-President if no student can be
elected for both offices?
38 Chapter 3
Answer: 870
3.6 Combinatorial Identities

265 Example Give a combinatorial interpretation of the symmetry
Identity

n n
(3.5) =
k n−k
266 Example Give a combinatorial proof that for integer n ≥ 1,

n 2
X
2n n
(3.6) =
n k=0
k
267 Example Give a combinatorial interpretation of Newton’s Identity

n r n n−k
(3.7) =
r k k r−k
for 0 ≤ k ≤ r ≤ n.
268 Example Give a combinatorial interpretation of the Pascal’s Identity

n n−1 n−1
(3.8) = +
k k k−1
269 Example Let n ≥ 1. Prove that

n
X n
(3.9) = 2n
k=0
k
270 Example (A IME 1989) Ten points are marked on a circle. How many
distinct convex polygons of three or more sides can be drawn using some
(or all) of the ten points as vertices? (Polygons are distinct unless they
have exactly the same vertices.)
Combinatorial Identities 39
Solution: Choosing k points, 3 ≤ k ≤ 10 will determine a k-sided polygon,

since the polygons are convex and thus have no folds. The answer is thus
10
X
10 10 10 10
=2 − − − = 968.
k=3
0 1 2
271 Example (A IME 1988) One commercially available ten-button lock

may be opened by depressing —in any order— the correct five buttons.
Suppose that there locks are redesigned so that sets of as many as nine
buttons or as few as one button could serve as combinations. How many
additional combination would this allow?
Solution: There are 210 configurations of the ten buttons. We are to

exclude those in which none or all of the buttons are depressed. The total
number of additional combinations is therefore

10 10
2 −1−1− = 770.
5
272 Example Form a set of n ≥ 3 points on the plane, no three collinear,
1. how many lines are determined?
2. how many straight lines pass through a particular point?
3. how many triangles are determined?
4. how many triangles have a particular point as a vertex?
Solution: (i) Since the points are not collinear and any two points
determine a straight line, there are 2 lines in total.
n

(ii) Once a point is chosen, there remains to choose another point. We

can do this in n − 1 ways.
(iii) A triangle is determined by 3 non-collinear points. We can choose
triangles then in n3 ways.

(iv) Once a point is chosen, there remain to choose two points from the
remaining n − 1 points. We can do this in 2 ways.
n−1

40 Chapter 3
Aliter: The number of triangles that can be formed by excluding any

particular point is 3 . From the total number of triangles, we subtract
n−1

those that do not have a particular point as a vertex: n3 − n−1 n−1

3
= 2
as before.
273 Problem Four writers must write a book containing seventeen

chapters. The first and third writers must each write five chapters, the
second must write four chapters, and the fourth writer must write three
chapters. How many ways can the book be written? What if the first and
third writers had to write ten chapters combined, but it did not matter
which of them wrote how many (e.g., the first could write ten and the third
none, the first could write none and the third one, etc.)?
Answer: 17 12
7 3 17
14

5 5 4 3
; 3 4
210
3.7 The Binomial Theorem

We recall that the symbol nk , n, k ∈ N, 0 ≤ k ≤ n, counts the number of

ways of selecting k different objects from n different objects. Using

Pascal’s Identity

n n−1 n−1
(3.10) = + ,
k k−1 k
we obtain Pascal’s Triangle.

0
0

1 1
0 1

2 2 2
0 1 2

3 3 3 3
0 1 2 3
The Binomial Theorem 41

4 4 4 4 4
0 1 2 3 4

5 5 5 5 5 5
0 1 2 3 4 5

6 6 6 6 6 6 6
0 1 2 3 4 5 6
......................................
When the numerical values are substituted, the triangle then looks like
this.
1
121
1331
14641
1 5 10 10 5 1
1 6 15 20 15 6 1
.....................................
We see from Pascal’s Triangle that binomial coefficients are
symmetric.
This symmetry is easily justified by the identity k = n−k . We also
n n

notice that the binomial coefficients tend to increase until they reach the
middle, and that they decrease symmetrically. That is, the n
k
satisfy
n n n n n n n

0
< 1 < · · · < [n/2]−1 < [n/2] > [n/2]+1 > [n/2]+2 > · · · > n−1 >
n
if n is even, and that 0 < 1 < · · · < [n/2]−1 < [n/2] = [n/2]+1 >
n n n n n

n
n n n
> nn for odd n. We call this property the

[n/2]+2
> [n/2]+3 > · · · > n−1
unimodality of the binomial coefficients. Forexample, without finding the
exact numerical values we can see that 17 < 69 and that
200 200
200
= 200 < 200 .

131 69 99
We now present some examples on the use of binomial coefficients.
274 Example Prove Newton’s Identity:

n i n n−j
= ,
i j j j−i
for integers 0 ≤ j ≤ i ≤ n.
42 Chapter 3
Solution: We have

n i n!i! n!(n − j)!
= =
i j i!(n − i)!j!(i − j)! (n − j)!j!(n − i)!(i − j)!
which is the same as
n n−j
.
j i−j
275 Example Prove Pascal’s Identity:

n n−1 n−1
= + ,
k k−1 k
for integers 1 ≤ k ≤ n.
Solution: We have

n−1 n−1 (n − 1)! (n − 1)!
+ = +
k−1 k (k − 1)!(n − k)! k!(n − k − 1)!
(n − 1)! 1 1
= +
(n − k − 1)!(k − 1)! n − k k
(n − 1)! n
=
(n − k − 1)!(k − 1)! (n − k)k
n!
=
(n −
k)!k!
n
=
k
276 Example The Catalan number of order n is defined as

1 2n
Cn = .
n+1 n
Prove that Cn is an integer for all natural numbers n.
Solution: Observe that

1 2n 2n 2n
= − ,
n+1 n n n−1
the difference of two integers.
277 Example (P UTNAM 1972) Shew that no four consecutive binomial

coefficients
n n n n
, , ,
r r+1 r+2 r+3
(n, r positive integers and r + 3 ≤ n) are in arithmetic progression.
Solution:
Assume that
n n n n
. This yields

a = r , a + d = r+1 , a + 2d = r+2 , a + 3d = r+3

n n n
2 = + ,
r+1 r r+2
or equivalently
r+1 n−r−1
2= + (∗).
n−r r+2
This is a quadratic equation in r, having r as one of its roots. The
condition that the binomial coefficients are in arithmetic progression
means that r + 1 is also a root of (∗). Replacing r by n − r − 2 we also
obtain
n−r−1 r+1
2= + ,
r+2 n−r
which is the same as (∗). This means that n − r − 3 and n − r − 2 are also
roots of (∗). Since a quadratic equation can only have two roots, we must
have r = n − r − 3. The four binomial coefficients must then be

2r + 3 2r + 3 2r + 3 2r + 3
, , , .
r r+1 r+2 r+3
But these cannot be in an arithmetic progression, since binomial
coefficients are unimodal and symmetric.
278 Example Let N(a) denote the number of solutions to the equation
a = nk for nonnegative integers n, k. For example,

N(1) = ∞, N(3) = N(5) = 2, N(6) = 3, etc. Prove that N(a) ≤ 2 + 2 log2 a.
Solution: Let b be the first time that 2b > a. By the unimodality of the

b
binomial coefficients, i = j is monotonically increasing in i and j.
i+j i+j

Hence
b+i+b+j b+b+j 2b
≥ ≥ >a
b+j b b
44 Chapter 3
for all i, j ≥ 0. Hence i+j = a implies i < b, or j < b. Also, for each fixed

j
value of i (or j), i = a has at most one solution. It follows that
i+j

N(a) < 2b. Since

2(b − 1)
a≥ ≥ 2b−1 ,
b−1
it follows that b ≤ log2 a + 1, and the statement is proven.
We now use Pascal’s Triangle in order to expand the binomial
(a + b)n .
The Binomial Theorem states that for n ∈ Z, n ≥ 0,

X n
n n k
(1 + x) = x .
k=0
k
As a way of proving this, we observe that expanding
(1 + x)(1 + x) · · · (1 + x)
| {z }
n times
consists of adding up all the terms obtained from multiplying either a 1 or

a x from the first set of parentheses times either a 1 or an x from the
second set of parentheses etc. To get xk , x must be chosen from exactly
k of the sets of parentheses. Thus the number of x terms is k . It
k n
follows that
n
n n X n k

n n n n 2
(1 + x) = + x+ x + ··· + x = x .
0 1 2 n k=0
k
279 Example Prove that

n
X n
= 2n .
k=0
k
Solution: This follows from letting x = 1 in the expansion

Xn
n n k
(1 + x) = x .
k=0
k
280 Example Prove that for integer n ≥ 1,
n
X
n j n n−i
= 2 , i ≤ n.
j=i
j i i
Solution: Recall that by Newton’s Identity

n j n n−i
= .
j i i j−i
Thus
n
X Xn
n j n n−i
= .
j=0
j i i j=0 j − i
But upon re-indexing
n
X n−i
X
n−i n−i
= = 2n−i ,
j=0
j−i j=0
j
by the preceding problem. Thus the assertion follows.
X m + k
n+m+1

= .
k≤n
k n
46 Chapter 3
Solution: Using Pascal’s Identity

Xn
k+m 0+m 0+m 1+m 2+m 3+m
= + + + +
k=0
k −1 0 1 2 3

n−1+m n+m
+··· + +
n − 1 n
1+m 1+m 2+m 3+m
= + + +
0 1 2 3
n−1+m n+m
+··· + +
n − 1 n
2+m 2+m 3+m
= + +
1 2 3
n−1+m n+m
+··· + +
n − 1 n
3+m 3+m
= +
2 3
n−1+m n+m
+··· + +
n−1 n
..
.
n+m n+m
= +
n−1 n
n+m+1
= ,
n
which is what we wanted.
282 Example Find a closed formula for

X mn−1
n ≥ m ≥ 0.
0≤k≤m
k k
Solution: Using Newton’s Identity,

X mn−1 n −1 X n − k
= .
0≤k≤m
k k m 0≤k≤m
m − k
Re-indexing,
X n − k X n − m + k n + 1
= = ,
0≤k≤m
m − k k≤m
k m
by the preceding problem. Thus
X mn−1 n + 1 n n+1
= / = .
0≤k≤m
k k m m n + 1 − m
283 Example Simplify

X 100
.
0≤k≤50
2k
Solution: By the Binomial Theorem

100 100 100 100 100 100
(1 + 1) = + + + ... + +
0 1 2 99 100
100 100 100 100 100
(1 − 1)100 = − + − ... − + ,
0 1 2 99 100
whence summing both columns

100 100 100 100
2 =2 +2 + ... + 2 .
0 2 100
Dividing by 2, the required sum is thus 299 .

X50
100
.
k=1
2k − 1
Solution: We know that

100
X
100
= 2100
k=0
k
and
50
X
100
= 299 .
k=0
2k
The desired sum is the difference of these two values 2100 − 299 = 299 .
48 Chapter 3

10
X
k11
2 .
k=1
k
P
Solution: By the Binomial Theorem, the complete sum 11 2 = 311 .
11 k

k=0 k
The required sum lacks the zeroth term, 11 20 = 1, and the eleventh

0
term, 11 211 from this complete sum. The required sum is thus

11
311 − 211 − 1.
286 Example Which coefficient of the expansion of

10
1 2
+ x
3 3
has the greatest magnitude?
Solution: By the Binomial Theorem,

10 10
1 2 10 X 10 k 10−k
X
( + x) = (1/3) (2x/3) = ak x k .
3 3 k=0
k k=0
We consider the ratios ak

ak−1
,k = 1, 2, . . . n. This ratio is seen to be
ak 2(10 − k + 1)
= .
ak−1 k
This will be < 1 if k < 22/3 < 8. Thus a0 < a1 < a2 < . . . < a7 . If
k > 22/3, the ratio above will be < 1. Thus a7 > a8 > a9 > a10 . The
largest term is that of k = 7, i.e. the eighth term.
287 Example At what positive integral value of x is the x4 term in the

expansion of (2x + 9)10 greater than the adjacent terms?
Solution: We want to find integral x such that

10 4 6 10
(2x) (9) ≥ (2x)3 (9)7 ,
4 3
and
10 4 6 10
(2x) (9) ≥ (2x)5 (9)5 .
4 5
After simplifying the factorials, the two inequalities sought are
x ≥ 18/7
and
15/4 ≥ x.
The only integral x that satisfies this is x = 3.

X n
n
k = n2n−1 .
k=1
k
Pn
Solution: Let f(x) = (1 + x)n = n
xk . Then

k=0 k
Xn
0 n−1 n k−1
f (x) = n(1 + x) = k x .
k=0
k
Letting x = 1 we obtain
Xn
n−1 n
n2 = k ,
k=0
k
which is what we wanted.

Aliter: Using the absorption identity
Xn X n
n−1 n
n = k ,
k=0
k−1 k=0
k
with the convention that n−1

= 0. But since

−1
n
X n−1
X
n−1 n−1
= = 2n−1 ,
k=0
k−1 k=0
k
we obtain the result once again.

50 Chapter 3
289 Example Prove that for all n ∈ N, n ≥ 1,

n
X
n
2
k = n(n + 1)2n−2 .
k=1
k
Pn
Solution: Let f(x) = (1 + x)n = n
xk . Then

k=0 k
Xn
0 n−1 n k−1
f (x) = n(1 + x) = k x
k=0
k
and
Xn
0 n−1 n k
xf (x) = nx(1 + x) = k x .
k=0
k
Differentiating this last expression,
f 0 (x) + xf 00 (x) = n(1 + x)n−1 + n(n − 1)x(1 + x)n−2
which equals
n
X
2n k−1
k x .
k=0
k
Letting x = 1 in the above expression,
n
X
n−1 n−1 n
2
n2 + n(n − 1)2 = k ,
k=0
k
whence the result follows.

n
X
1 n
.
k=0
k+1 k
Solution: We have
Z1 Z1 X
n
n n
(1 + x) dx = xk dx.
0 0 k=0
k
Evaluating these integrals,

n
X
2n+1 1 n 1
− = .
n + 1 n + 1 k=0 k k
Aliter: Using the absorption identity

Xn n
1 X n+1

1 n 1
= = (2n+1 − 1).
k=0
k + 1 k n + 1 k=0
k + 1 n + 1
291 Example Let n ∈ N. Prove that

Xn
(−1)k+1 n

= 1 + 1/2 + 1/3 + · · · + 1/n.
k=1
k k
Solution: We evaluate the integral

Z1
1 − (1 − x)n
dx
0 x
in two different ways. First, making the substitution u = 1 − x, we obtain
Z1 Z1 Z1
1 − (1 − x)n 1 − un
dx = du = 1 + u + u2 + · · · + un−1 du,
0 x 0 1−u 0
from where we obtain the dextral side of the identity we want to prove. On
the other hand, evaluating the integral directly by expanding using the
Binomial Theorem,
Z1 Z1 Xn
1 − (1 − x)n n
dx = (−1)k−1 xk−1 dx,
0 x 0 k=1 k
which, after integration, becomes the sinistral side of the equality we

wanted to establish.
292 Example Prove that if m, n are nonnegative integers then

X n
n+1 k
= .
m+1 k=m
m
52 Chapter 3
Solution: Using Pascal’s Identity

Xn
k m m m+1 n
= + + + ··· +
k=m
m m+1 m m m

m+1 m+1 m+2 n
= + + + ··· +
m + 1 m m m
m+2 m+2 m+3 n
= + + + ··· +
m+1 m m m
..
.
n n
= +
m + 1 m
n+1
= .
m+1
293 Example Find a closed form for

X
k(k + 1).
k≤n
Solution: Let X
S= k(k + 1).
k≤n
Then
X k(k + 1) X k + 1
S/2! = = .
k≤n
2! k≤n
2
By the preceding problem
X k + 1
n+2

= .
k≤n
2 3
We gather that S = 2 n+2

3
= n(n + 1)(n + 2)/3.
294 Problem Prove that

X n

= 2n−1 .
2k + 1
0≤k≤n/2
295 Problem Expand

1 √ 1 √
(1 + x)100 + (1 − x)100 .
2 2

m jn j1
X X X
n+m

··· 1= .
jn =1 jn−1 =1 k=1
n+1
297 Problem The expansion of (x + 2y)20 contains two terms with the
same coefficient, Kxa yb and Kxa+1 yb−1 . Find a.
298 Problem Prove that for n ∈ N, n > 1 the identity

X n
k−1 n
(−1) k =0
k=1
k
holds true.
299 Problem If n is an even natural number, shew that

1 1 1 1 2n−1
+ + + ··· + = .
1!(n − 1)! 3!(n − 3)! 5!(n − 5)! (n − 1)!1! n!
300 Problem Find a closed formula for

X n − k
(−1)k .
0≤k≤n
k
301 Problem What is the exact numerical value of

X
k 100
k3 ?
k≤100
k

n
X
k2 − k.
k=1
54 Chapter 3

X m − k − 1
k m > n ≥ 0.
0≤k≤n
n − k − 1
(Hint: Write k = m − (m − k). Use the absorption identity to evaluate

Xn
m−k−1
(m − k) .)
k=0
n − k − 1

X 5k 100
?
k≤100
k+1 k
305 Problem Find n if 10 10 n

4
+ 3
= 4
.
Answer: 11.
306 Problem If

1991 1991 1991 1991
+ + + ··· + = 2a ,
1 3 5 1991
find a.
Answer: a = 1990.
307 Problem True or False:

20 20
= .
5 15
Answer: True.

48 49
49 = 10 .
9 10
Answer: True.
309 Problem What is the coefficient of x24 y24 in the expansion
(2x3 + 3y2 )20 ?
Answer: 20

8
(28 )(312 ).
310 Problem What is the coefficient of x12 y7 in the expansion
(x3/2 + y)15 ?
Answer: 15

8
.
311 Problem What is the coefficient of x4 y6 in

√
(x 2 − y)10 ?
Answer: 840.
312 Problem Shew that the binomial coefficients satisfy the following
hexagonal property:

n−1 n n+1 n−1 n+1 n
= .
k−1 k+1 k k k+1 k−1
313 Problem (A IME 1991) In the expansion

1000
X
1000 1000
(1 + 0.2) = (0.2)k ,
k=0
k
which one of the 1001 terms is the largest?
Answer: 166-th
314 Problem (P UTNAM 1971) Shew that for 0 < < 1 the expression
(x + y)n (x2 − (2 − )xy + y2 )

56 Chapter 3
is a polynomial with positive coefficients for integral n sufficiently large.

For = .002 find the smallest admissible value of n.
315 Problem Prove that for integer n ≥ 1,

Xn
3 n
k = n2 (n + 3)2n−3 .
k=1
k
316 Problem Which one of the following quantities is the largest?
(A) 49
+ 50 + · · · + 99

49 49 49
(B) 100
50
50 2
2 2
(C) + 50 + · · · + 50

0 1 50
(D) 200
100
Answer: D.
317 Problem Expand and simplify

p p
( 1 − x2 + 1)7 − ( 1 − x2 − 1)7 .
318 Problem Which of the following assertions is false?
(A) 200 200

17
< 20
(B) 199 199 200

25
+ 26
= 174
(C) 200
17
> 200
184 199
(D) 200 200
16
= 17 17
Answer: D.
319 Problem Simplify

5 6 7 999
+ + + ··· +
5 5 5 5
Answer: 1000

6

15 15 15 15 15 15
− + − ··· + −
1 2 3 4 13 14
Multinomial Theorem 57
Answer: 0, as 15 15
, 15 15
, etc.

1
= 14 2
= 13

1994
X
k−1 1994
(−1) ?
k=0
k
Answer: 0.

4 5 199 16 17 199
+ + ··· + > + + ··· + .
4 4 4 16 16 16
Answer: False. Sinistral side = 200

, dextral side = 200

5 17
323 Problem (A IME 1992) In which row of Pascal’s triangle (we start with
zeroth row, first row ,etc.) do three consecutive entries occur that are in
the ratio 3 : 4 : 5?
Answer: 62-nd
3.8 Multinomial Theorem

If n, n1 , n2 , . . . , nk are nonnegative integers and n = n1 + n2 + · · · nk we
put
n n!
= .
n1 , n 2 · · · n k n1 !n2 ! · · · nk !
It is easy to see combinatorially why this quantity is an integer, as we
know from (???). Proceeding in the same way we proved the Binomial
Theorem, we may establish the Multinomial Theorem:
X
(x1 + x2 + · · · + xk )n = xn1 1 xn2 2 · · · xnk k .
n1 +n2 +···+nk =n
n1 ,n2 ,...,nk ≥0
We give a few examples on the use of the Multinomial Theorem.

58 Chapter 3
324 Example Determine the coefficient of x2 y3 z3 in
(x + 2y + z)8
Solution: By the Multinomial Theorem

X
8

8
(x + 2y + z) = xn1 (2y)n2 zn3 .
n1 ;n2 ;n3 ≥0
n1 , n 2 , n 3
n1 +n2 +n3 =8
This requires n1 = 2, n2 = 3, n3 = 3. The coefficient sought is then

8
3

2 2,3,3 .
325 Example In (1 + x5 + x9 )23 , find the coefficient of x23 .
Solution: By the Multinomial Theorem

X
23

x5n2 +9n3 .
n ;n ;n ≥0
n 1 , n 2 , n 3
1 2 3
n1 +n2 +n3 =23
Since 5n2 + 9n3 = 23 and n1 + n2 + n3 = 23, we must have

n1 = 20, n2 = 1, n3 = 2. The coefficient sought is thus 20,1,2
23
.
326 Example How many different terms are there in the expansion of
(x + y + z + w + s + t)20 ?
Solution: There as many terms as nonnegative integral solutions of
n1 + n2 + · · · + n6 = 20.
But we know that there are 25 of these.

5
327 Problem How many terms are in the expansion (x + y + z)10 ?
Answer: 12

2
.
Multinomial Theorem 59
328 Problem Find the coefficient of x4 in the expansion of
(1 + 3x + 2x3 )10 ?
Answer: 6 10 10

1,1,8
+ 34 0,4,6
.
329 Problem Find the coefficient of x2 y3 z5 in the expansion of
(x + y + z)10 ?
Answer: 10

2,3,5
.
60 Chapter 3
Chapter 4
Arithmetic
4.1 Division Algorithm

330 Definition If a 6= 0, b are integers, we say that a divides b if there is
an integer c such that ac = b. We write this as a|b.
If a does not divide b we write a 6 |b. It should be clear that if a|b and
b 6= 0 then 1 ≤ |a| ≤ |b|.
331 Theorem 1. If c divides a and b then c divides any linear

combination of a and b. Tha is, if a, b, c, m, n are integers with
c|a, c|b, then c|(am + nb).
2. Division by an integer is transitive. That is, if x, y, z are integers with

x|y, y|z then x|z.
Proof There are integers s, t with sc = a, tc = b. Thus
am + nb = c(sm + tn),
giving c|(am + bn). Also, there are integers u, v with xu = y, yv = z.

Hence xuv = z, giving x|z.
A very useful property of the integers is the following:
61
62 Chapter 4
332 Theorem Division Algorithm Let a, b be integers, a > 0. There exist

integers q and r satisfying
(4.1) b = aq + r, 0 ≤ r < a
For example, 39 = 4 · 9 + 3. The Division Algorithm thus discriminates

integers according to the remainder they leave upon division by a. For
example, if a = 2, then according to the Division Algorithm, the integers
may be decomposed into the two families
A0 = {. . . − 4, −2, 0, 2, 4, . . .},
A1 = {. . . , −5, −3, −1, 1, 3, 5, . . .}.
Therefore, all integers have one of the forms 2k or 2k + 1. We mention in
passing that every integer of the form 2k + 1 is also of the form 2t − 1, for
2k + 1 = 2(k + 1) − 1, so it suffices to take t = k + 1.
If a = 4 we may decompose the integers into the four families
B0 = {. . . , −8, −4, 0, 4, 8, . . .},
B1 = {. . . , −7, −3, 1, 5, 9, . . .},
B2 = {. . . , −6, −2, 2, 6, 10, . . .},
B3 = {. . . , −5, −1, 3, 7, 11, . . .}.
Therefore any integer will take one of the forms 4k, 4k + 1, 4k + 2 or
4k + 3. Again, any integer of the form 4k + 1 is also of the form 4t − 3 and
any integer of the form 4k + 3 is also of the form 4t − 1.
333 Example Show that the square of any integer is of the form 4k or of
the form 4k + 1. That is, the square of any integer is either divisible by 4
or leaves remainder 1 upon division by 4.
Solution: If n is even, that is n = 2a, then n2 = (2a)2 = 4a2 , which is of

the form 4k. If n is odd, say n = 2t + 1, then n2 = (2t + 1)2 = 4(t2 + t) + 1,
which is of the form 4k + 1.
334 Example Show that no integer in the sequence

11, 111, 1111, 11111, . . .
is a perfect square.
Division Algorithm 63
Solution: Clearly 11 is not a square, so assume, that an integer of this

sequence has n > 2 digits. If n > 2,
11 . . . 1} = 11
| {z . . 11} 00 + 12 − 1 = 100 · 11
| .{z . . 11} +12 − 1.
| .{z
n 1 0s n−2 1 0 s n−2 1 0 s
Hence any integer in this sequence is of the form 4k − 1. By the

preceding problem, no integer of the form 4k − 1 can be a square. This
finishes the proof.
335 Example Show that n2 + 23 is divisible by 24 for infinitely many values

of n.
Solution: Observe that n2 + 23 = n2 − 1 + 24 = (n − 1)(n + 1) + 24.

Therefore the families of integers n = 24m ± 1, m = 0, ±1, ±2, ±3, . . .
produce infinitely many values such that n2 + 23 is divisible by 24.
336 Example Show that the square of any prime greater than 3 leaves
remainder 1 upon division by 12.
Solution: If p > 3 is prime, then p is of one of the forms 6k ± 1.

Now,
(6k ± 1)2 = 12(3k2 ± k) + 1,
proving the assertion.
337 Example Prove that if p and 8p − 1 are prime, then 8p + 1 is

composite.
Solution: If p = 3, 8p − 1 = 23 and 8p + 1 = 25, then the assertion is true

for p = 3. If p > 3, then either p = 3k + 1 or p = 3k + 2. If
p = 3k + 1, 8p − 1 = 24k − 7 and 8p + 1 = 24k − 6, which is divisible by 6
and hence not prime. If p = 3k + 2, 8p − 1 = 24k − 15 is not a prime, .
338 Example Show that if 3n + 1 is a square, then n + 1 is the sum of

three squares.
Solution: Clearly 3n + 1 is not a multiple of 3, and so 3n + 1 = (3k ± 1)2 .

64 Chapter 4
Therefore
(3k ± 1)2 − 1
n+1= + 1 = 3k2 ± 2k + 1 = k2 + k2 + (k ± 1)2 ,
3
as we wanted to show.
339 Example (A HSME 1976) Let r be the common remainder when

1059, 1417 and 2312 are divided by d > 1. Find d − r.
Solution: By the division algorithm there are integers q1 , q2 , q3 with

1059 = dq1 + r, 1417 = dq2 + r and 2312 = dq3 + r. Subtracting we get
1253 = d(q3 − q1 ), 895 = d(q3 − q2 ) and 358 = d(q2 − q1 ). Notice that d is
a common divisor of 1253, 895, and 358. As 1253 = 7 · 179, 895 = 5 · 179,
and 358 = 2 · 179, we see that 179 is the common divisor greater than 1 of
all three quantities, and so d = 179. Since 1059 = 179q1 + r, and
1059 = 5 · 179 + 164, we deduce that r = 164. Finally, d − r = 15.
340 Example Show that from any three integers, one can always choose
two so that a3 b − ab3 is divisible by 10.
Solution: It is clear that a3 b − ab3 = ab(a − b)(a + b) is always even, no

matter which integers are substituted. If one of the three integers is of the
form 5k, then we are done. If not, we are choosing three integers that lie
in the residue classes 5k ± 1 or 5k ± 2. By the Pigeonhole Principle, two
of them must lie in one of these two groups, and so there must be two
whose sum or whose difference is divisible by 5. The assertion follows.
341 Problem Find all positive integers n for which
n + 1|n2 + 1.
342 Problem If 7|3x + 2 prove that 7|(15x2 − 11x + 14.).
343 Problem Show that the square of any integer is of the form 3k or
3k + 1.
Division Algorithm 65
344 Problem Prove that if 3|(a2 + b2 ), then 3|a and 3|b
(Hint: Argue by contradiction. Assume a = 3k ± 1 or b = 3m ± 1.)
345 Problem Show that if the sides of a right triangle are all integers, then
3 divides one of the lengths of a side.
346 Problem Given that 5 divides (n + 2), which of the following are
divisible by 5
n2 − 4, n2 + 8n + 7, n4 − 1, n2 − 2n?
347 Problem Prove that there is no prime triplet of the form p, p + 2, p + 4,

except for 3, 5, 7.
348 Problem Find the largest positive integer n such that
(n + 1)(n4 + 2n) + 3(n3 + 57)
be divisible by n2 + 2.
Answer: 13
349 Problem Demonstrate that if n is a positive integer such that 2n + 1 is

a square, then n + 1 is the sum of two consecutive squares.
350 Problem Show that the product of two integers of the form 4n + 1 is
again of this form. Use this fact and an argument by contradiction similar
to Euclid’s to prove that there are infinitely many primes of the form 4n − 1.
351 Problem Prove that there are infinitely many primes of the form
6n − 1.
352 Problem Prove that there are infinitely many primes p such that p − 2
is not prime.
353 Problem Demonstrate that there are no three consecutive odd

integers such that each is the sum of two squares greater than zero.
66 Chapter 4
354 Problem Let n > 1 be a positive integer. Prove that if one of the
numbers 2n − 1, 2n + 1 is prime, then the other is composite.
355 Problem Prove that there are infinitely many integers n such that
4n2 + 1 is divisible by both 13 and 5.
356 Problem Prove that any integer n > 11 is the sum of two positive
composite numbers.
Hint: Think of n − 6 if n is even and n − 9 if n is odd.
357 Problem Prove that 3 never divides n2 + 1.
358 Problem Show the existence of infinitely many natural numbers x, y

such that x(x + 1)|y(y + 1) but
x 6 |y and (x + 1) 6 |y,
and also
x 6 |(y + 1) and (x + 1) 6 |(y + 1).
Hint: Try x = 36k + 14, y = (12k + 5)(18k + 7).
4.2 The Decimal Scale

Any natural number n can be written in the form
n = a0 10k + a1 10k−1 + a2 10k−2 + · · · + ak−1 10 + ak
where 1 ≤ a0 ≤ 9, 0 ≤ aj ≤ 9, j ≥ 1. This is the decimal representation of

n. For example
65789 = 6 · 104 + 5 · 103 + 7 · 102 + 8 · 10 + 9.
359 Example Find a reduced fraction equivalent to the repeating decimal

0.123 = 0.123123123 . . . .
The Decimal Scale 67
Solution: Let N = 0.123123123 . . . . Then 1000N = 123.123123123 . . . .

123 41
Hence 1000N − N = 123, whence N = = .
999 333
360 Example What are all the two-digit positive integers in which the
difference between the integer and the product of its two digits is 12?
Solution: Let such an integer be 10a + b, where a, b are digits. Solve

10a + b − ab = 12 for a getting
12 − b 2
a= =1+ .
10 − b 10 − b
Since a is an integer, 10 − b must be a positive integer that divides 2. This
gives b = 8, a = 2 or b = 9, a = 3. Thus 28 and 39 are the only such
integers.
361 Example Find all the integers with initial digit 6 such that if this initial
integer is suppressed, the resulting number is 1/25 of the original number.
Solution: Let x be the integer sought. Then x = 6 · 10n + y where y is a

positive integer. The given condition stipulates that
1
y= (6 · 10n + y) ,
25
that is,
10n
y= = 25 · 10n−2 .
4
This requires n ≥ 2, whence y = 25, 250, 2500, 25000, etc.. Therefore
x = 625, 6250, 62500, 625000, etc..
362 Example (I MO 1968) Find all natural numbers x such that the product
of their digits (in decimal notation) equals x2 − 10x − 22.
Solution: Let x have the form
x = a0 + a1 10 + a2 102 + · · · + an 10n , ak ≤ 9, an 6= 0.
Let P(x) be the product of the digits of x, P(x) = x2 − 10x − 22. Now
P(x) = a0 a1 · · · an ≤ 9n an < 10n an ≤ x (strict inequality occurs when x
68 Chapter 4
has more than one digit). This means that x2 − 10x − 22 ≤ x which entails
that x < 13, whence x has one digit or x = 10, 11 or 12. Since
x2 − 10x − 22 = x has no integral solutions, x cannot have one digit. If
x = 10, P(x) = 0, but x2 − 10x − 22 6= 0. If x = 11, P(x) = 1, but
x2 − 10x − 22 6= 1. The only solution is seen to be x = 12.
363 Example A whole number decreases an integral number of times

when its last digit is deleted. Find all such numbers.
Solution: Let 0 ≤ y ≤ 9, and 10x + y = mx, where m, x are natural

y
numbers. This requires 10 + = m, an integer. Hence, x must divide y.
x
If y = 0, any natural number x will do, as we obtain multiples of 10. If
y = 1 then x = 1, and we obtain 11. Continuing in this fashion, the sought
number are the multiples of 10, together with the numbers 11, 12, 13, 14,
15, 16, 17, 18, 19, 22, 24, 26, 28, 33, 36, 39, 44, 55, 77, 88, and 99.
364 Example Show that all integers in the sequence
49, 4489, 444889, 44448889, 44

| .{z
. . 44} 88
| .{z
. . 88} 9
n 4 0s n−1 8 0 s
are perfect squares.

44
| .{z
. . 44} 88 . . 88} 9 = 44
| .{z . . 44} ·10n + 88
| .{z . . 88} ·10 + 9
| .{z
n 4 0s n−1 8 0 s n 4 0s n−1 8 0 s
4
= 9
· (10n − 1) · 10n + 98 · (10n−1 − 1) · 10 + 9
4
= 9
· 102n + 49 · 10n + 19
= 1
9
(2 · 10n + 1)2
2·10n +1 2

= 3
We must show that this last quantity is an integer, that is, that 3 divides
2 · 10n + 1 = 2 00 . . 00} 1. But the sum of the digits of this last quantity is 3,
| .{z
n−1 0 0 s
2 · 10n + 1
which makes it divisible by 3. In fact, = 6| .{z
. . 6} 7
3
n−1 6 s
0
365 Example (A IME 1987) An ordered pair (m, n) of non-negative

integers is called simple if the addition m + n requires no carrying. Find
the number of simple ordered pairs of non-negative integers that add to
1492.
Solution: Observe that there are d + 1 solutions to x + y = d, where x, y

are positive integers and d is a digit. These are
(0 + d), (1 + d − 1), (2 + d − 2), . . . , (d + 0)

Since there is no carrying, we search for the numbers of solutions of this
form to x + y = 1, u + v = 4, s + t = 9, and a + b = 2. Since each separate
solution may combine with any other, the total number of simple pairs is
(1 + 1)(4 + 1)(9 + 1)(2 + 1) = 300.
366 Example (A IME 1992) For how many pairs of consecutive integers in
{1000, 1001, . . . , 2000}
is no carrying required when the two integers are added?
Solution: Other than 2000, a number on this list has the form
n = 1000 + 100a + 10b + c, where a, b, c are digits. If there is no carrying
in n + n + 1 then n has the form
1999, 1000 + 100a + 10b + 9, 1000 + 100a + 99, 1000 + 100a + 10b + c
with 0 ≤ a, b, c ≤ 4, i.e., five possible digits. There are 53 = 125 integers
of the form 1000 + 100a + 10b + c, 0 ≤ a, b, c ≤ 4, 52 = 25 integers of the
form 1000 + 100a + 10b + 9, 0 ≤ a, b ≤ 4, and 5 integers of the form
1000 + 100a + 99, 0 ≤ a ≤ 4. The total of integers sought is thus
125 + 25 + 5 + 1 = 156.
367 Example (A IME 1994) Given a positive integer n, let p(n) be the
product of the non-zero digits of n. (If n has only one digit, then p(n) is
equal to that digit.) Let
S = p(1) + p(2) + · · · + p(999).
Find S.
70 Chapter 4
Solution: If x = 0, put m(x) = 1, otherwise put m(x) = x. We use three

digits to label all the integers, from 000 to 999 If a, b, c are digits, then
clearly p(100a + 10b + c) = m(a)m(b)m(c). Thus
p(000) + p(001) + p(002) + · · · + p(999) = m(0)m(0)m(0) + m(0)m(0)m(1) + m(0)m
· · · + m(9)m(9)m(9)
= (m(0) + m(1) + · · · + m(9))3
= (1 + 1 + 2 + · · · + 9)3
= 463
= 97336.
Hence
S = p(001) + p(002) + · · · + p(999)
= 97336 − p(000)
= 97336 − m(0)m(0)m(0)
= 97335.
368 Example (A IME 1992) Let S be the set of all rational numbers r,
0 < r < 1, that have a repeating decimal expansion of the form
0.abcabcabc . . . = 0.abc,
where the digits a, b, c are not necessarily distinct. To write the elements
of S as fractions in lowest terms, how many different numerators are
required?
abc
Solution: Observe that 0.abcabcabc . . . = , and that 999 = 33 · 37. If
999
abc is neither divisible by 3 nor by 37, the fraction is already in lowest
terms. By Inclusion-Exclusion there are

999 999 999
999 − + + = 648
3 37 3 · 37
s
such fractions. Also, fractions of the form where s is divisible by 3 but
37
not by 37 are in S. There are 12 fractions of this kind (with s = 3, 6, 9, 12,
l
. . . , 36). We do not consider fractions of the form t , t ≤ 3 with l divisible
3
by 37 but not by 3, because these fractions are > 1 and hence not in S.
The total number of distinct numerators in the set of reduced fractions is
thus 640 + 12 = 660.
Problems
369 Problem Find an equivalent fraction for the repeating decimal 0.3172.
370 Problem A two-digit number is divided by the sum of its digits. What
is the largest possible remainder?
371 Problem Show that the integer
11
| .{z
. . 11}
221 1 0 s
is a composite number.
372 Problem Let a and be be the integers
a = 111
| {z. . . 1}
m 1 0s
b = 1 000
| {z. . . 0} 5.
m−1 0 0 s
Show that ab + 1 is a perfect square.
373 Problem What digits appear on the product
. . 3} · 6| .{z
3| .{z . . 6} ?
666 3 0 s 666 6 0 s
374 Problem Show that there exist no integers with the following property:
if the initial digit is suppressed, the resulting integer is 1/35 of the original
number.
375 Problem Show that the sum of all the integers of n digits, n ≥ 3, is
494 99 . . . 9} 55 00
| {z . . . 0} .
| {z
n−3 9 0 s n−2 0 0 s
72 Chapter 4
376 Problem Show that for any positive integer n,
11 . . . 1} − 22
| {z . . . 2}
| {z
2n 1 0 s n 2 0s
is a perfect square.
377 Problem A whole number is equal to the arithmetic mean of all the
numbers obtained from the given number with the aid of all possible
permutation of its digits. Find all whole numbers with that property.
378 Problem The integer n is the smallest multiple of 15 such that every
n
digit of n is either 0 or 8. Compute .
15
379 Problem Show that Champernowne’s number
0.12345678910111213141516171819202122 . . .
, which is the sequence of natural numbers written after the decimal point,
is irrational.
380 Problem Given that

1
= 0.020408163265306122448979591836734693877551, find the last
49
thousand digits of
1 + 50 + 502 + · · · + 50999 .
381 Problem Let t be a positive real number. Prove that there is a positive
integer n such that the decimal expansion of nt contains a 7.
382 Problem (A IME 1989) Suppose that n is a positive integer and d is a

single digit in base-ten. Find n if
n
= 0.d25d25d25d25d25 . . .
810
383 Problem (A IME 1988) Find the smallest positive integer whose cube
ends in 888.
Non-decimal Scales 73
384 Problem (A IME 1986) In the parlor game, the “magician” asks one of
the participants to think of a three-digit number abc, where a, b, c
represent the digits of the number in the order indicated. The magician
asks his victim to form the numbers
acb, bac, cab, cba,
to add these numbers and to reveal their sum N. If told the value of N,
the magician can identify abc. Play the magician and determine abc if
N = 319.
385 Problem (A IME 1988) For any positive integer k, let f1 (k) denote the
square of the sums of the digits of k. For n ≥ 2, let fn (k) = f1 (fn−1 (k)).
Find f1988 (11).
386 Problem (I MO 1969) Determine all three-digit numbers N that are

N
divisible by 11 and such that equals the sum of the squares of the
11
digits of N.
387 Problem (I MO 1962) Find the smallest natural number having the last
digit 6 and if this 6 is erased and put in from of the other digits, the
resulting number is four times as large as the original number.
4.3 Non-decimal Scales

The fact that most people have ten fingers has fixed our scale of notation
to the decimal. Given any positive integer r > 1, we can, however,
express any number x in base r.
If n is a positive integer, and r > 1 is an integer, then n has the base-r
representation
n = a0 + a1 r + a2 r2 + · · · + ak rk , 0 ≤ at ≤ r − 1, ak 6= 0, rk ≤ n < rk+1 .
We use the convention that we shall refer to a decimal number without

referring to its base, and to a base-r number by using the subindex r .
388 Example Express the decimal number 5213 in base-seven.

74 Chapter 4
Solution: Observe that 5213 < 75 . We thus want to find

0 ≤ a0 , . . . , a4 ≤ 6, a4 6= 0 such that
5213 = a4 74 + a3 73 + a2 72 + a1 7 + a0 .
Dividing by 74 , we obtain 2+ proper fraction = a4 + proper fraction. This

means that a4 = 2. Thus 5213 = 2 · 74 + a3 73 + a2 72 + a1 7 + a0 or
411 = 5213 = a3 73 + a2 72 + a1 7 + a0 . Dividing by 73 this last equality we
obtain 1+ proper fraction = a3 + proper fraction, and so a3 = 1.
Continuing in this way we deduce that 5213 = 211257 .
The method of successive divisions used in the preceding problem can
be conveniently displayed as
7 5212 5
7 744 2
7 106 1
7 15 1
7 2 2
The central column contains the successive quotients and the rightmost
column contains the corresponding remainders. Reading from the last
remainder up, we recover 5213 = 211257 .
389 Example Write 5627 in base-five.
Solution: 5627 = 5 · 72 + 6 · 7 + 2 = in decimal scale, so the problem

reduces to convert 289 to base-five. Doing successive divisions,
5 289 4
5 57 2
5 11 1
5 2 2
Thus 5627 = 289 = 21245 .
13
390 Example Express the fraction in base-six.
16
Solution: Write
13 a1 a2 a3 a4
= + 2 + 3 + 4 + ···
16 6 6 6 6
Non-decimal Scales 75
Multiplying by 6, we obtain 4+ proper fraction = a1 + proper fraction, so

a1 = 4. Hence
13 4 7 a2 a3 a4
− = = 2 + 3 + 4 + ···
16 6 48 6 6 6
Multiply by 6 we obtain 5+ proper fraction = a2 + proper fraction, and so
2
a2 = 5. Continuing in this fashion

13 4 5 1 3
= + 2 + 3 + 4 = 0.45136 .
16 6 6 6 6
We may simplify this procedure of successive multiplications by recurring
to the following display:
6 13
16
4
6 7
8
5
6 1
4
1
6 1
2
3
The third column contains the integral part of the products of the first
column and the second column. Each term of the second column from
the second on is the fractional part of the product obtained in the
preceding row. Thus 6 · 13
16
− 4 = 78 , 6 · 78 − 5 = 41 , etc..
391 Example Prove that 4.41r is a perfect square in any scale of notation.
Solution: 2
4 4 1
4.41r = 4 + + 2 = 2+
r r r
392 Example (A IME 1986) The increasing sequence

1, 3, 4, 9, 10, 12, 13, . . .
consists of all those positive integers which are powers of 3 or sums of
distinct powers or 3. Find the hundredth term of the sequence.
Solution: If the terms of the sequence are written in base-three, they

comprise the positive integers which do not contain the digit 2. Thus the
terms of the sequence in ascending order are
13 , 103 , 113 , 1003 , 1013 , 1103 , 1113 , . . .
76 Chapter 4
In the binary scale these numbers are, of course, the ascending natural
numbers 1, 2, 3, 4, . . .. Therefore to obtain the 100th term of the sequence
we write 100 in binary and then translate this into ternary: 100 = 11001002
and 11001003 = 36 + 35 + 32 = 981.
393 Example (A HSME 1993) Given 0 ≤ x0 < 1, let

2xn−1 if 2xn−1 < 1,
xn =
2xn−1 − 1 if 2xn−1 ≥ 1.
for all integers n > 0. For how many x0 is it true that x0 = x5 ?
Solution: Write x0 in binary,

∞
X ak
x0 = , ak = 0 or 1.
k=1
2k
The algorithm given moves the binary point one unit to the right. For x0 to
equal x5 we need (0.a1 a2 a3 a4 a5 a6 a7 . . .)2 = (0.a6 a7 a8 a9 a10 a11 a12 . . .)2 .
This will happen if and only if x0 has a repeating expansion with
a1 a2 a3 a4 a5 as the repeating block. There are 25 = 32 such blocks. But if
a1 = a2 = · · · = a5 = 1 then x0 = 1, which lies outside ]0, 1[. The total
number of values for which x0 = x5 is therefore 32 − 1 = 31.
Problems
394 Problem Express the decimal number 12345 in every scale from
binary to base-nine.
395 Problem Distribute the 27 weights of 12 , 22 , 32 , . . . , 272 lbs each into

three separate piles, each of equal weight.
396 Problem Let C denote the class of positive integers which, when
written in base-three, do not require the digit 2. Prove that no three
integers in C are in arithmetic progression.
397 Problem What is the largest integer that I should be permitted to

choose so that you may determine my number in twenty “yes” or “no”
questions?
Well-Ordering Principle 77
398 Problem Let bxc denote the greatest integer less than or equal to x.
Does the equation
bxc + b2xc + b4xc + b8xc + b16xc + b32xc = 12345
have a solution?
4.4 Well-Ordering Principle

The set N = {1, 2, 3, 4, . . .} of natural numbers is endowed with two
operations, addition and multiplication, that satisfy the following properties
for natural number a, b, and c:
1. Closure: a + b and ab are also natural numbers,
2. Commutativity: a + b = b + a and ab = ba,
3. Associative Laws: (a + b) + c = a + (b + c) and (ab)c = a(bc),
4. Distributive Law: a(b + c) = ab + ac
5. Multiplicative Identity: 1a = a.
One further property of the natural numbers is the following.
Well-Ordering Axiom: Every non-empty subset S of the natural numbers

has a least element.
As an example of the use of the Well-Ordering Axiom let us prove that
there is no integer between 0 and 1.
399 Example Prove that there is no integer in the open interval ]0, 1[.
Solution: Assume to the contrary that the set S of integers in ]0, 1[ is

non-empty. As a set of positive integers, by Well-Ordering it must contain
a least element, say m. Since 0 < m < 1, we have 0 < m2 < m < 1. But
this last string of inequalities says that m2 is an integer in ]0, 1[ which is
smaller than m, the smallest integer in ]0, 1[. This contradiction shows
that m cannot exist.
Recall that an irrational number is one that cannot be represented as the
ratio of two integers.
78 Chapter 4
√
400 Example Prove that 2 is irrational.
√
Solution:√The proof is by contradiction. Suppose that 2 were rational,
i.e., that 2 = ab for some integers a, b, b 6= 0. This implies that the set
√ √
A = {n 2 : both n and n 2 positive integers}
is non-empty since√it contains

√ a. By Well-Ordering, A has a smallest
element,
√ say √
j=k √ 2. As √2 − 1 > 0, √
j( 2 − 1) =√j 2 −√k 2 = 2(j √ − k), is a positive integer. Since 2 < 2 2
implies 2 − 2 < 2 and also j 2 = 2k, we see that
√ √ √
(j − k) 2 = k(2 − 2) < k 2 = j.
√
Thus (j − k) 2 is a positive integer in A which is smaller than j. This
contradicts the choice of j as the smallest integer in A and hence,
finishes the proof.
401 Example Let a, b, c be integers such that a6 + 2b6 = 4c6 . Show that
a = b = c = 0.
Solution: Clearly we can restrict ourselves to non-negative numbers.

Choose a triplet of non-negative integers a, b, c satisfying this equation
and with
max(a, b, c) > 0
as small as possible. If a6 + 2b6 = 4c6 , then a must be even, a = 2a1 .

This leads to 32a61 + b6 = 2c6 . This implies that b is even, b = 2b1 and so
16a61 + 32b61 = c6 . This implies that c is even, c = 2c1 and so
a61 + 2b61 = 4c61 . But clearly max(a1 , b1 , c1 ) < max(a, b, c). We have
produce a triplet of integers with a maximum smaller than the smallest
possible maximum, a contradiction.
a2 + b 2
402 Example (I MO 1988) If a, b are positive integers such that is
1 + ab
a2 + b 2
an integer, then show that must be a square.
1 + ab
Well-Ordering Principle 79
a2 + b 2
Solution: Suppose that = k is a counterexample of an integer
1 + ab
which is not a perfect square, with max(a, b) as small as possible. We
may assume without loss of generality that a < b for if a = b then
2a2 2
0<k= = 2 − < 2,
a2 + 1 a2 + 1
which forces k = 1, a square.
Now, a2 + b2 − k(ab + 1) = 0 is a quadratic in b with sum of roots ka and
product of roots a2 − k. Let b1 , b be its roots, so b1 + b = ka, bb1 = a2 − k.
As a, k are positive integers, supposing b1 < 0 is incompatible with
a2 + b21 = k(ab1 + 1). As k is not a perfect square, supposing b1 = 0 is
incompatible with a2 + 02 = k(0 · a + 1). Also
a2 − k b2 − k k
b1 = < = b − < b.
b b b
a2 + b21
Thus we have shown b1 to be a positive integer with = k smaller
1 + ab1
than b. This is a contradiction to the choice of b. Such a counterexample
a2 + b 2
k cannot exist, and so must be a perfect square. In fact, it can be
1 + ab
a2 + b 2
shown that is the square of the greatest common divisor of a and
1 + ab
b.
Problems
403 Problem Find all integers solutions of a3 + 2b3 = 4c3 .
404 Problem Prove that the equality x2 + y2 + z2 = 2xyz can hold for
whole numbers x, y, z only when x = y = z = 0.
405 Problem Show that the series of integral squares does not contain an
infinite arithmetic progression.
406 Problem Prove that x2 + y2 = 3(z2 + w2 ) does not have a positive

integer solution.
80 Chapter 4
4.5 Mathematical Induction

The Principle of Mathematical Induction is based on the following fairly
intuitive observation. Suppose that we are to perform a task that involves
a certain finite number of steps. Suppose that these steps are sequential.
Finally, suppose that we know how to perform the n-th step provided we
have accomplished the n − 1-th step. Thus if we are ever able to start the
task (that is, if we have a base case), then we should be able to finish it
(because starting with the base we go to the next case, and then to the
case following that, etc.).
We formulate the Principle of Mathematical Induction (PMI) as follows:
Principle of Mathematical Induction Suppose we have an assertion

P(n) concerning natural numbers satisfying the following two properties:
(PMI I) P(k0 ) is true for some natural number k0 ,
(PMI II) If P(n − 1) is true then P(n) is true.

Then the assertion P(n) is true for every n ≥ k0 .
407 Example Prove that the expression 33n+3 − 26n − 27 is a multiple of

169 for all natural numbers n.
Let P(n) be the assertion “33n+3 − 26n − 27 is a multiple of 169.” Observe

that 33(1)+3 − 26(1) − 27 = 676 = 4(169) so P(1) is true. Assume the truth
of P(n − 1), that is, that there is an integer M such that
33(n−1)+3 − 26(n − 1) − 27 = 169M.
This entails
33n − 26n − 1 = 169M.
Now
33n+3 − 26n − 27 = 27 · 33n − 26n − 27
= 27(33n − 26n − 1) + 676n
= 27(169M) + 169 · 4n
= 169(27M + 4n),
and so the truth of P(n − 1) implies the truth of P(n). The assertion then
follows for all n ≥ 1 by PMI.
Mathematical Induction 81

√ √ 2n
(1 + 2)2n + (1 − 2)
is an even integer and that

√ √ √
(1 + 2)2n − (1 − 2)2n = b 2
for some positive integer b, for all integers n ≥ 1.
Solution: Let P(n) be the assertion: “

√ √ 2n
(1 + 2)2n + (1 − 2)
is an even integer and that

√ √ √
(1 + 2)2n − (1 − 2)2n = b 2
for some positive integer b.” We see that P(1) is true since
√ √
(1 + 2)2 + (1 − 2)2 = 6,
and √ 2 √ √
(1 + 2) − (1 − 2)2 = 4 2.
Assume now that P(n − 1), i.e., assume that
√ 2(n−1) √
(1 + 2) + (1 − 2)2(n−1) = 2N
for some integer N and that

√ √ √
(1 + 2)2(n−1) − (1 − 2)2(n−1) = a 2
for some positive integer a. Consider now the quantity

√ √ 2n √ 2 √ √ 2 √
(1 + 2)2n + (1 − 2) = (1 + √2) (1 + √2)2n−2 + (1 − √
2) (1 − √2)2n−2
= (3 + 2 2)(1 + 2)2n−2 + (3 − 2 2)(1 − 2)2n−2
= 12N + 4a
= 2(6n + 2a),
82 Chapter 4
an even integer. Similarly

√ √ √ √ √ 2 √
(1 + 2)2n − (1 − 2)2n = (1 + √2)2 (1 + √2)2n−2 − (1 − √2) (1 − √2)2n−2
2n−2
= (3 √ √ + 2)
+ 2 2)(1 − (3 − 2 2)(1 − 2)2n−2
= 3a 2 + 2 √2(2N)
= (3a + 4N) 2,
√
which is of the form b 2. This implies that P(n) is true. The statement of
the problem follows by PMI.
409 Example Prove that if k is odd, then 2n+2 divides

n
k2 − 1
for all natural numbers n.
Solution: The statement is evident for n = 1, as k2 − 1 = (k − 1)(k + 1) is

divisible by 8 for any odd natural number k since k − 1 and k + 1 are
n
consecutive even integers. Assume that 2n+2 a = k2 − 1 for some integer
a. Then
n+1 n n n
k2 − 1 = (k2 − 1)(k2 + 1) = 2n+2 a(k2 + 1).
n n
Since k is odd, k2 + 1 is even and so k2 + 1 = 2b for some integer b.
This gives
n+1 n
k2 − 1 = 2n+2 a(k2 + 1) = 2n+3 ab,
and so the assertion follows by PMI.
410 Example Let s be a positive integer. Prove that every interval [s, 2s]
contains a power of 2.
Solution: If s is a power of 2, then there is nothing to prove. If s is not a

power of 2 then it must lie between two consecutive powers of 2, say
2r < s < 2r+1 . This yields 2r+1 < 2s. Hence s < 2r+1 < 2s, which yields the
result.
411 Definition The Fibonacci Numbers are given by

f0 = 0, f1 = 1, fn+1 = fn + fn−1 , n ≥ 1, that is every number after the
second one is the sum of the preceding two.
The Fibonacci sequence then goes like 0, 1, 1, 2, 3, 5, 8, 13, 21, . . . .

fn−1 fn+1 = f2n + (−1)n+1 .
Solution: If n = 1, then 2 = f0 f2 = 12 + (−1)2 = f21 + (−1)1+1 . If

fn−1 fn+1 = f2n + (−1)n+1 then using the fact that fn+2 = fn + fn+1 ,
fn fn+2 = fn (fn + fn+1 )
= f2n + fn fn+1
= fn−1 fn+1 − (−1)n+1 + fn fn+1
= fn+1 (fn−1 + fn ) + (−1)n+2
= f2n+1 + (−1)n+2 ,
which establishes the assertion by induction.
413 Example Prove that a given square can be decomposed into n

squares, not necessarily of the same size, for all n = 4, 6, 7, 8, . . ..
Solution: A quartering of a subsquare increases the number of squares

by three (four new squares are gained but the original square is lost). The
figure below shows that n = 4 is achievable.$.4in]
If n were achievable, a quartering would make {n, n + 3, n + 6, n + 9, . . .}

also achievable. We will show now that n = 6 and n = 8 are achievable.
But this is easily seen from the figures below, and this finishes the
proof.$.4in]
Sometimes it is useful to use the following version of PMI, known as the

Principle of Strong Mathematical Induction (PSMI).
Principle of Strong Mathematical Induction Suppose we have an

assertion P(n) concerning natural numbers satisfying the following two
properties:
84 Chapter 4
(PSMI I) P(k0 ) is true for some natural number k0 ,

(PSMI II) If m < n and P(m), P(m + 1), . . . , P(n − 1) are true then
P(n) is true.
Then the assertion P(n) is true for every n ≥ k0 .
414 Example In the country of SmallPesia coins only come in values of 3

and 5 pesos. Show that any quantity of pesos greater than or equal to 8
can be paid using the available coins.
Solution: We use PSMI. Observe that 8 = 3 + 5, 9 = 3 + 3 + 3, 10 = 5 + 5,

so, we can pay 8, 9, or 10 pesos with the available coinage. Assume that
we are able to pay n − 3, n − 2, and n − 1 pesos, that is, that 3x + 5y = k
has non-negative solutions for k = n − 3, n − 2 and n − 1. We will show
that we may also obtain solutions for 3x + 5y = k for k = n, n + 1 and
n + 2. Now
3x + 5y = n − 3 =⇒ 3(x + 1) + 5y = n,
3x1 + 5y1 = n − 2 =⇒ 3(x1 + 1) + 5y1 = n + 1,
3x2 + 5y2 = n − 1 =⇒ 3(x2 + 1) + 5y2 = n + 2,
and so if the amounts n − 3, n − 2, n − 1 can be paid so can
n, n + 1, n + 2. The statement of the problem now follows from PSMI.
415 Example (U SAMO 1978) An integer n will be called good if we can

write
n = a 1 + a2 + · · · + a k ,
where the integers a1 , a2 , . . . , ak are positive integers (not necessarily
distinct) satisfying
1 1 1
+ + ··· = 1.
a1 a2 ak
Given the information that the integers 33 through 73 are good, prove that
every integer ≥ 33 is good.
Solution: We first prove that if n is good, then 2n + 8 and 2n + 9 are also

good. For assume that n = a1 + a2 + · · · + ak , and
1 1 1
+ + ··· = 1.
a1 a2 ak
Then 2n + 8 = 2(a1 + a2 + · · · + ak ) + 4 + 4 and
1 1 1 1 1 1 1 1
+ + ··· + + = + + = 1.
2a1 2a2 2ak 4 4 2 4 4
Also 2n + 9 = 2(a1 + a2 + · · · + ak ) + 3 + 6 and
1 1 1 1 1 1 1 1
+ + ··· + + = + + = 1.
2a1 2a2 2ak 3 6 2 3 6
Therefore
if n is good then 2n + 8 and 2n + 9 are good (*)
We now establish the truth of the assertion of the problem by induction on

n. Let P(n) be the proposition “all the integers n, n + 1, n + 2, . . . , 2n + 7”
are good. By the statement of the problem, we see that P(33) is true. But
(*) implies the truth of P(n + 1) whenever P(n) is true. The assertion is
thus proved by induction.
Problems
416 Problem Use Sophie Germain’s trick to show that

x4 + x2 + 1 = (x2 − x + 1)(x2 + x + 1). Use this to show that if n is a
positive integer then
n+1 n
22 + 22 + 1
has at least n different prime factors.
417 Problem Prove that n3 + (n + 1)3 + (n + 2)3 is divisible by 9.
418 Problem Let n ∈ N. Prove the inequality
1 1 1
+ + ··· + > 1.
n+1 n+2 3n + 1
419 Problem Prove that for all positive integers n and all real numbers x,
(4.2) | sin nx| ≤ n| sin x|

86 Chapter 4

s r
√
q
π
2+ 2+ 2 + ··· + 2 = 2 cos n+1
| {z } 2
n radical signs
for n ∈ N.
421 Problem Let a1 = 3, b1 = 4, and an = 3an−1 , bn = 4bn−1 when n > 1.

Prove that a1000 > b999 .
422 Problem Let n ∈ N, n > 1. Prove that

1 · 3 · 5 · · · (2n − 1) 1
<√ .
2 · 4 · 6 · · · (2n) 3n + 1
423 Problem Prove that for all natural number n > 1,
4n (2n)!
< .
n+1 (n!)2
1
424 Problem Let k be a positive integer Prove that if x + is an integer
x
1
then x + k is also an integer.
k
x
425 Problem Prove that for all natural numbers

1 1 1 1 1
2
+ 2 + 2 + ··· + 2 < 2 − .
1 2 3 n n
426 Problem Let n ≥ 2 be an integer. Prove that

f1 + f2 + · · · + fn = fn+2 − 1.
427 Problem Let n, m ≥ 0 be integers. Prove that
(4.3) fn+m = fn−1 fm + fn fm+1

Congruences 87
428 Problem This problems uses the argument of A. Cauchy’s to prove

the AM-GM Inequality. It consists in showing that AM-GM is true for all
powers of 2 and then deducing its truth for the numbers between two
consecutive powers of 2. Let a1 , a2 , . . . , al be non-negative real numbers.
Let P(l) be the assertion the AM-GM Inequality
a1 + a 2 + · · · + a l √
≥ l a 1 a2 · · · a l
l
holds for the l given numbers.
1. Prove that P(2) is true.
2. Prove that the truth of P(2k−1 ) implies that of P(2k ).
3. Let 2k−1 < n < 2k . By considering the 2k quantities

y1 + y 2 + · · · + y n
a1 = y1 , a2 = y2 , . . . , an = yn , an+1 = an+1 = · · · = a2k = ,
n
prove that P(n) is true.
4.6 Congruences
429 Definition The notation a ≡ b mod n is due to Gauß, and it means
that n|(a − b).
Thus if a ≡ b mod n then a and b leave the same remainder upon

division by n. For example, since 8 and 13 leave the same remainder
upon division by 5, we have 8 ≡ 13 mod 5. Also observe that 5|(8 − 13).
As a further example, observe that −8 ≡ −1 ≡ 6 ≡ 13 mod 7.
Consider all the integers and arrange them in five columns as follows.
... ... ... ... ...

−10 −9 −8 −7 −6
−5 −4 −3 −2 −1
0 1 2 3 4
5 6 7 8 9
... ... ... ... ...
88 Chapter 4
The arrangement above shows that any integer comes in one of 5

flavours: those leaving remainder 0 upon division by 5, those leaving
remainder 1 upon division by 5, etc..
Since n|(a − b) implies that ∃k ∈ Z such that nk = a − b, we deduce that
a ≡ b mod n if and only if there is an integer k such that a = b + nk.
The following theorem is quite useful.
430 Theorem Let n ≥ 2 be an integer. If x ≡ y mod n and u ≡ v mod n

then
ax + bu ≡ ay + bv mod n.
Proof As n|(x − y), n|(u − v) then there are integers s, t with

ns = x − y, nt = u − v. This implies that
a(x − y) + b(u − v) = n(as + bt),
which entails that,

n|(ax + bu − ay − bv).
This last assertion is equivalent to saying
ax + bu ≡ ay + bv mod n.
This finishes the proof. ❑
431 Corollary Let n ≥ 2 be an integer. If x ≡ y mod n and u ≡ v mod n

then
xu ≡ yv mod n.
Proof Let a = u, b = y in Theorem 430. ❑
432 Corollary Let n > 1 be an integer, x ≡ y mod n and j a positive

integer. Then xj ≡ yj mod n.
Proof Use repeteadly Corollary 431 with u = x, v = y. ❑

Congruences 89
433 Corollary Let n > 1 be an integer, x ≡ y mod n. If f is a polynomial

with integral coefficients then f(x) ≡ f(y) mod n.
434 Example Find the remainder when 61987 is divided by 37.
Solution: 62 ≡ −1 mod 37. Thus
61987 ≡ 6 · 61986 ≡ 6(62 )993 ≡ 6(−1)996 ≡ −6 ≡ 31 mod 37
and the remainder sought is 31.
435 Example Find the remainder when
12233 · 455679 + 876533
is divided by 4.
Solution: 12233 = 12200 + 32 + 1 ≡ 1 mod 4. Similarly,

455679 = 455600 + 76 + 3 ≡ 3, 87653 = 87600 + 52 + 1 ≡ 1 mod 4. Thus
12233 · 455679 + 876533 ≡ 1 · 3 + 13 ≡ 4 ≡ 0 mod 4.
This means that 12233 · 455679 + 876533 is divisible by 4.
436 Example Prove that 7 divides 32n+1 + 2n+2 for all natural numbers n.
32n+1 ≡ 3 · 9n ≡ 3 · 2n mod 7
and
2n+2 ≡ 4 · 2n mod 7
. Hence
32n+1 + 2n+2 ≡ 7 · 2n ≡ 0 mod 7,
437 Example Prove the following result of Euler: 641|(232 + 1).

90 Chapter 4
Solution: Observe that 641 = 27 · 5 + 1 = 24 + 54 . Hence 27 · 5 ≡ −1

mod 641 and 54 ≡ −24 mod 641. Now, 27 · 5 ≡ −1 mod 641 yields
54 · 228 = (5 · 27 )4 ≡ (−1)4 ≡ 1 mod 641.
This last congruence and
54 ≡ −24 mod 641
yield
−24 · 228 ≡ mod 641,
which means that 641|(232 + 1).
438 Example Prove that 7|(22225555 + 55552222 ).
Solution: 2222 ≡ 3 mod 7, 5555 ≡ 4 mod 7 and 35 ≡ 5 mod 7. Now
22225555 +55552222 ≡ 35555 +42222 ≡ (35 )1111 +(42 )1111 ≡ 51111 −51111 ≡ 0 mod 7.
439 Example Find the units digit of 77 .

7
7
Solution: We must find 77 mod 10. Now, 72 ≡ −1 mod 10, and so
73 ≡ 72 · 7 ≡ −7 ≡ 3 mod 10 and 74 ≡ (72 )2 ≡ 1 mod 10. Also, 72 ≡ 1
mod 4 and so 77 ≡ (72 )3 · 7 ≡ 3 mod 4, which means that there is an
integer t such that 77 = 3 + 4t. Upon assembling all this,
7
77 ≡ 74t+3 ≡ (74 )t · 73 ≡ 1t · 3 ≡ 3 mod 10.
Thus the last digit is 3.
440 Example Find infinitely many integers n such that 2n + 27 is divisible

by 7.
Solution: Observe that 21 ≡ 2, 22 ≡ 4, 23 ≡ 1, 24 ≡ 2, 25 ≡ 4, 26 ≡ 1 mod 7

and so 23k ≡ 1 mod 3 for all positive integers k. Hence
23k + 27 ≡ 1 + 27 ≡ 0 mod 7 for all positive integers k. This produces the
infinitely many values sought.
Congruences 91
441 Example Prove that 2k − 5, k = 0, 1, 2, . . . never leaves remainder 1

when divided by 7.
Solution: 21 ≡ 2, 22 ≡ 4, 23 ≡ 1 mod 7, and this cycle of three repeats.

Thus 2k − 5 can leave only remainders 3, 4, or 6 upon division by 7.
442 Example (A IME 1994) The increasing sequence
3, 15, 24, 48, . . . ,
consists of those positive multiples of 3 that are one less than a perfect
square. What is the remainder when the 1994-th term of the sequence is
divided by 1000?
Solution: We want 3|n2 − 1 = (n − 1)(n + 1). Since 3 is prime, this

requires n = 3k + 1 or n = 3k − 1, k = 1, 2, 3, . . .. The sequence
3k + 1, k = 1, 2, . . . produces the terms n2 − 1 = (3k + 1)2 − 1 which are
the terms at even places of the sequence of 3, 15, 24, 48, . . .. The
sequence 3k − 1, k = 1, 2, . . . produces the terms n2 − 1 = (3k − 1)2 − 1
which are the terms at odd places of the sequence 3, 15, 24, 48, . . .. We
must find the 997th term of the sequence 3k + 1, k = 1, 2, . . .. Finally, the
term sought is (3(997) + 1)2 − 1 ≡ (3(−3) + 1)2 − 1 ≡ 82 − 1 ≡ 63
mod 1000. The remainder sought is 63.
443 Problem Prove that 0, 1, 3, 4, 9, 10, and 12 are the only perfect squares
mod 13.
(Hint: It is enough to consider 02 , 12 , 22 , . . . , 122 . In fact, by observing that

r2 ≡ (13 − r)2 mod n, you only have to go half way.)
444 Problem Prove that there are no integers with x2 − 5y2 = 2.
(Hint: Find all the perfect squares mod 5.)
445 Problem Which digits must we substitute for a and b in 30a0b03 so

that the resulting integer be divisible by 13?
92 Chapter 4
446 Problem Find the number of all n, 1 ≤ n ≤ 25 such that

n2 + 15n + 122 is divisible by 6.
(Hint: n2 + 15n + 122 ≡ n2 + 3n + 2 = (n + 1)(n + 2) mod 6.)
447 Problem (A IME 1983) Let an = 6n + 8n . Determine the remainder

when a83 is divided by 49.
448 Problem (P OLISH M ATHEMATICAL O LYMPIAD ) What digits should be

put instead of x and y in 30x0y03 in order to give a number divisible by
13?
449 Problem Prove that if 9|(a3 + b3 + c3 ), then 3|abc, for integers a, b, c.
450 Problem Describe all integers n such that 10|n10 + 1.
451 Problem Find the last digit of 3100 .
452 Problem (A HSME 1992) What is the size of the largest subset S of
{1, 2, . . . , 50} such that no pair of distinct elements of S has a sum divisible
by 7?
453 Problem Prove that there are no integer solutions to the equation
x2 − 7y = 3.
454 Problem Prove that if 7|a2 + b2 then 7|a and 7|b.
455 Problem Prove that there are no integers with

800000007 = x2 + y2 + z2 .
456 Problem Prove that the sum of the decimal digits of a perfect square
cannot be equal to 1991.

n n
7|42 + 22 + 1
Congruences 93
458 Problem Find the last two digits of 3100 .
459 Problem (U SAMO 1986) What is the smallest integer n > 1, for which
the root-mean-square of the first n positive integers is an integer?
Note. The root mean square of n numbers a1 , a2 , . . . , an is defined to be

1/2
a21 + a22 + · · · + a2n

.
n
460 Problem If 62ab427 is a multiple of 99, find the digits a and b.
461 Problem Show that an integer is divisible by 2n , n = 1, 2, 3, . . . if the

number formed by its last n digits is divisible by 2n .
462 Problem Find the last digit of
2333333334 · 9987737 + 12 · 21327 + 12123 · 99987.
463 Problem (A IME 1994) The increasing sequence
3, 15, 24, 48, . . . ,
consists of all those multiples of 3 which are one less than a square. Find
the remainder when the 1994th term is divided by 1000.
Answer: 63
464 Problem (A IME 1983) Let an = 6n + 8n . Find the remainder when a83
is divided by 49.
465 Problem Show that if 9|(a3 + b3 + c3 ), then 3|abc, for the integers
a, b, c.
94 Chapter 4
4.7 Miscellaneous Problems with Integers

Recall that bxc is the unique integer satisfying
(4.4) x − 1 < bxc ≤ x
Thus bxc is x is an integer, or the integer just to the left of x if x is not an
integer. For example b3.9c = 1, b−3.1c = −4.
Let p be a prime and n a positive integer. In the product n! = 1 · 2 · 3 · · · n
the number of factors contributing a factor of of p is b np c the number of
factors contributing a factor of p2 is b pn2 c, etc.. This proves the following
theorem.
466 Theorem De Polignac-Legendre The highest power of a prime p

diving n! is given by
X∞
n
(4.5) b kc
k=1
p
467 Example How many zeroes are there at the end of

999! = 1 · 2 · 3 · 4 · · · 998 · 999?
Solution: The number of zeroes is determined by the highest power of 10

dividing 999!. As there are fewer multiples of 5 amongst {1, 2, . . . , 999} that
multiples of 2, the number of zeroes is the determined by the highest
power of 5 dividing 999!. But the highest power of 5 dividing 999! is given
by
999 999 999 999
b c + b 2 c + b 3 c + b 4 c = 199 + 39 + 7 + 1 = 246.
5 5 5 5
Therefore 999! ends in 246 zeroes.
468 Example Let m, n be non-negative integers. Prove that

(m + n)!
(4.6) is an integer.
m!n!
Solution: Let p be a prime and k a positive integer. By the De

Polignac-Legendre Theorem, it suffices to show that
m+n m n
b k
c ≥ b k c + b k c.
p p p
Miscellaneous Problems with Integers 95
This inequality in turn will follow from the inequality
(4.7) bαc + bβc ≤ bα + βc
which we will show valid for all real numbers α, β.

Adding the inequalities bαc ≤ α, bβc ≤ β, we obtain bαc + bβc ≤ α + β.
Since bαc + bβc is an integer less than or equal to α + β, it must be less
than or equal than the integral part of α + β, that is bαc + bβc ≤ bα + βc,
as we wanted to show.
Observe that (m + n)! = m!(m + 1)(m + 2) · · · (m + n). Thus cancelling a
factor of m!,
(m + n)! (m + 1)(m + 2) · · · (m + n)
=
m!n! n!
we see that the product of n consecutive positive integers is divisible by
n!. If all the integers are negative, we may factor out a (−1)n , or if they
include 0, their product is 0. This gives the following theorem.
469 Theorem The product of n consecutive integers is divisible by n!.
470 Example Prove that n5 − 5n3 + 4n is always divisible by 120 for all
integers n.
Solution: We have
n5 − 5n3 + 4n = n(n2 − 4)(n2 − 1) = (n − 2)(n − 1)(n)(n + 1)(n + 2),
the product of 5 consecutive integers and hence divisible by 5! = 120.
471 Example Let A be a positive integer and let A 0 be the resulting

integer after a specific permutation of the digits of A. Show that if
A + A 0 = 1010 then A s divisible by 10.
Solution: Clearly, A and A 0 must have 10 digits each. Put
A = a10 a9 a8 . . . a1
and
A 0 = b10 b9 b8 . . . b1 ,
96 Chapter 4
where ak , bk , k = 1, 2, . . . , 10 are the digits of A and A 0 respectively. As

A + A 0 = 10000000000, we must have
a1 + b1 = a2 + b2 = · · · = ai + bi = 0 and
ai+1 + bi+1 = 10, ai+2 + bi+2 = · · · = a10 + b10 = 9,
for some subindex i, 0 ≤ i ≤ 9. Notice that if i = 9 there are no sums

ai+2 + bi+2 , ai+3 + bi+3 , . . . and if i = 0 there are no sums
a1 + b 1 , . . . , a i + b i .
Adding,
a1 + b1 + a2 + b2 + · · · + ai + bi + ai+1 + bi+1 + · · · + a10 + b10 = 10 + 9(9 − i).
If i is even, 10 + 9(9 − i) is odd and if i is odd 10 + 9(9 − i) is even. As
a1 + a2 + · · · + a10 = b1 + b2 + · · · + b10 ,
we have
a1 +b1 +a2 +b2 +· · ·+ai +bi +ai+1 +bi+1 +· · ·+a10 +b10 = 2(a1 +a2 +· · ·+a10 ),
an even integer. We gather that i is odd, which entails that a1 = b1 = 0,

that is , A and A 0 are both divisible by 10.
472 Example (P UTNAM 1956) Prove that every positive integer has a
multiple whose decimal representation involves all 10 digits.
Solution: Let n be an arbitrary positive integer with k digits. Let

m = 1234567890 · 10k+1 . Then all of the n consecutive integers
m + 1, m + 2, . . . , m + n
begin with 1234567890 and one of them is divisible by n.
473 Example (P UTNAM 1966) Let 0 < a1 < a2 < . . . < amn+1 be mn + 1
integers. Prove that you can find either m + 1 of them no one of which
divides any other, or n + 1 of them, each dividing the following.
Solution: Let, for each 1 ≤ k ≤ mn + 1, nk denote the length of the

longest chain, starting with ak and each dividing the following one, that
can be selected from ak , ak+1 , . . . , amn+1 . If no nk is greater than n, then

the are at least m + 1 nk ’s that are the same. However, the integers ak
corresponding to these nk ’s cannot divide each other, because ak |al
implies that nk ≥ nl + 1.
474 Theorem If k|n then fk |fn .
Proof Letting s = kn, t = n in the identity fs+t = fs−1 ft + fs ft+1 we obtain

f(k+1)n = fkn+n = fn−1 fkn + fn fkn+1 .
It is clear that if fn |fkn then fn |f(k+1)n . Since fn |fn·1 , the assertion follows.
475 Example Prove that if p is an odd prime and if

a
= 1 + 1/2 + · · · + 1/(p − 1),
b
then p divides a.
Solution: Arrange the sum as

1 1 1 1 1
1+ + + + ··· + + .
p−1 2 p−2 (p − 1)/2 (p + 1)/2
After summing consecutive pairs, the numerator of the resulting fractions
is p. Each term in the denominator is < p. Since p is a prime, the p on
the numerator will not be thus cancelled out.
476 Example The sum of some positive integers is 1996. What is their
maximum product?
Solution: We are given some positive integers a1 , a2 , . . . , an with

a1 + a2 + · · · + an = 1996. To maximise a1 a2 · · · an , none of the ak ’s can
be 1. Let us show that to maximise this product, we make as many
possible ak = 3 and at most two aj = 2.
Suppose that aj > 4. Substituting aj by the two terms aj − 3 and 3 the
sum is not changed, but the product increases since aj < 3(aj − 3). Thus
the ak ’s must equal 2, 3 or 4. But 2 + 2 + 2 = 3 + 3 and 2 × 2 × 2 < 3 × 3,
thus if there are more than two 2’s we may substitute them by 3’s. As
1996 = 3(665) + 1 = 3(664) + 4, the maximum product sought is 3664 × 4.
98 Chapter 4
477 Example Find all the positive integers of the form

1
r+ ,
r
where r is a rational number.
Solution: We will show that the expression r + 1/r is a positive integer

only if r = 1, in which case r + 1/r = 2. Let
1
r+ = k,
r
k a positive integer. Then
√
k± k2 − 4
r= .
2
Since k is an integer, r will be an integer if and only k2 − 4 is a square of
the same parity as k. Now, if k ≥ 3,
(k − 1)2 < k2 − 4 < k2 ,
that is, k2 − 4 is strictly between

√ two consecutive squares and so it cannot
be itself a square. If k = 1, k2 − 4 is not a real number. If k = 2,
k2 − 4 = 0. Therefore, r + 1/r = 2, that is, r = 1. This finishes the proof.
478 Example For how many integers n in {1, 2, 3, . . . , 100} is the tens digit
of n2 odd?
Solution: In the subset {1, 2, . . . 10} there are only two values of n (4 and
6) for which the digits of the tens of n2 is odd. Now, the tens digit of
(n + 10)2 = n2 + 20n + 100 has the same parity as the tens digit of n2 .
Thus there are only 20 n for which the prescribed condition is verified.
Problems
479 Problem Find the sum
5 + 55 + 555 + · · · + 5| .{z
. . 5} .
n 5 0s
√
480 Problem Show that for all numbers a 6= 0, a 6= ±i 3 the following
formula of Reyley (1825) holds.
3 3 3
a6 + 45a5 − 81a2 + 27 −a2 + 30a2 − 9 −6a3 + 18a

a= + + .
6a(a2 + 3)2 6a(a2 + 3) (a2 + 3)2
If a is rational this shows that every rational number is expressable as the

sum of the cubes of three rational numbers.
481 Problem What is the largest power of 7 that divides 1000!?
482 Problem Demonstrate that for all integer values n,
n9 − 6n7 + 9n5 − 4n3
is divisible by 8640.
483 Problem Prove that if n > 4 is composite, then n divides (n − 1)!.

(Hint: Consider, separately, the cases when n is and is not a perfect
square.)
484 Problem Find all real numbers satisfying the equation
bx2 − x − 2c = bxc.
485 Problem Solve the equation

x x
b c=b c
1999 2000
486 Problem (P UTNAM 1948) Let n be a positive integer. Prove that

√ √ √
b n + n + 1c = b 4n + 2c
√ √ √ √
(Hint: Prove that 4n + 1 < n + n + 1 < 4n + 3. Argue that neither
4n + 2 nor 4n + 3 are perfect squares.)
487 Problem Prove that 6|n3 − n, for all integers n.

100 Chapter 4
488 Problem (P OLISH M ATHEMATICAL O LYMPIAD ) Prove that if n is an

even natural number, then the number 13n + 6 is divisible by 7.
489 Problem Find, with proof, the unique square which is the product of
four consecutive odd numbers.
490 Problem (P UTNAM 1989) How many primes amongst the positive
integers, written as usual in base-ten are such that their digits are
alternating 1’s and 0’s, beginning and ending in 1?
491 Problem Let a, b, c be the lengths of the sides of a triangle. Show that
3(ab + bc + ca) ≤ (a + b + c)2 ≤ 4(ab + bc + ca).
492 Problem Let k ≥ 2 be an integer. Show that if n is a positive integer,

then nk can be represented as the sum of n successive odd numbers.
493 Problem (I MO 1979) If a, b are natural numbers such that

a 1 1 1 1 1
= 1 − + − + ··· − + ,
b 2 3 4 1318 1319
prove that 1979|a.
494 Problem (P OLISH M ATHEMATICAL O LYMPIAD ) A triangular number is

one of the form 1 + 2 + . . . + n, n ∈ N. Prove that none of the digits
2, 4, 7, 9 can be the last digit of a triangular number.
495 Problem Demonstrate that there are infinitely many square triangular
numbers.
496 Problem (P UTNAM 1975) Supposing that an integer n is the sum of

two triangular numbers,
a2 + a b 2 + b
n= + ,
2 2
write 4n + 1 as the sum of two squares, 4n + 1 = x2 + y2 where x and y
are expressed in terms of a and b.
Conversely, show that if 4n + 1 = x2 + y2 , then n is the sum of two

triangular numbers.
497 Problem (P OLISH M ATHEMATICAL O LYMPIAD ) Prove that

amongst ten successive natural numbers, there are always at least one
and at most four numbers that are not divisible by any of the numbers
2, 3, 5, 7.
498 Problem Are there five consecutive positive integers such that the
sum of the first four, each raised to the fourth power, equals the fifth
raised to the fourth power?

(2m)!(3n)!
(m!)2 (n!)3
is always an integer.
500 Problem Prove that for n ∈ N, (n!)! is divisible by n!(n−1)!
501 Problem (O LIMP ÍADA MATEM ÁTICA ESPA ÑOLA , 1985)

If n is a positive integer, prove that (n + 1)(n + 2) · · · (2n) is divisible by 2n .
102 Chapter 4
Chapter 5
Sums, Products, and Recursions
5.1 Telescopic cancellation

We could sum the series
a1 + a 2 + a 3 + · · · + a n
if we were able to find {vk } satisfying ak = vk − vk−1 . For
a1 +a2 +a3 +· · ·+an = v1 −v0 +v2 −v1 +· · ·+vn−1 −vn−2 +vn −vn−1 = vn −v0 .
If such sequence vn exists, we say that a1 + a2 + · · · + an is a telescopic

series.

1 1 1 1
1+ · 1+ · 1+ ··· 1 + .
2 3 4 99
Solution: Adding each fraction:
3 4 5 100
· · ··· ,
2 3 4 99
which simplifies to 100/2 = 50.
103
104 Chapter 5
503 Example Find integers a, b so that

2 3 99
(2 + 1) · 22 + 1 · 22 + 1 · 22 + 1 · · · 22 + 1 = 2a + b.
Solution: Using the identity x2 − y2 = (x − y)(x + y) and letting P be the

sought product:
2 3 99
(2 − 1)P = (2 − 1) (2 + 1) · 22 + 1 · 22 + 1 · 22 + 1 · · · 22 + 1
2 3 99
22 − 1 · 22 + 1 · 22 + 1 · 22 + 1 · · · 22 + 1

=
2 2 3 99
2 2 2 2
= 2 − 1 · 2 + 1 · 2 + 1 ··· 2 + 1
3 3 4 99
= 22 − 1 · 22 + 1 · 22 + 1 · · · 22 + 1
.. ..
. .
299 299
= (2 − 1)(2 + 1)
100
= 22 − 1,
whence
100
P = 22 − 1.
504 Example Find the exact value of the product

π 2π 4π
P = cos · cos · cos .
7 7 7
Solution: Multiplying both sides by sin π7 and using sin 2x = 2 sin x cos x
we obtain
π π π 2π 4π
sin P = (sin cos ) · cos · cos
7 7 7 7 7
1 2π 2π 4π
= (sin cos ) · cos
2 7 7 7
1 4π 4π
= (sin cos )
4 7 7
1 8π
= sin .
8 7
As sin 7 = − sin 7 , we deduce that
π 8π
1
P=− .
8
Telescopic cancellation 105
505 Example Show that

1 3 5 9999 1
· · ··· < .
2 4 6 10000 100
Solution: Let
1 3 5 9999
A= · · ···
2 4 6 10000
and
2 4 6 10000
B= · · ··· .
3 5 7 10001
Clearly, x2 − 1 < x2 for all real numbers x. This implies that
x−1 x
<
x x+1
whenever these four quantities are positive. Hence
1/2 < 2/3

3/4 < 4/5
5/6 < 6/7
.. .. ..
. . .
9999/10000 < 10000/10001
As all the numbers involved are positive, we multiply both columns to

obtain
1 3 5 9999 2 4 6 10000
· · ··· < · · ··· ,
2 4 6 10000 3 5 7 10001
or A < B. This yields A2 = A · A < A · B. Now
1 2 3 4 5 6 7 9999 10000 1
A·B= · · · · · · ··· · = ,
2 3 4 5 6 7 8 10000 10001 10001
and consequently,
√ A2 < A · B = 1/10001. We deduce that
A < 1/ 10001 < 1/100.
For the next example we recall that n! (n factorial) means
n! = 1 · 2 · 3 · · · n.
For example, 1! = 1, 2! = 1 · 2 = 2, 3! = 1 · 2 · 3 = 6, 4! = 1 · 2 · 3 · 4 = 24.

Observe that (k + 1)! = (k + 1)k!. We make the convention 0! = 1.
106 Chapter 5
506 Example Sum

1 · 1! + 2 · 2! + 3 · 3! + · · · + 99 · 99!.
Solution: From (k + 1)! = (k + 1)k! = k · k! + k! we deduce

(k + 1)! − k! = k · k!. Thus
1 · 1! = 2! − 1!
2 · 2! = 3! − 2!
3 · 3! = 4! − 3!
.. .. ..
. . .
98 · 98 = 99! − 98!
99 · 99! = 100! − 99!
Adding both columns,
1 · 1! + 2 · 2! + 3 · 3! + · · · + 99 · 99! = 100! − 1! = 100! − 1.

Dn = 1 − 2 + 3 − 4 + · · · + (−1)n−1 n.

1 1 1 1
1 − 2 · 1 − 2 · 1 − 2 ··· 1 − 2 .
2 3 4 99
Answer: 2400.

1 1 1 1
log2 1 + + log2 1 + + log2 1 + + · · · + log2 1 + .
2 3 4 1023
Answer: 9.
510 Problem Prove that for all positive integers n, 22 + 1 divides

n
2n +1
22 − 2.
Arithmetic Sums 107
5.2 Arithmetic Sums

An arithmetic progression is one of the form
a, a + d, a + 2d, a + 3d, . . . , a + (n − 1)d, . . .
One important arithmetic sum is
n(n + 1)
1 + 2 + ··· + n = .
2
To obtain a closed form, we utilise Gauss’ trick:
If
An = 1 + 2 + 3 + · · · + n
then
An = n + (n − 1) + · · · + 1.
Adding these two quantities,
An = 1 + 2 + ··· + n
An = n + (n − 1) + · · · + 1
2An = (n + 1) + (n + 1) + · · · + (n + 1)
= n(n + 1),
n(n + 1)
since there are n summands. This gives An = .
2
We summarise this as
n(n + 1)
(5.1) 1 + 2 + ··· + n = .
2
For example,
100(101)
1 + 2 + 3 + · · · + 100 = = 5050.
2
Applying Gauss’s trick to the general arithmetic sum
(a) + (a + d) + (a + 2d) + · · · + (a + (n − 1)d)
we obtain
(5.2)
n(2a + (n − 1)d)
(a) + (a + d) + (a + 2d) + · · · + (a + (n − 1)d) =
2
108 Chapter 5
511 Example Find the sum of all the integers from 1 to 1000 inclusive,
which are not multiples of 3 or 5.
Solution: One computes the sum of all integers from 1 to 1000 and weeds
out the sum of the multiples of 3 and the sum of the multiples of 5, but
puts back the multiples of 15, which one has counted twice. The desired
sum is
(1 + 2 + 3 + · · · + 1000) − (3 + 6 + 9 + · · · + 999)
−(5 + 10 + 15 + · · · + 1000)
+(15 + 30 + 45 + · · · + 990)
= (1 + 2 + 3 + · · · + 1000) − 3(1 + 2 + 3 + · · · + 333)
−5(1 + 2 + 3 + · · · + 200)
+15(1 + 2 + 3 + · · · + 66)
= 500500 − 3 · 55611 − 5 · 20100 +
= 266332
512 Example Each element of the set {10, 11, 12, . . . , 19, 20} is multiplied
by each element of the set {21, 22, 23, . . . , 29, 30}. If all these products are
added, what is the resulting sum?
Solution: This is asking for the product

(10 + 11 + · · · + 20)(21 + 22 + · · · + 30) after all the terms are multiplied. But
(20 + 10)(11)
10 + 11 + · · · + 20 = = 165
2
and
(30 + 21)(10)
21 + 22 + · · · + 30 = = 255.
2
The required total is (165)(255) = 42075.
513 Example The sum of a certain number of consecutive positive

integers is 1000. Find these integers.
Solution: Let the the sum of integers be S = (l + 1) + (l + 2) + (l + n).

n(2l + n + 1)
Using Gauss’ trick we obtain S = . As S = 1000,
2
Arithmetic Sums 109
√ n(2l + n + 1). Now 2000 = n + 2ln + n > n , whence

2 2
2000 =
n ≤ b 2000c = 44. Moreover, n and 2l + n + 1 divisors of 2000 and are of
opposite parity. Since 2000 = 24 53 , the odd factors of 2000 are 1, 5, 25,
and 125. We then see that the problem has te following solutions:
n = 1, l = 999,
n = 5, l = 197,
n = 16, l = 54,
n = 25, l = 27.
514 Example Find the sum of all integers between 1 and 100 that leave
remainder 2 upon division by 6.
Solution: We want the sum of the integers of the form

6r + 2, r = 0, 1, . . . , 16. But this is
16
X 16
X 16
X 16(17)
(6r + 2) = 6 r+ 2=6 + 2(17) = 850.
r=0 r=0 r=0
2
515 Problem Show that
2 n2 (n2 + 1)
2
1 + 2 + 3 + · · · + (n − 1) + n = .
2
1 + 3 + 5 + · · · + 2n − 1 = n2 .
517 Problem (A HSME 1994) Sum the series
1 2
20 + 20 + 20 + · · · + 40.
5 5
Answer: 3030
110 Chapter 5

1 2 3 1995
+ + + ··· +
1996 1996 1996 1996
is an integer.
519 Problem (A HSME 1991) Let Tn = 1 + 2 + 3 + · · · + n and
T2 T3 T4 Tn
Pn = · · ··· .
T2 − 1 T3 − 1 T4 − 1 Tn − 1
Find P1991 .
Answer: 5973
1993
520 Problem Given that

1 1 1
, ,
a+b b+c c+a
are consecutive terms in an arithmetic progression, prove that
b2 , a2 , c2
are also consecutive terms in an arithmetic progression.
521 Problem Consider the following table:
1=1
2+3+4=1+8
5 + 6 + 7 + 8 + 9 = 8 + 27
10 + 11 + 12 + 13 + 14 + 15 + 16 = 27 + 64
Conjecture the law of formation and prove your answer.
522 Problem The odd natural numbers are arranged as follows:
(1)
Geometric Sums 111
(3, 5)
(7, 9, 11)
(13, 15, 17, 19)
(21, 23, 25, 27, 29)
...............................
Find the sum of the nth row.
523 Problem Sum
10002 − 9992 + 9982 − 9972 + · · · + 44 − 32 + 22 − 11 .
524 Problem The first term of an arithmetic progression is 14 and its 100th
term is −16. Find (i) its 30th term and (ii) the sum of all the terms from the
first to the 100th.
5.3 Geometric Sums

A geometric progression is one of the form
a, ar, ar2 , ar3 , . . . , arn−1 , . . . ,
525 Example Find the following geometric sum:
1 + 2 + 4 + · · · + 1024.
Solution: Let
S = 1 + 2 + 4 + · · · + 1024.
Then
2S = 2 + 4 + 8 + · · · + 1024 + 2048.
Hence
S = 2S−S = (2+4+8 · · ·+2048)−(1+2+4+· · ·+1024) = 2048−1 = 2047.

112 Chapter 5
526 Example Find the geometric sum

1 1 1 1
x= + 2 + 3 + · · · + 99 .
3 3 3 3
Solution: We have
1 1 1 1 1
x = 2 + 3 + · · · + 99 + 100 .
3 3 3 3 3
Then
2
3
x = x − 13 x
= ( 13 + 312 + 313 + · · · + 3199 )
−( 312 + 313 + · · · + 3199 + 1
3100
)
1
= 13 − 3100 .
From which we gather
1 1
x=
− .
2 2 · 399
The following example presents an arithmetic-geometric sum.
527 Example Sum
a = 1 + 2 · 4 + 3 · 42 + · · · + 10 · 49 .
Solution: We have
4a = 4 + 2 · 42 + 3 · 43 + · · · + 9 · 49 + 10 · 410 .
Now, 4a − a yields
3a = −1 − 4 − 42 − 43 − · · · − 49 + 10 · 410 .
Adding this last geometric series,

10 · 410 410 − 1
a= − .
3 9
528 Example Find the sum
Sn = 1 + 1/2 + 1/4 + · · · + 1/2n .
Interpret your result as n → ∞.

Geometric Sums 113
Solution: We have
1
Sn − Sn = (1+1/2+1/4+· · ·+1/2n )−(1/2+1/4+· · ·+1/2n +1/2n+1 ) = 1−1/2n .
2
Whence
Sn = 2 − 1/2n .
So as n varies, we have:
S1 = 2 − 1/20 = 1
S2 = 2 − 1/2 = 1.5
S3 = 2 − 1/22 = 1.875
S4 = 2 − 1/23 = 1.875
S5 = 2 − 1/24 = 1.9375
S6 = 2 − 1/25 = 1.96875
S10 = 2 − 1/29 = 1.998046875
Thus the farther we go in the series, the closer we get to 2.

Let us sum now the geometric series
S = a + ar + ar2 + · · · + arn−1 .
Plainly, if r = 1 then S = na, so we may assume that r 6= 1. We have
rS = ar + ar2 + · · · + arn .
Hence
S − rS = a + ar + ar2 + · · · + arn−1 − ar − ar2 − · · · − arn = a − arn .
From this we deduce that

a − arn
S= ,
1−r
that is,
a − arn
(5.3) a + ar + · · · + arn−1 =
1−r
If |r| < 1 then rn → 0 as n → ∞.
For |r| < 1, we obtain the sum of the infinite geometric series
a
(5.4) a + ar + ar2 + · · · =
1−r
114 Chapter 5
529 Example A fly starts at the origin and goes 1 unit up, 1/2 unit right,
1/4 unit down, 1/8 unit left, 1/16 unit up, etc., ad infinitum. In what
coordinates does it end up?
Solution: Its x coordinate is

1
1 1 1 2 2
− + − ··· = −1
= .
2 8 32 1− 4 5
Its y coordinate is
1 1 1 4
1− + − ··· = −1
= .
4 16 1− 4 5
Therefore, the fly ends up in ( 52 , 45 ).
530 Problem The 6th term of a geometric progression is 20 and the 10th
is 320. Find (i) its 15th term, (ii) the sum of its first 30 terms.
5.4 Fundamental Sums

In this section we compute several sums using telescoping cancellation.
We start with the sum of the first n positive integers, which we have
already computed using Gauss’ trick.

An = 1 + 2 + · · · + n.

k2 − (k − 1)2 = 2k − 1.
From this
12 − 0 2 = 2·1−1
22 − 1 2 = 2·2−1
32 − 2 2 = 2·3−1
.. .. ..
. . .
n2 − (n − 1)2 = 2 · n − 1
Fundamental Sums 115
n2 − 02 = 2(1 + 2 + 3 + · · · + n) − n.
Solving for the sum,
n(n + 1)
1 + 2 + 3 + · · · + n = ·n2 /2 + n/2 = .
2
12 + 2 2 + 3 2 + · · · + n 2 .
k3 − (k − 1)3 = 3k2 − 3k + 1.
Hence
13 − 0 3 = 3 · 12 − 3 · 1 + 1
23 − 1 3 = 3 · 22 − 3 · 2 + 1
33 − 2 3 = 3 · 32 − 3 · 3 + 1
.. .. ..
. . .
n3 − (n − 1)3 = 3 · n2 − 3 · n + 1
n3 − 03 = 3(12 + 22 + 32 + · · · + n2 ) − 3(1 + 2 + 3 + · · · + n) + n.
n(n+1)
From the preceding example 1 + 2 + 3 + · · · + n = ·n2 /2 + n/2 = 2
so
3
n3 − 03 = 3(12 + 22 + 32 + · · · + n2 ) − · n(n + 1) + n.
2
Solving for the sum,
n3 1 n
12 + 2 2 + 3 2 + · · · + n 2 = + · n(n + 1) − .
3 2 3
After simplifying we obtain
n(n + 1)(2n + 1)
(5.5) 12 + 2 2 + 3 2 + · · · + n 2 =
6
116 Chapter 5
533 Example Add the series
1 1 1 1
+ + + ··· + .
1·2 2·3 3·4 99 · 100

1 1 1
= − .
k(k + 1) k k+1
Thus
1
1·2
= 11 − 12
1
2·3
= 12 − 13
1
3·4
= 13 − 14
.. .. ..
. . .
1 1 1
99·100
= 99 − 100
1 1 1 1 1 99
+ + + ··· + =1− = .
1·2 2·3 3·4 99 · 100 100 100
534 Example Add
1 1 1 1
+ + + ··· + .
1 · 4 4 · 7 7 · 10 31 · 34

1 1 1 1 1
= · − · .
(3n + 1) · (3n + 4) 3 3n + 1 3 3n + 4
Thus
1
1·4
= 13 − 12 1
1 1 1
4·7
= 12 − 21
1 1 1
7·10
= 21 − 30
1 1 1
10·13
= 30 − 39
.. .. ..
. . .
1 1 1
34·37
= 102 − 111
Fundamental Sums 117
Summing both columns,
1 1 1 1 1 1 12
+ + + ··· + = − = .
1 · 4 4 · 7 7 · 10 31 · 34 3 111 37
535 Example Sum
1 1 1 1
+ + + ··· + .
1 · 4 · 7 4 · 7 · 10 7 · 10 · 13 25 · 28 · 31

1 1 1 1 1
= · − · .
(3n + 1) · (3n + 4) · (3n + 7) 6 (3n + 1)(3n + 4) 6 (3n + 4)(3n + 7)
Therefore
1 1 1
1·4·7
= 6·1·4 − 6·4·7
1 1 1
4·7·10
= 6·4·7 − 6·7·10
1 1 1
7·10·13
= 6·7·10 − 6·10·13
.. .. ..
. . .
1 1 1
25·28·31
= 6·25·28 − 6·28·31
Adding each column,
1 1 1 1 1 1 9
+ + +· · ·+ = − = .
1 · 4 · 7 4 · 7 · 10 7 · 10 · 13 25 · 28 · 31 6 · 1 · 4 6 · 28 · 31 217
1 · 2 + 2 · 3 + 3 · 4 + · · · + 99 · 100.

1 1
k(k + 1) = (k)(k + 1)(k + 2) − (k − 1)(k)(k + 1).
3 3
Therefore
118 Chapter 5
1·2 = 31 ·1·2·3− 1
3
·0·1·2
2·3 = 13 ·2·3·4− 1
3
·1·2·3
3·4 = 13 ·3·4·5− 1
3
·2·3·4
.. .. ..
. . .
99 · 100 = 13 · 99 · 100 · 101 − 1
3
· 98 · 99 · 100
Adding each column,
1 1
1 · 2 + 2 · 3 + 3 · 4 + · · · + 99 · 100 = · 99 · 100 · 101 − · 0 · 1 · 2 = 333300.
3 3

2
n(n + 1)
(5.6) 3 3 3
1 + 2 + 3 + ··· + n = 3
2
538 Problem Let a1 , a2 , . . . , an be arbitrary numbers. Show that
a1 + a2 (1 + a1 ) + a3 (1 + a1 )(1 + a2 ) + a4 (1 + a1 )(1 + a2 )(1 + a3 )

+ · · · + an−1 (1 + a1 )(1 + a2 )(1 + a3 ) · · · (1 + an−2 )
= (1 + a1 )(1 + a2 )(1 + a3 ) · · · (1 + an ) − 1.

csc 2 + csc 4 + csc 8 + · · · + csc 2n = cot 1 − cot 2n .
Hint: Show first that csc 2x = cot x − cot 2x.
540 Problem Let 0 < x < 1. Show that

∞
X n
x2 x
2 n+1 = .
n=1
1−x 1−x
Hint:
y 1 1
2
= − .
1−y 1 − y 1 − y2
First Order Recursions 119

π π π π π
tan 100 + 2 tan 99 + 22 tan 298 + · · · + 298 tan 2 = cot 100 .
2 2 2 2 2

n
X k 1 n2 + n
= · .
k=1
k4 + k 2 + 1 2 n2 + n + 1
543 Problem Evaluate

1/3
1 · 2 · 4 + 2 · 4 · 8 + 3 · 6 · 12 + · · ·
.
1 · 3 · 9 + 2 · 6 · 18 + 3 · 9 · 27 + · · ·

∞
X 1 π
arctan 2
= .
n=1
1+n+n 4
Hint: From
tan x − tan y
tan x − tan y =
1 + tan x tan y
deduce that
a−b
arctan a − arctan b = arctan
1 + ab
for suitable a and b.
545 Problem Prove the following result due to Gramm

∞
Y n3 − 1 2
= .
n=2
n3 +1 3
5.5 First Order Recursions

We have already seen the Fibonacci numbers, defined by the recursion
f0 = 0, f1 = 1 and
fn+1 = fn + fn−1 , n ≥ 1.
120 Chapter 5
The order of the recurrence is the difference between the highest and the
lowest subscripts. For example
un+2 − un+1 = 2
is of the first order, and
un+4 + 9u2n = n5
is of the fourth order.
A recurrence is linear if the subscripted letters appear only to the first
power. For example
un+2 − un+1 = 2
is a linear recurrence and
x2n + nxn−1 = 1 and xn + 2xn−1 = 3
are not linear recurrences.
A recursion is homogeneous if all its terms contain the subscripted
variable to the same power. Thus
xm+3 + 8xm+2 − 9xm = 0
is homogeneous. The equation
xm+3 + 8xm+2 − 9xm = m2 − 3
is not homogeneous.
A closed form of a recurrence is a formula that permits us to find the n-th
term of the recurrence without having to know a priori the terms
preceding it.
We outline a method for solving first order linear recurrence relations of
the form
xn = axn−1 + f(n), a 6= 1,
where f is a polynomial.
1. First solve the homogeneous recurrence xn = axn−1 by “raising the

subscripts” in the form xn = axn−1 . This we call the characteristic
equation. Cancelling this gives x = a. The solution to the
homogeneous equation xn = axn−1 will be of the form xn = Aan ,
where A is a constant to be determined.
2. Test a solution of the form xn = Aan + g(n), where g is a polynomial

of the same degree as f.
546 Example Let x0 = 7 and xn = 2xn−1 , n ≥ 1. Find a closed form for xn .
Solution: Raising subscripts we have the characteristic equation

xn = 2xn−1 . Cancelling, x = 2. Thus we try a solution of the form
xn = A2n , were A is a constant. But 7 = x0 = A20 and so A = 7. The
solution is thus xn = 7(2)n .
Aliter: We have
x0 = 7
x1 = 2x0
x2 = 2x1
x3 = 2x2
.. .. ..
. . .
xn = 2xn−1
Multiplying both columns,
x0 x1 · · · xn = 7 · 2n x0 x1 x2 · · · xn−1 .
Cancelling the common factors on both sides of the equality,
xn = 7 · 2 n .
547 Example Let x0 = 7 and xn = 2xn−1 + 1, n ≥ 1. Find a closed form for

xn .
Solution: By raising the subscripts in the homogeneous equation we

obtain xn = 2xn−1 or x = 2. A solution to the homogeneous equation will
be of the form xn = A(2)n . Now f(n) = 1 is a polynomial of degree 0 (a
constant) and so we test a particular constant solution C. The general
solution will have the form xn = A2n + B. Now, 7 = x0 = A20 + B = A + B.
Also, x1 = 2x0 + 7 = 15 and so 15 = x1 = 2A + B. Solving the
simultaneous equations
A + B = 7,
2A + B = 15,
we find A = 8, B = −1. So the solution is xn = 8(2n ) − 1 = 2n+3 − 1.
122 Chapter 5
Aliter: We have:
x0 = 7
x1 = 2x0 + 1
x2 = 2x1 + 1
x3 = 2x2 + 1
.. .. ..
. . .
xn−1 = 2xn−2 + 1
xn = 2xn−1 + 1
Multiply the kth row by 2n−k . We obtain
2 n x0 = 2n · 7
2n−1 x1 = 2n x0 + 2n−1
2n−2 x2 = 2n−1 x1 + 2n−2
2n−3 x3 = 2n−2 x2 + 2n−3
.. .. ..
. . .
22 xn−2 = 23 xn−3 + 22
2xn−1 = 22 xn−2 + 2
xn = 2xn−1 + 1
Adding both columns, cancelling, and adding the geometric sum,
xn = 7 · 2n + (1 + 2 + 22 + · · · + 2n−1 ) = 7 · 2n + 2n − 1 = 2n+3 − 1.
Aliter: Let un = xn + 1 = 2xn−1 + 2 = 2(xn−1 + 1) = 2un−1 . We solve the
recursion un = 2un−1 as we did on our first example:
un = 2n u0 = 2n (x0 + 1) = 2n · 8 = 2n+3 . Finally, xn = un − 1 = 2n+3 − 1.
548 Example Let x0 = 2, xn = 9xn−1 − 56n + 63. Find a closed form for
this recursion.

obtain the characteristic equation xn = 9xn−1 or x = 9. A solution to the
homogeneous equation will be of the form xn = A(9)n . Now
f(n) = −56n + 63 is a polynomial of degree 1 and so we test a particular
solution of the form Bn + C. The general solution will have the form
xn = A9n + Bn + C. Now
x0 = 2, x1 = 9(2) − 56 + 63 = 25, x2 = 9(25) − 56(2) + 63 = 176. We thus
solve the system
2 = A + C,
25 = 9A + B + C,
176 = 81A + 2B + C.
We find A = 2, B = 7, C = 0. The general solution is xn = 2(9n ) + 7n.
549 Example Let x0 = 1, xn = 3xn−1 − 2n2 + 6n − 3. Find a closed form for

this recursion.

obtain the characteristic equation xn = 3xn−1 or x = 9. A solution to the
homogeneous equation will be of the form xn = A(3)n . Now
f(n) = −2n2 + 6n − 3 is a polynomial of degree 2 and so we test a
particular solution of the form Bn2 + Cn + D. The general solution will
have the form xn = A3n + Bn2 + Cn + D. Now
x0 = 1, x1 = 3(1) − 2 + 6 − 3 = 4, x2 = 3(4) − 2(2)2 + 6(2) − 3 = 13, x3 =
3(13) − 2(3)2 + 6(3) − 3 = 36. We thus solve the system
1 = A + D,
4 = 3A + B + C + D,
13 = 9A + 4B + 2C + D,
36 = 27A + 9B + 3C + D.
We find A = B = 1, C = D = 0. The general solution is xn = 3n + n2 .
550 Example Find a closed form for xn = 2xn−1 + 3n−1 , x0 = 2.
Solution: We test a solution of the form xn = A2n + B3n . Then

x0 = 2, x1 = 2(2) + 30 = 5. We solve the system
2 = A + B,
7 = 2A + 3B.
We find A = 1, B = 1. The general solution is xn = 2n + 3n .
We now tackle the case when a = 1. In this case, we simply consider a
polynomial g of degree 1 higher than the degree of f.
551 Example Let x0 = 7 and xn = xn−1 + n, n ≥ 1. Find a closed formula

for xn .
124 Chapter 5

obtain the characteristic equation xn = xn−1 or x = 1. A solution to the
homogeneous equation will be of the form xn = A(1)n = A, a constant.
Now f(n) = n is a polynomial of degree 1 and so we test a particular
solution of the form Bn2 + Cn + D, one more degree than that of f. The
general solution will have the form xn = A + Bn2 + Cn + D. Since A and
D are constants, we may combine them to obtain xn = Bn2 + Cn + E.
Now, x0 = 7, x1 = 7 + 1 = 8, x2 = 8 + 2 = 10. So we solve the system
7 = E,
8 = B + C + E,
10 = 4B + 2C + E.
1 n2 n
We find B = C = , E = 7. The general solution is xn = + + 7.
2 2 2
Aliter: We have
x0 = 7
x1 = x0 + 1
x2 = x1 + 2
x3 = x2 + 3
.. .. ..
. . .
xn = xn−1 + n
x0 + x1 + x2 + · · · + xn = 7 + x0 + x2 + · · · + xn−1 + (1 + 2 + 3 + · · · + n).
n(n + 1)
Cancelling and using the fact that 1 + 2 + · · · + n = ,
2
n(n + 1)
xn = 7 + .
2
Some non-linear first order recursions maybe reduced to a linear first

order recursion by a suitable transformation.
552 Example A recursion satisfies u0 = 3, u2n+1 = un , n ≥ 1. Find a closed

form for this recursion.
Solution: Let vn = log un . Then

1/2
vn = log un = log un−1 = 21 log un−1 = vn−1 2
. As vn = vn−1 /2, we have
n
vn = v0 /2 , that is, log un = (log u0 )/2 . Therefore, un = 31/2 .
n n
xn−1 + 4
553 Problem Find a closed form for x0 = 3, xn = .
3
1
Answer: xn = + 2.
3n
554 Problem Find a closed form for x0 = 1, xn = 5xn−1 − 20n + 25.
Answer: xn = 5n + 5n.
555 Problem Find a closed form for x0 = 1, xn = xn−1 + 12n.
Answer: xn = 6n2 + 6n + 1.
556 Problem Find a closed form for xn = 2xn−1 + 9(5n−1 ), x0 = 5.
Answer: xn = 2n + 3(5n ).
557 Problem Find a closed form for
a0 = 5, aj+1 = a2j + 2aj , j ≥ 0.

j
Answer: aj+1 = 62 − 1.
558 Problem (A IME 1994) If n ≥ 1,
xn + xn−1 = n2 .
Given that x19 = 94, find the remainder when x94 is divided by 1000.
559 Problem Find a closed form for
x0 = −1; xn = xn−1 + n2 , n > 0.

126 Chapter 5
560 Problem If u0 = 1/3 and un+1 = 2u2n − 1, find a closed form for un .
Hint: Let un = cos vn .
561 Problem Let x1 = 1, xn+1 = x2n − xn + 1, n > 0. Show that

X∞
1
= 1.
n=1
xn
5.6 Second Order Recursions

All the recursions that we have so far examined are first order recursions,
that is, we find the next term of the sequence given the preceding one.
Let us now briefly examine how to solve some second order recursions.
We now outline a method for solving second order homogeneous linear
recurrence relations of the form
xn = axn−1 + bxn−2 .
1. Find the characteristic equation by “raising the subscripts” in the

form xn = axn−1 + bxn−2 . Cancelling this gives x2 − ax − b = 0. This
equation has two roots r1 and r2 .
2. If the roots are different, the solution will be of the form

xn = A(r1 )n + B(r2 )n , where A, B are constants.
3. If the roots are identical, the solution will be of the form

xn = A(r1 )n + Bn(r1 )n .
562 Example Let x0 = 1, x1 = −1, xn+2 + 5xn+1 + 6xn = 0.
Solution: The characteristic equation is x2 + 5x + 6 = (x + 3)(x + 2) = 0.

Thus we test a solution of the form xn = A(−2)n + B(−3)n . Since
1 = x0 = A + B, −1 = −2A − 3B, we quickly find A = 2, B = −1. Thus the
solution is xn = 2(−2)n − (−3)n .
563 Example Find a closed form for the Fibonacci recursion

f0 = 0, f1 = 1, fn = fn−1 + fn−2 .
Second Order Recursions 127
Solution: The characteristic equation is f2 − f − 1 =!0, whence a solution

√ !n √ n
1+ 5 1− 5
will have the form fn = A +B . The initial
2 2
conditions give
0 = A + B,
√ ! √ ! √ √
1+ 5 1− 5 1 5 5
1=A +B = (A + B) + (A − B) = (A − B)
2 2 2 2 2
1 1
This gives A = √ , B = − √ . We thus have the Cauchy-Binet Formula:
5 5
√ !n √ !n
1 1+ 5 1 1− 5
(5.7) fn = √ −√
5 2 5 2
564 Example Solve the recursion x0 = 1, x1 = 4, xn = 4xn−1 − 4xn−2 = 0.
Solution: The characteristic equation is x2 − 4x + 4 = (x − 2)2 = 0. There

is a multiple root and so we must test a solution of the form
xn = A2n + Bn2n . The initial conditions give
1 = A,
4 = 2A + 2B.
This solves to A = 1, B = 1. The solution is thus xn = 2n + n2n .
565 Problem Solve the recursion x0 = 0, x1 = 1, xn = 10xn−1 − 21xn−2 .
566 Problem Solve the recursion x0 = 0, x1 = 1, xn = 10xn−1 − 25xn−2 .
567 Problem Solve the recursion x0 = 0, x1 = 1, xn = 10xn−1 − 21xn−2 + n.
568 Problem Solve the recursion

x0 = 0, x1 = 1, xn = 10xn−1 − 21xn−2 + 2n .
128 Chapter 5
5.7 Applications of Recursions

569 Example Find the recurrence relation for the number of n digit binary
sequences with no pair of consecutive 1’s.
Solution: It is quite easy to see that a1 = 2, a2 = 3. To form an , n ≥ 3, we

condition on the last digit. If it is 0, the number of sequences sought is
an−1 . If it is 1, the penultimate digit must be 0, and the number of
sequences sought is an−2 . Thus
an = an−1 + an−2 , a1 = 2, a2 = 3.
570 Example Let there be drawn n ovals on the plane. If an oval

intersects each of the other ovals at exactly two points and no three ovals
intersect at the same point, find a recurrence relation for the number of
regions into which the plane is divided.
Solution: Let this number be an . Plainly a1 = 2. After the n − 1th stage,

the nth oval intersects the previous ovals at 2(n − 1) points, i.e. the nth
oval is divided into 2(n − 1) arcs. This adds 2(n − 1) regions to the an−1
previously existing. Thus
an = an−1 + 2(n − 1), a1 = 2.
571 Example Find a recurrence relation for the number of regions into
which the plane is divided by n straight lines if every pair of lines
intersect, but no three lines intersect.
Solution: Let an be this number. Clearly a1 = 2. The nth line is cut by he

previous n − 1 lines at n − 1 points, adding n new regions to the
previously existing an−1 . Hence
an = an−1 + n, a1 = 2.
Applications of Recursions 129
572 Example (Derangements) An absent-minded secretary is filling n

envelopes with n letters. Find a recursion for the number Dn of ways in
which she never stuffs the right letter into the right envelope.
Solution: Number the envelopes 1, 2, 3, · · · , n. We condition on the last

envelope. Two events might happen. Either n and r(1 ≤ r ≤ n − 1) trade
places or they do not.
In the first case, the two letters r and n are misplaced. Our task is just to
misplace the other n − 2 letters, (1, 2, · · · , r − 1, r + 1, · · · , n − 1) in the
slots (1, 2, · · · , r − 1, r + 1, · · · , n − 1). This can be done in Dn−2 ways.
Since r can be chosen in n − 1 ways, the first case can happen in
(n − 1)Dn−2 ways.
In the second case, let us say that letter r, (1 ≤ r ≤ n − 1) moves to the
n-th position but n moves not to the r-th position. Since r has been
misplaced, we can just ignore it. Since n is not going to the r-th position,
we may relabel n as r. We now have n − 1 numbers to misplace, and this
can be done in Dn−1 ways.
As r can be chosen in n − 1 ways, the total number of ways for the
second case is (n − 1)Dn−1 . Thus Dn = (n − 1)Dn−2 + (n − 1)Dn−1 .
573 Example There are two urns, one is full of water and the other is
empty. On the first stage, half of the contains of urn I is passed into urn II.
On the second stage 1/3 of the contains of urn II is passed into urn I. On
stage three, 1/4 of the contains of urn I is passed into urn II. On stage
four 1/5 of the contains of urn II is passed into urn I, and so on. What
fraction of water remains in urn I after the 1978th stage?
Solution: Let xn , yn , n = 0, 1, 2, . . . denote the fraction of water in urns I

and II respectively at stage n. Observe that xn + yn = 1 and that
130 Chapter 5
x0 = 1; y0 = 0
x1 = x0 − 21 x0 = 21 ; y1 = y1 + 21 x0 = 1
2
x2 = x1 + 31 y1 = 32 ; y2 = y1 − 31 y1 = 1
3
x3 = x2 − 41 x2 = 21 ; y1 = y1 + 41 x2 = 1
2
x4 = x3 + 51 y3 = 53 ; y1 = y1 − 51 y3 = 2
5
x5 = x4 − 61 x4 = 21 ; y1 = y1 + 61 x4 = 1
2
x6 = x5 + 71 y5 = 74 ; y1 = y1 − 71 y5 = 3
7
x7 = x6 − 81 x6 = 21 ; y1 = y1 + 81 x6 = 1
2
x8 = x7 + 91 y7 = 95 ; y1 = y1 − 91 y7 = 4
9
A pattern emerges (which may be proved by induction) that at each odd

stage n we have xn = yn = 21 and that at each even stage we have (if
k+1
n = 2k) x2k = 2k+1 k
, y2k = 2k+1 . Since 1978 ÷ 2 = 989 we have x1978 = 1979
990
.
574 Problem At the Golem Gambling Casino Research Institute an

experiment is performed by rolling a die until two odd numbers have
appeared (and then the experiment stops). The tireless researchers
wanted to find a recurrence relation for the number of ways to do this.
Help them!
Answer: a0 = 0, an = an−1 + (n − 1)3n .
575 Problem Mrs. Rosenberg has $8 000 000 in one of her five savings
accounts. In this one, she earns 15% interest per year. Find a recurrence
relation for the amount of money after n years.
Applications of Recursions 131
576 Problem Find a recurrence relation for the number of ternary n-digit
sequences with no consecutive 2’s.

Discretemaths Book

Uploaded by

Copyright:

Available Formats

Discretemaths Book

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Discretemaths Book

Uploaded by

Copyright:

Available Formats

c

Discrete Mathematics Notes

Philadelphia, PA May 29, 2002

1.7.2 Function Calls . . . . . . . . . . . . . . . . . . . . . 32

5 Sums, Products, and Recursions 103

5.5 First Order Recursions . . . . . . . . . . . . . . . . . . . . . 119

These notes started during the Spring of 2002

1.1 C++ Alphabet

2 Definition A token is a string of characters recognised as meaningful by

3 Definition White space is the name given to spaces (blanks), horizontal

4 Definition A comment is an explanatory note for the humans reading the

// This is a valid C++ comment.

Another way of writing comments, inherited from C, is by enclosing the

! Comments of the type / ∗ COMMENT ∗ / cannot be nested. The

5 Definition A punctuator of C++ is any of the following characters (or in

7 Example The following blocks are disjoint.

! Indentation, albeit ignored by the C++ compiler, is recommended when

A list of standard C++ keywords appears in table 1.1.

and and_eq asm auto bitand

Table 1.1: Standard C++ Keywords.

! All standard C++ keywords are in lowercase letters.

Some predefined types in C++ are:

• the type void. This type is effectively the empty set.

• the type wchar_t. This is the long character type.

! For the purposes of these notes we will restrict to numerical data of

1.2.1 Notation for Types

11 Example The following are decimal integers

The following are octal integers

0234 0101 The following are hexadecimal integers

12 Example The following are floating point numbers

To indicate the compiler that we are using a character type, we enclose

13 Example The following are character types

Some characters cannot be found on the keyboard or have predetermined

• ’\n’ denotes the newline character (to go to the beginning of the

• ’\t’ denotes a horizontal tab character,

• ’\v’ denotes a vertical tab character,

• ’\b’ denotes a backspace character,

• ’\a’ denotes the bell or audible alert character,

• ’\\ ’ denotes a backslash character,

• ’\’’ denotes the single quote character,

• ’\"’ denotes the double quote character,

• ’\?’ denotes the question mark character,

• ’\0’ denotes the null character.

! There is a distinction between ’A’ (a character type) and "A" (a string

15 Example To produce the output

1.3 Variables and Constants

• does not contain whitespace,

• does not form a keyword,

• is composed of letters, underscores, or digits only, and,

• whose first character is not a digit.

17 Example The following are valid C++ identifiers:

18 Example The following are not valid as C++ identifiers:

19 Definition A variable is an instance of a type. It is a memory location

20 Definition A variable declaration is a statement with syntax

! The declaration of the variable allocates space for it and a specific

is equivalent to the code

21 Example The following are examples of variable declarations.

22 Example The following are examples of variable declarations with

! A variable may not be declared multiple times in the same block.

1.3.2 Aggregate Types