Search for notes by fellow students, in your own course and all over the country.
Browse our notes for titles which look like what you need, you can preview any of the notes via a sample of the contents. After you're happy these are the notes you're after simply pop them into your shopping cart.
Title: Colllege Discrete Mathematics
Description: A lecture note by Hovart Gabor. It is gonna help you alot.
Description: A lecture note by Hovart Gabor. It is gonna help you alot.
Document Preview
Extracts from the notes are below, to see the PDF you'll receive please use the links above
Lecture Notes for College Discrete
Mathematics
Gábor Horváth and Szabolcs Tengely
2013
Contents
1 Introduction
4
1
...
5
1
...
11
1
...
15
1
...
2 Counting
25
2
...
2
...
3
Permutations
2
...
5
The number of ordered subsets of a given size
2
...
32
...
40
...
46
2
...
51
2
...
3 Proof techniques
66
3
...
66
3
...
75
3
...
78
3
...
86
3
...
90
4 Pascal's triangle
4
...
93
96
3
CONTENTS
4
...
100
5 Recurrence sequences
112
5
...
112
5
...
117
129
6
...
129
6
...
142
6
...
4
Pascal's triangle
...
5
Recurrence sequences
...
160
Chapter 1
Introduction
These lecture notes are based on the class material College Discrete Mathematics for students in the Foundation Semester year at University of Debrecen, Hungary
...
Discrete mathematics deals with the non-continuous mathematics
...
The course sets the basis for future mathematical classes,
and is essential to understand those later
...
In Chapter 2 we show dierent counting arguments
...
Then we consider the
number of ordered subsets, the number of subsets of a given size
...
In Chapter 3 we explain dierent basic mathematical proof methods, such
as mathematical induction and proof by contradiction
...
At the end of the chapter we use these proof techniques to bring the reader
behind the curtains of a mathematical card trick
...
1
5
Sets
nomial coe cients
...
In Chapter 5 recurrence sequences are
discussed
...
Finally, in Chapter 6 we give all solutions to the exercises occurring
in the lecture notes
...
1
Sets
In mathematics a set is a collection of objects that are called elements
...
If
a set and
of
A,
a
is an element of
then we write
a ∈ A
...
If
a
A
is
is not an element
Now we deal with the problem how to provide a
set
...
If we have a set containing certain
elements, then we enclose these elements in braces
...
A
This notation is
di cult to use if the given set has large amount of elements
...
As an example
B is a set containg the integers between 1 and 1000
...
, 1000 }
...
, 99 }
...
Dk
Dk = { 1, 3,
...
denotes the set containing the rst
k
positive odd inte-
6
INTRODUCTION
k
1
{ 1, 3 }
3
{ 1, 3, 5 }
4
Standard sets
...
These are the set of natural numbers, the set of
integers, the set of rational numbers, the set of real numbers and the
set of complex numbers
...
},
the set of natural numbers
...
, −2, −1, 0, 1, 2,
...
Q,
R,
the set of real numbers
...
the set of complex numbers
...
It is also possible to de ne sets using the
so-called set-builder notation
...
g
...
We can use semicolon instead of the vertical line, as well:
{ 1, 3, 5 } = { a : (a − 1)(a − 3)(a − 5) = 0 } ,
{ 1, 3, 5 } = { a : a = 2k − 1, k ∈ { 1, 2, 3 } } ,
{ 1, 3, 5 } = { a : 1 ≤ a ≤ 5,
and
a
Let us de ne the set of even natural numbers:
{ 2n | n ∈ N }
...
D3 =
1
...
To study some basic properties of sets we give some de nitions
...
De nition 1
...
A set is called nite if it has nite number of elements
...
Now we consider cardinality of nite sets
...
De nition 1
...
Let
dierent elements of
A be a nite set
...
Notation: |A|
...
De nition 1
...
Let
if every element of
B
A and B
be sets
...
B
is a subset of
Notation:
A if and only
B ⊆ A
...
As the name suggests it is the set which has no element, that is, its
cardinality is 0
...
4
...
B = ∅, B = A,
then
B
is a proper subset of
A
...
5
...
The two sets are equal if
A⊆B
and
B ⊆ A
...
De nition 1
...
set
{x | x ∈ A
A and B be sets
...
Notation: A ∩ B
...
intersection of
A
and
By shading the appropriate region we illustrate the
B
...
sets is the set A ∩ B = { 3, 4, 5 }
...
7
...
and
B
be sets
...
The corresponding Venn diagram is as follows
...
The union of these two sets
is the set A ∪ B = { 1, 2, 3, 4, 5, 6, 7 }
...
It is not true for the
Let
dierence of two sets
...
8
...
The
x ∈ B }
...
/
Let
The Venn diagram of
A\B :
A
B
dierence of
A
and
B
is the set
1
...
Now we have that
A \ B = { 1, 2 } ,
B \ A = { 6, 7 }
...
De nition 1
...
B
is the set
A and B be sets
...
Notation: A B
...
We
Let
The Venn diagram of the symmetric dierence of
A
We give an example using sets
A
dierence of
and
B:
B
obtain that
A B = { 1, 2, 6, 7 }
...
De nition 1
...
U be a set (called the universe) and A is a subset of
U
...
Notation: A
...
U
A
A
U = {1, 2, 3, 4, 5, 6}
{2, 4, 6}
...
The
Exercise 1
...
Let A = { 3, 4, 6, 7, 8 } , B = { 2, 4, 5, 6, 8 } and C = { 1, 2, 4, 5, 8 }
...
2
...
What are the elements of the set
Exercise 1
...
What are the
(A ∩ B) \ (C ∩ B)?
A = { 1, 3, 4, 6, 7 } , B = { 2, 4, 6, 8 }
elements of the set (A \ B) ∪ (C \ B)?
Exercise 1
...
Let
and
C = { 1, 3, 4, 8 }
...
Exercise 1
...
Describe the following sets using set-builder notation
...
, 21k ,
...
Exercise 1
...
Draw a Venn diagram for the following sets:
(a)
(A ∩ B) ∪ C ,
(b)
(A \ B) ∪ (A \ C),
1
...
(c)
Exercise 1
...
Provide three sets
A, B
C
and
which satisfy the following
cardinality conditions
|A ∩ B ∩ C| = 2,
|A ∩ B| = |A ∩ C| = |B ∩ C| = 2,
|A| = |B| = |C| = 4
...
8
...
2
|B| = 5,
|B ∩ C| = 3,
|C| = 6
...
The special symbol
is used to denote sums
...
k=1
In a more general form
n
k = m + (m + 1) +
...
k=m
Here
m
is the lower bound of summation and
n
is the upper bound of sum-
mation
...
g
...
, n }
...
That is, the values of the following summations are equal:
3
k 2 = 12 + 22 + 32 = 14
k=1
and
3
m2 = 12 + 22 + 32 = 14
...
1≤i,j≤2
Now we deal with products of mathematical expressions
...
Product notation is very similar to summation notation so
it is straightforward to learn to use
...
k=1
If we change the
symbol to
, then we obtain
5
k = 1 · 2 · 3 · 4 · 5
...
We
1
...
, n }
...
By de nition, in such situations the sum is always 0 and the product is
always 1, e
...
k = 0,
k∈∅
k = 1
...
k=
k∈S∪T
k∈T
k∈S
k,
or
T
is the empty set
...
)
There is a special notation for the product of positive integers up to
n,
that is, when we multiply the elements of
Sn = { k | k
is a positive integer, k
The product of the elements of
that is,
is called
n
factorial and denoted by
n
n! =
0!,
k = 1 · 2 · · · · · (n − 1) · n
...
, n }
...
k∈∅
S0 :
n!,
14
INTRODUCTION
Factorials are always computed before any other operation
...
Exercise 1
...
Expand the following sums
...
10
...
Write the following expressions in summation notation
...
Exercise 1
...
Expand the following products
...
12
...
Write the following expressions in product notation
...
3
Exercise 1
...
Compute the values of n! for every n ∈ { 0, 1, 2, 3, 4, 5, 6, 7, 8 }
...
3
15
The Euclidean algorithm
Exercise 1
...
Compute the values of
5 + 3!
(5 + 3)!
4 − 2 · 3!
(4 − 2) · 3!
4 − (2 · 3)!
3 · 2!
(3 · 2)!
4 · 3!
4! · 5
...
15
...
for n = 1, which is one of the reasons we de ne 0!
Prove that
Note, that it is even true
to be equal to 1
...
3
The Euclidean algorithm
In this section we introduce the so-called Division algorithm, we de ne the
greatest common divisor of given integers and we consider the Euclidean
algorithm, which is one of the oldest mathematical algorithms
...
exist unique integers
q
Given two integers
and
r
q
is called quotient and
r
0 ≤ r < b
...
There is a special case,
when the Division algorithm yields
some
There
for which
a = qb + r,
Here
a and b such that b > 0
...
In such a situation
a = qb
for
q
...
11
...
b | a
...
We start with q = 0 and r = a
...
How to nd an appropriate
q
Notation:
and
16
INTRODUCTION
a < b, then we are done, otherwise a − b ≥ 0
...
We check if a−b < b
...
We stop when we have a − kb < b
for some k
...
12
...
d divides a
Let
if
0 ≤ 6 < 7
...
gcd(a, b)
d
is called a common
b
...
Notation: gcd(a, b)
...
The method also provides so-
lution of the linear Diophantine equation
ax + by = gcd(a, b)
...
then
d
divides
r = a − qb
as well
...
The Euclidean algorithm works as follows
...
3
17
The Euclidean algorithm
r1
...
We continue, we divide r1 by r2 to
obtain q3 and r3
...
Since the procedure
a remainder
produces a decreasing sequence of non-negative integers so must eventually
terminate by descent
...
As an example we compute
gcd(553, 161)
...
gcd(553, 161) = 7
...
It follows that
x=7
Exercise 1
...
integers
x
and
y
and
y = −24
...
gcd(a, b)
and compute
18
INTRODUCTION
1
...
In everyday
life we use base 10
...
Let us consider counting
...
He was raised using the base 10 numbers, thus after
reaching 9 lines, he crosses them on the tenth day (thus marking them as
ten)
...
Then, when he reaches
ten of such groups, then he carves a big box around them
...
That is how
Then he circles around every ten boxes, indicating
thousands, etc
...
Assume Robinson had arrived at the island 1st May 1817, and was rescued
on 30th April 1850
...
33 · 365 = 12045 days, not counting leap
The leap years are 1820, 1824, 1828, 1832, 1836, 1840, 1844, 1848,
that is, he spent
12053 days altogether on the island
...
That is, he would have one rock completely full with ten circles, ten
boxes in each circle, and ten of the ten lines crossed in each box
...
Robinson is basically writing the numbers in base 10 by grouping every
ten together
...
When we think about the number 12053, we
automatically give the meaning to the positions with the appropriate powers
of 10:
12053 = 1 · 10 000 + 2 · 1 000 + 0 · 100 + 5 · 10 + 3 · 1 =
= 1 · 104 + 2 · 103 + 0 · 102 + 5 · 101 + 3 · 100
...
4
19
Numeral systems
positioning
...
That is, the value of the second
rightmost digit is
101 ,
the digit left from it is
102 ,
etc
...
All other numeral systems are based on the same idea
...
The values of the digits from
right to left will be the two powers in increasing order, that is, 1, 2, 4, 8,
16, 32, 64, etc
...
For example
1010112 = 1 · 25 + 0 · 24 + 1 · 23 + 0 · 22 + 1 · 21 + 1 · 20 = 32 + 8 + 2 + 1 = 4310
...
Another typical example from Computer Science could be the octal sys-
tem, i
...
base 8 (1 byte equals to 8 bits)
...
Similarly, in Computer Science, base 16 (hexadecimal number
system) is used
...
That is, we need separate digits
for the digits corresponding to 10, 11, 12, 13, 14 and 15
...
At rst, it might look strange to use digits for the number ten, eleven or
twelve
...
Counting months, or looking at the clock we use base 12
numeral system
...
Moreover, in the English language eleven
and twelve have dierent names, they are not generated as all the others
20
INTRODUCTION
between 10 and 20, indicating that they may have been distinguished as
extra digits
...
We
will write numbers in positional system, as above
...
That is, the rightmost digit
n0 = 1, the second rightmost digit has value n1 = n, the digit left
2
to it has value n , etc
...
a2 a1 a0 in base n (where
0 ≤ ak ≤ n − 1 for every 0 ≤ k ≤ t) represents the number
has value
t
ak ·nk = at ·nt +at−1 ·nt−1 +· · ·+a2 ·n2 +a1 ·n1 +a0 ·n0
...
a2 a1 a0 )n =
k=0
Now, the question is how to write numbers into dierent numeral systems
...
Another method is to repeatedly multiply by the base and add the next digit
...
The other direction is to nd a base
n representation of a decimal number
...
The rst is that we check
1
...
For example, write
25010
in base 8
...
Thus
250 = 3 · 64 + 58
...
we execute the division algorithm with 64:
Finally, 1 is the highest 8-power not greater than 2, and after the division
algorithm we obtain
2 = 2 · 1 + 0
...
Exercise 1
...
Write
2110
in base 2,
5010
in base 3,
281410
in base 16 using
the method explained above
...
For example, if we want to rewrite
281410
into base
16, then
2814 = 175 · 16 + 14,
175 = 10 · 16 + 15,
10 = 0 · 16 + 10
...
Exercise 1
...
Write
2110
in base 2,
5010
in base 3,
25010
in base 8 using
the division algorithm
...
For example, if we need to write
into base 3, we can do the following
...
3728
22
INTRODUCTION
Now, rewrite
25010
into base 3:
250 = 83 · 3 + 1,
83 = 27 · 3 + 2,
27 = 9 · 3 + 0,
9 = 3 · 3 + 0,
3 = 1 · 3 + 0,
1 = 0 · 3 + 1
...
Finally, we mention that some rewriting can be done much quicker if one
base is a full power of another
...
Going from right to left, every three base 2 digits can be easily rewritten into
base 8, as well
...
Similarly, as
16 = 24 ,
every base 16 digit can be rewritten easily to four
1
...
Going from right to left, every four base 2 digits can be easily rewritten into
base 16, as well
...
We have to stress, though, that this method only works if one base is a
full power of the other
...
Exercise 1
...
1110011012 ,
10101012 , 111112 , 101102 , 1010101012 , 100010002 , 10101112 , 1111012 ,
211023 , 12345 , 12347 , 12348 , 7778 , 3458 , 20128 , 45658 , 11238 , 6668 , 7418 ,
CAB16 , BEE16 , EEE16 , 4D416 , ABC16 , 9B516 , DDD16 , 3F 216
...
24
INTRODUCTION
(c) Rewrite the given numbers into the particular numeral system:
11213 =
...
7 ,
6548 =
...
7 ,
5438 =
...
3
...
(d) Write the following numbers into base 2 and base 16:
Chapter 2
Counting
In this Chapter we will consider counting problems
...
Let us warm up to this rst by solving some easy exercises
...
Five friends (Arnold, Bill,
Carl, David, Edmund) greet each other at this party by shaking hands
...
That is, there are
4 + 3 + 2 + 1 = 10
handshakes altogether
...
Say, there are 200 College freshmen greeting each other by shaking hands
...
Let us count the number of handshakes by ordering the people in
some way (say, by date of birth)
...
The oldest person shakes hand with 199 other people, this is 199 handshakes
...
That is, we count 198
26
COUNTING
more handshakes
...
That is, we count 197 more handshakes, etc
...
For the second youngest people we count only one new handshake: the handshake with
the youngest person
...
That is, the number of handshakes is
199 + 198 + 197 + · · · + 1
...
But
even without that knowledge, we can calculate this sum by observing that
the sum of the rst and last number is 200
...
We can continue this argument, and reach
99 + 101 = 200,
and the number 100 is left alone
...
This summation argument works in general, as well:
Proposition 2
...
For a positive integer
n
we have
1 + 2 + · · · + (n − 1) + n =
n · (n + 1)
...
1
...
1 by using the argument described above
...
Proof
...
Let
S
be the sum of the integers from 1 to
the same sum in reverse order below:
S = 1 + 2 + · · · + (n − 1) + n,
S = n + (n − 1) + · · · + 2 + 1
...
n,
and write
2
27
Counting
Adding the two equations together, we obtain
2S = (1 + n) + (2 + n − 1) + · · · + (n − 1 + 2) + (n + 1),
2S = (n + 1) + (n + 1) + · · · + (n + 1) + (n + 1),
2S = n · (n + 1),
S=
n · (n + 1)
...
Using the same line of thought, the rst person shakes hand with
(n − 1)
Now, we are able to tell the number of handshakes between
other people, the next one with
(n − 2) other people (we already counted the
handshake with the rst person), etc
...
1 (writing
2
(n − 1)
instead of
n)
...
2
...
2
Proof
...
The reason for this is that this proof method will
be useful later on
...
Altogether there
are n people, this would mean (n − 1) · n handshakes
...
Thus, in reality, (n − 1) · n is twice the number
Every person shakes hand with
of handshakes
...
2
...
2
Five friends meet at this party
...
Is it possible that everyone shook hands exactly three times? What is the
answer if a person can shake hands with another more than once? What are
the answers if seven people meet?
28
COUNTING
Four girls (Alice, Beth, Carrie, Diane) and four boys (Ed, Frank, George,
Hugo) meet at this party
...
Exercise 2
...
How many handshakes and kisses are there?
After greeting each other, they want to dance
...
First, let us count the number of ways they can form dancing couples (one
boy and one girl)
...
We can even list these 16 possibilities:
Alice Ed
Beth Ed
Carrie Ed
Diane Ed
Alice Frank
Beth Frank
Carrie Frank
Diane Frank
Alice George
Beth George
Carrie George
Diane George
Alice Hugo
Beth Hugo
Carrie Hugo
Diane Hugo
In one round four couples can dance
...
First Alice chooses a partner, then Beth, then Carrie, and
nally Diane dances with whoever is left
...
Beth will only have three choices, because Alice
will have already chosen someone
...
Finally, Diane has only
one choice
...
Now, in one round at most four couples can dance
...
But be
careful! We only proved that they need 4 rounds, we have not proved that
they can actually do it in 4 rounds
...
g
...
1
2
...
1: Four couples dancing in four rounds
1st round
2nd round
3rd round
4th round
Alice Ed
Beth Ed
Carrie Ed
Diane Ed
Beth Frank
Alice Frank
Diane Frank
Carrie Frank
Carrie George
Diane George
Alice George
Beth George
Diane Hugo
Carrie Hugo
Beth Hugo
Alice Hugo
Exercise 2
...
Is it possible
(a) to distribute 100 rabbits into ve packs such that each pack contains
an odd number of rabbits?
(b) that both the sum and the product of some integer numbers are 9?
(c) that both the sum and the product of 9 integer numbers are 9?
(d) that the sum of 9 integer numbers is 0 and the product of these numbers
is 9?
Exercise 2
...
(a) What is the sum of the rst 24 positive integers, i
...
1 + 2 + 3 + · · · + 23 + 24 =?
(b) Compute
2
...
1−2+3−4+···+23−24
Sequences
In Section 1
...
We are now interested in how many
certain numeral system
...
numbers exist in a
We know that there
are 9 one-digit positive integers: 1, 2, 3, 4, 5, 6, 7, 8, 9
...
We have
already counted that there are 9 one-digit positive integers
...
30
COUNTING
We could have calculated this dierently: there are 9 possibilities for a
rst digit of a two-digit number, and there are 10 possibilities (independently
from the rst digit) for the second digit
...
Now, what about three-digit positive integers? There are 999 `at most
three-digit numbers', and 99 are `at most two-digit numbers'
...
But we can obtain this result
by using the other idea, as well
...
Let us generalize this argument for
n-digit
positive integers
...
Altogether, the number of
n-digit
positive integers (in base 10) is
9 · 10 · · · · · 10 = 9 · 10n−1
...
6
...
Proposition 2
...
The number of
n-digit
base
k
positive integers is
(k − 1) · k n−1
...
, k − 1), and there are k possibilities for every other digit
...
There are
(k − 1) · k · · · · · k = (k − 1) · k n−1
...
Thus, there are
digit,
k
k
possibilities for the second digit, etc
...
1
31
Sequences
Proposition 2
...
base
k
The number of at most
n-digit
non-negative integers in
is
k · k · · · · · k = kn
...
(Here, we count the not necessarily meaningful words, as well
...
That is, the
number of 5 letter long words is
26 · 26 · 26 · 26 · 26 = 265
...
e
...
Indeed, we can formulate our main theorem
...
5
...
There are
k
k
k
n
k
letters
...
possibilities to choose the rst letter
...
Altogether there are
repetitions), thus the number of
n
n
letters to choose (with possible
letter long sequences is
k · k · · · · · k = kn
...
We already saw an example: for calculating the number of
n-
digit long base 10 numbers, the rst digit is an element of an alphabet of
size 9, and every other
(n − 1)
digit can be an element of size 10
...
Another possible example is the mobile phone number of a person
...
Thus altogether there are
3 · 107
possibilities for a mobile
phone number in Hungary
...
7
...
How many at most 3 digit palindrome numbers exist (in base 10)? Generalize
the result to
n-digit
Exercise 2
...
base
k
palindrome numbers
...
How many 5,
7, 10 letter long (not necessarily meaningful) words can be created using
Hungarian letters?
Exercise 2
...
In Hungary there is a game called TOTÓ, where one bets
on the outcome of certain football games
...
How many TOTÓ tickets should be
lled out to make sure that one of them will be correct for all
Exercise 2
...
13 + 1
games?
In a company the following system is used to record the
people working there: in the rst record the name of the person is written as
a 20 long string with possible spaces
...
Then follows the person's job title in a
10 letter long string, and nally comes the payment of the person as an at
most 8 digit non-negative integer in base 10
...
2
Number of subsets
In Section 1
...
Now,
we want to count these subsets
...
Exercise 2
...
List all subsets of { 1, 2, 3 }, { a, b, c }, { Alice, Beth, Carrie },
{ apple,
banana, cherry }
...
2
33
Number of subsets
After solving Exercise 2
...
This is true in general: for example if a set has three elements, then
we might as well name the elements
a, b
and
c,
and then its subsets will be
exactly the same as we determined in Exercise 2
...
Let us try to determine the number of subsets of a set with given car-
S be a set of cardinality 0, i
...
S = ∅
...
If S is a set of cardinality 1, e
...
S = { a }, then it has two subsets:
{ } = ∅, { a } = S
...
g
...
If S is a set of cardinality 3,
e
...
S = { a, b, c }, then it has eight subsets: { } = ∅, { a }, { b }, { c }, { a, b },
{ a, c }, { b, c }, { a, b, c } = S
...
1 shows all subsets of { a, b, c }
...
Let
this gure, two sets are connected if the lower one is a subset of the upper
one
...
2 summarizes our ndings on the number of subsets so far
...
1: Subsets of
Exercise 2
...
all subsets of
{ a, b, c }
...
2 and listing
{ a, b, c, d }
It seems that if
S
has
and
{ a, b, c, d, e },
if necessary
...
This is reinforced
by Figure 2
...
2: Number of subsets
Cardinality of
S
S
Number of subsets of
0
1
1
2
2
4
3
8
eight vertices of a cube
...
6
...
Then
-many subsets
...
Let us denote the elements of
S
by
a1 , a2 ,
...
, an }
...
of
S,
and we count the number of possibilities
First we decide whether or not
a1 ∈ T ,
that is,
a1 into T
...
Now, independent
of how we decided on a1 , we decide whether or not we want to put a2 into
T , that is, whether or not a2 ∈ T
...
Third
whether or not we put
(independently on how we decided on the earlier elements) we decide whether
or not we put
a3
into
T,
that is, whether or not
a3 ∈ T
...
This way we decide after each other for every element whether or not we
want to put the element into
T
...
For example, if for
ak
we decide dierently, then in one case
ak
will be an element of the subset,
in the other case it will not be an element
...
A
we decide to put the elements of
On the other hand, all subsets can be obtained this way: for a subset
This way,
T =A
A
into
T,
and not put other elements in
...
That is, by deciding for every element whether or not it should be in
T
we obtain all subsets exactly once
...
2
35
Number of subsets
either we put them into the subset or we do not put them into the subset
...
This is the same as the number of subsets of
set has
n
2
S
...
Exercise 2
...
For
S = { a, b, c } obtain all subsets using this decision algo-
rithm
...
Another argument
can be the following:
Second proof of Theorem 2
...
We give a draft of the proof, which can be
made precise after reading about mathematical induction
...
, an ,
Again, let us
that is,
S = { a1 , a2 ,
...
Here, every subset either contains
an
or does not contain
First, consider those subsets, which do not contain
an
...
, an−1 }
...
Moreover, every subset of S is a subset of S not containing an
...
Now, consider the subsets of S containing an
...
That is, it
is an added to a subset of S
...
That is, there is a one-to-one
correspondence between the subsets of S containing an and the subsets of S
...
Continuing this argument, we obtain that the number of subsets of S is 4
times the number of subsets of { a1 ,
...
That is, the number of
n
subsets of S is 2 times the number of subsets of { } = ∅
...
36
COUNTING
Note, that this argument would not have been necessary, as we have
already proved the statement of Theorem 2
...
Therefore this new proof
does not make the statement any more true (in any case, a mathematical
statement is either true or not true, there are no degrees to how true it is)
...
For example, this argument can be useful if we need certain types of subsets:
Exercise 2
...
S = { a, b, c, d } not containing d, and
subsets of { a, b, c }
...
It is an interesting coincidence that there are
set, and that exactly
2n -many
at most
n-digit
2n
subsets of an
n-element
binary numbers exist
...
Exercise 2
...
Encode all subsets of
S = { a, b, c, d }
in the following way:
T we assign an at most four digit binary number
...
Similarly, the second digit is 0 if c ∈ T ,
/
/
and 1 if c ∈ T
...
Finally,
/
the fourth digit is 0 if a ∈ T , and 1 if a ∈ T
...
The idea of Exercise 2
...
6
...
, an−1 ,
that is,
S = { a0 , a1 ,
...
n-digit binary number to every subset of S
...
Its last digit (corresponding to 2 ) is 0 if a0 ∈ T and 1 if
/
a0 ∈ T
...
2
37
Number of subsets
a1 ∈ T
...
Finally, the rst
/
n−1
digit (corresponding to 2
) is 0 if an−1 ∈ T and 1 if an−1 ∈ T
...
For dierent
and 1 if
subsets we assigned dierent binary numbers, and for every number we can
easily generate the subset corresponding to it (we just need to add those
elements into the subset where the digit is 1)
...
By Proposition 2
...
Thus,
S
has
2n -many
n
2
n-digit
-many at most
subsets, as well
...
Now,
we have enumerated all the subsets of
S,
and if we are interested in the
k th
subset, we can easily compute it
...
16
...
in the third proof of Theorem 2
...
the binary representation of
Exercise 2
...
Let
Let us encode the subsets of
S
as
Compute the subsets corresponding to
11, 7, 15
...
Let us encode the subsets of
S
as in the third proof of Theorem 2
...
Compute the subsets corresponding to
the binary representation of
11, 7, 15, 16, 31
...
16
...
18
...
Let us encode the subsets of
as in the third proof of Theorem 2
...
Compute the subset corresponding
to the binary representation of
49
...
19
...
of
S
Let us encode the subsets
as in the third proof of Theorem 2
...
Compute the subset corresponding
to the binary representation of
Exercise 2
...
subsets of
S
Let
101
...
as in the third proof of Theorem 2
...
corresponding to the binary representation of
199
...
3
Permutations
Three students are taking an oral exam in Mathematics
...
In how many dierent order can they do the exam?
Let the three students be Alice, Beth and Claire
...
For example, Alice can start the
exam, and then Beth follows and Claire nishes, or Claire follows and Beth
nishes
...
Finally, Claire may start, and Alice
continues and then Beth, or Beth continues and Alice nishes
...
3 lists
all six possibilities
...
3: The orders in which Alice, Beth and Claire can take the exam
rst
second
third
Alice
Beth
Claire
Alice
Claire
Beth
Beth
Alice
Claire
Beth
Claire
Alice
Claire
Alice
Beth
Claire
Beth
Alice
Looking at Table 2
...
There
are three ways to choose who the rst person will be (Alice, Beth or Carrie)
...
Then the person left will take the exam as the
third
...
At the next exam, there are four students: Ed, Frank, George, Hugo
...
In how many dierent orders can they do the exam?
2
...
21
...
Let us try to use our new argument
...
Then, no matter who starts, there
are three possibilities for choosing the second person (as the rst person has
already been chosen)
...
have
4 · 3 · 2 · 1 = 24
That is, altogether they
possibilities to choose the order to do the exam
...
In general, if there are
n
elements, then we call an ordering of
these elements a permutation
...
g
...
This is the number we denoted by
number of permutations of
the result would be
n!
in Section 1
...
Theorem 2
...
The number of permutations of
n
elements is
n!
...
We have n-many
rst element, then (n − 1)-many ways to choose the
cannot choose the rst anymore), then (n − 2)-many
Proof
...
Thus the number of dierent ways we
can put these
n
elements into an order is
n · (n − 1) · (n − 2) · · · · · 2 · 1 = n!
...
Recall that at the
beginning of Chapter 2, Alice, Beth, Claire, Diane, Ed, Frank, George and
Hugo wanted to form four dancing couples
...
That is, their choosing put an
order on the four boys, and therefore determined a permutation of them
...
And indeed, there are
form four dancing
and they can
40
COUNTING
Exercise 2
...
1, 2, 3, 4
How many four digit numbers exist, where all of the digits
appear exactly once?
Exercise 2
...
How many four letter long (not necessarily meaningful words)
can be built from the letters
Exercise 2
...
a, b, c, d, if all letters must be used exactly once?
Five boys and three girls buy cinema tickets
...
How many
dierent ways can they sit on the seats? How many dierent ways can they
sit on the seats if boys sit on seats from 1 to 5, and girls sit on seats from 6
to 8?
2
...
For
example an anagram of `retinas' can be `nastier', `retains', or `stainer'
...
One can even form
anagrams using multiple words, like `tin ears' or `in tears'
...
Of course,
the number of all meaningful anagrams would be very hard to nd, because
some expressions can be meaningful to some, and not to others
...
e
...
Nevertheless, there is
meaning given to all possible anagrams of `east' in Ross Eckler's Making the
Alphabet Dance
...
That is, altogether
there are
4 · 3 · 2 · 1 = 4! = 24-many
anagrams
...
2 Ross
Eckler,
Making the Alphabet Dance, St Martins Pr (July 1997)
2
...
It is possible that
by clever punctuations one can make more of these
...
)
To make matters simple, from now on we are only interested in the not
necessarily meaningful anagrams, without punctuations
...
Exercise 2
...
How many anagrams does `retinas' have?
Now, let us count the number of anagrams of `eye'
...
Unfortunately, exactly the same argument as
before does not work in this case
...
We could easily solve the
problem if the two e's would be dierent
...
Thus let us make them look
Let us colour one of the e's by blue, the other e by red, and
consider all coloured anagrams
...
Nevertheless, we
are interested in the number of anagrams, no matter their colour
...
2)
...
2: Coloured anagrams of `eye'
Now, we are interested in the number of groups
...
Take for example the group cor-
42
COUNTING
responding to the anagram `eye' (upper right part)
...
Similarly, every group contain exactly two coloured anagrams
...
Exercise 2
...
How many anagrams does the word `puppy' have? Try to
use the argument presented above
...
8
...
Let
n = n1 + n2 + · · · + nk be the number of letters altogether in this word
...
n1 ! · n2 ! · · · · · nk !
Proof
...
This is the number of permutations of
dierent letters, that is,
n!
n
by Theorem 2
...
Now, group together those anagrams which represent the same word,
and dier only in their colourings
...
To compute this number, we count the
number of coloured words in each group
...
The words listed in
this group dier only by the colourings
...
7
...
7, etc
...
7
...
Therefore the number of groups, and hence the number of (uncoloured)
times, and these letters have
anagrams is
n!
...
5
The number of ordered subsets of a given size
Exercise 2
...
43
How many anagrams does the following expressions have?
(a) `college',
(b) `discrete',
(c) `mathematics',
(d) `discrete mathematics',
(e) `college discrete mathematics'
...
28
...
For their birthdays,
they receive 12 bouquets of owers, all of them are from dierent owers
...
How many ways can
they distribute these 12 bouquets?
2
...
During Formula 1 racing some cars
obtain points (usually the cars nishing the race rst), and these points are
accumulated during the whole season
...
Between 1960 and 2002 only the rst six cars (out of 22) nishing the
race obtained points
...
Moreover, depending on their place they obtain dierent points
...
We are interested in how many possible outcomes exist for the Driver's
Championship
...
3, when we counted the number of permutations of
some elements
...
No matter which car
nishes the race rst, there will be 21 possible cars to nish the race second
...
Then,
there are 19 possibilities for the fourth place, 18 possibilities for the fth
place, and nally, there will remain 17 cars who can nish the race as sixth
...
Exercise 2
...
Which number is bigger?
22 · 21 · 20 · 19 · 18 · 17
22!
16!
or
Exercise 2
...
Altogether there are
22!
possible orders for the 22 cars (this is
the number of permutations of 22 cars)
...
In fact, those cases will be
considered the same where the rst six are the same (and in the same order)
...
4 for counting the anagrams, we can group together those permutations of the 22 cars, which are the same for the Driver's
Championship, that is, where the order of the rst six cars is the same
...
interested in the number of groups we have
...
cars
...
(22 − 6)!
16!
Let us try to generalize the result
...
We were interested in the rst six arriving
...
Thus, we may generalize our results in the following way
...
5
The number of ordered subsets of a given size
45
Theorem 2
...
Let S be a set of n elements, and let 0 ≤ k ≤ n be an integer
...
(n − k)!
n possibilities to choose from
...
Then, there will be (n − 2) possibilities to choose a third
element, etc
...
Thus the number
of the ordered k -element subsets is
Proof
...
(n − k)!
n · (n − 1) · · · · · (n − k + 1) =
Exercise 2
...
Prove Theorem 2
...
Exercise 2
...
(a) Between 2003 and 2009, the rst eight cars nishing
the race counts for the Driver's Championship
...
How many possibilities are there for the rst ten cars
(out of 22)?
Exercise 2
...
only the rst
k
There are
n
people at a running competition
...
How many possible lists
exist if
(a)
n = 10
and
k = 3,
(b)
n = 12
and
k = 3,
(c)
n = 10
and
k = 4,
46
COUNTING
(d)
n = 12
(e)
n=8
(f )
n = 10
2
...
Five numbers of them are chosen in an arbitrary way (usually a celebrity
blindly pulls out ve balls without putting them back)
...
People can guess in advance what the ve chosen numbers will be,
and they can win money depending on how many numbers they managed
to guess correctly
...
Let us imagine the situation that we want to win the jackpot
...
this problem in Theorem 2
...
5
...
Thus the number of possibilities to choose ve numbers such that
their order counts is
90 · 89 · 88 · 87 · 86 = 5 273 912 160
...
4 and 2
...
That is, let us
group together those chosen ve numbers, where the ve numbers are the
same, they only dier in the order they were chosen
...
Let us name these
For example, there will be a group
2
...
Similarly, there will be a group called `13, 42, 51, 66, 90'
containing all possible choosing of these ve numbers
...
Similarly, the numbers `51, 66, 90, 13, 42'
are put into the group `13, 42, 51, 66, 90', as well
...
To count the number of groups, we rst count the number
of ordered ve numbers in one group
...
This is the number of permutations of these
ve numbers
...
Similarly, there are
5! = 120-many orders in the group `13, 42,
5! = 120-many orders in every other group
...
5!
120
Exercise 2
...
Which number is bigger?
90 · 89 · 88 · 87 · 86
5!
90!
5! · 85!
or
The number occurring in Exercise 2
...
We denote it by
90
5
(read as `90 choose 5'), and it equals
90
5
=
90!
...
10
...
n
k
=
k ')
be
n!
...
Exercise 2
...
0, 1,
...
Calculate the numbers
n
k
for
n = 0, 1, 2, 3, 4, 5, 6
and
k=
48
COUNTING
Usually, it is easier to calculate
Proposition 2
...
For
n
k
n≥k≥1
=
n
k
as in the left hand side of Exercise 2
...
we have
n · (n − 1) · · · · · (n − k + 1)
...
The following calculation shows that the two sides are equal:
n
k
n!
n · (n − 1) · · · · · (n − k + 1) · (n − k)!
=
k! · (n − k)!
k! · (n − k)!
n · (n − 1) · · · · · (n − k + 1)
...
With that
argument we proved that the number of possibilities to choose 5 numbers
90
...
5
out of 90 is
Theorem 2
...
(2
...
k! · (n − k)!
k!
Proof
...
9
...
contains dierent orderings of the same
k
elements
...
Therefore the number of groups (and the number of k -element
subsets) is
n!
(n−k)!
k!
=
n!
=
k! · (n − k)!
n
...
11 this is the same number as
n · (n − 1) · · · · · (n − k + 1)
...
6
49
The number of subsets of a given size
In light of Theorem 2
...
Therefore, we spend some time to know them a little bit better
...
Exercise 2
...
What is
n
,
0
n
,
1
n
,
2
n
,
n−2
n
n−1
n
n
and
in general?
Moreover, it is pretty straightforward from formula (2
...
13
...
n−k
Proof
...
1), we give a combinatorial
argument
...
Naturally, if they
count the same thing, they must be equal
...
The right hand side counts the number of (n − k)-element subsets of an
n-element set
...
Let S be an n-element set, and let us map every
k -element subset into its complementer
...
Moreover, dierent k -element subsets are
mapped to dierent (n − k)-element subsets
...
Therefore this map is a one-to-one correspondence between
the
k -element
subsets and the
(n − k)-element
subsets
...
That is,
We can think about this proof in the following way
...
We can `not choose'
(n − k)
elements in
n
-many ways, which therefore must be the same as the number of choices
n−k
n
...
50
COUNTING
Exercise 2
...
n
k=0
for
Calculate the sum
n
k
=
n
n
n
n
n
+
+
+ ··· +
+
0
1
2
n−1
n
n = 0, 1, 2, 3, 4, 5, 6
...
36, one can conjecture on the general case:
Proposition 2
...
n
k=0
n
k
=
For every positive integer
n
we have
n
n
n
n
n
+
+
+ ··· +
+
0
1
2
n−1
n
= 2n
...
Again, we give a combinatorial argument
...
We prove that the left hand side
counts the same, only in a dierent manner
...
That is, a subset of an
n-element
set can have
0, 1, 2,
...
An n-element set has
0-element subsets,
n
n
1-element subsets, 2 -many 2-element subsets, etc
...
That is, the number of
n
subsets the n-element set has is
n
n
n
n
n
+
+
+ ··· +
+
...
hence it has
An
n-element
n-element
set can have
set has exactly
n
-many
k
k -element subsets
k -element subsets,
n
n
k=0 k -many subsets altogether
...
37
...
38
...
n
n
?
2
divide
n+1
2
+
n
2
for
n ≥ 2
...
7
51
Distributing money
2
...
They take all the treasure they can nd, which is seven gold pieces
altogether
...
They only have one rule: since everybody was useful during the raid,
everyone should receive at least 1 gold piece
...
It only matters how many gold pieces each pirate
gets
...
Let us list the possibilities by considering the amount of gold
pieces received by the highest rewarded pirate
...
In
fact, if somebody gets ve gold pieces, then the other two will have two
gold pieces to distribute, which they can only do by giving one gold piece
to each of them
...
If the pirate in the highest regard gets four gold pieces,
then the other two pirates will have three gold pieces to distribute
...
This altogether amounts to 6 possibilities:
3 possibilities on who gets four gold pieces, then in each case 2 possibilities
on who gets two gold pieces, that is,
3·2
possibilities
...
)
(Note that this is
Finally, if the highest
reward is three gold pieces, then the other two pirates can distribute the
remaining four gold pieces in two dierent ways:
either one of them gets
three gold pieces, and the other gets one, or both get two gold pieces
...
In the rst case there are 3
possibilities to choose who gets one gold piece (and the other two gets three
gold pieces each)
...
Table 2
...
52
COUNTING
Table 2
...
Anne Bonney
Black Bellamy
Calico Jack
5
1
1
1
5
1
1
1
5
4
2
1
4
1
2
2
4
1
1
4
2
2
1
4
1
2
4
3
3
1
3
1
3
1
3
3
3
2
2
2
3
2
2
2
3
This is all well and good, but if next time the pirates raid a much bigger
ship and nd a treasure chest full of gold on board, we will have a much
harder time counting the possibilities for them to distribute the gold
...
We give such a method in the following
...
The leftmost part will go to Anne Bonney, the middle
part is for Black Bellamy, and Calico Jack takes the rightmost part
...
7
53
Distributing money
example if Anne Bonney gets one gold piece, Black Bellamy gets two gold
pieces, and Calico Jack takes four, then they divide the seven gold pieces like
this:
That is, they use two sticks to divide the seven gold pieces into three parts
...
Where can they put the sticks? They can put the
sticks between gold pieces
...
Similarly,
they cannot put a stick after the last gold piece, because Calico Jack needs
to receive at least one gold piece
...
Thus, they need to put the two sticks somewhere in the
spaces between the gold pieces, but they cannot put the two sticks between
the same two gold pieces
...
There are 6 places between the seven gold pieces, and they need to
nd two, where they put the two sticks
...
This combinatorial argument works in general, when we need to
distribute
k
gold pieces among
n
pirates
...
Thus we obtain
Theorem 2
...
themselves (for some
n pirates want to distribute k gold pieces among
k ≥ n) such that everybody gets at least one gold piece
...
n−1
Exercise 2
...
Assume
Prove Theorem 2
...
After having found that they have 15 possible ways to distribute seven
gold pieces among themselves, the three pirates divide the gold pieces in
some way and continue sailing the oceans
...
All of them needed to do quite a bit of work for getting the treasure
chest (lot of sword- ghting for all three of them), therefore this time they
want to distribute the money so that everyone receives at least two gold
pieces
...
As before, let us list the possibilities by considering the
amount of gold pieces received by the highest rewarded pirate
...
In fact, if somebody gets six gold pieces, then the other two will
have four gold pieces to distribute, which they can only do by giving two gold
pieces to each of them
...
If the pirate in the highest regard gets ve gold pieces,
then the other two pirates will have ve gold pieces to distribute
...
This altogether amounts to 6 possibilities: 3
possibilities on who gets ve gold pieces, then in each case 2 possibilities on
who gets three gold pieces, that is,
3·2
possibilities
...
Both
distributions amounts to 3 possibilities altogether
...
In the second case there are 3 possibilities to choose
who gets four gold pieces (and the other two gets three gold pieces each)
...
5 summarizes the 15 possible distributions
...
5: Possibilities to distribute 10 gold pieces among three pirates so
that everyone gets at least two gold pieces
...
7
55
Distributing money
Here, we received exactly the same number of distributions as for the
earlier case, when the three pirates needed to distribute 7 gold pieces, and
everybody needed to get at least one
...
Somehow, we should be able to reduce the new problem to the earlier problem
...
This can be easily remedied: everyone takes one
gold piece at the very beginning
...
And this is now exactly the
same problem as before
...
This way, everyone needs
to get one more gold piece, and they will have
k − n gold pieces to distribute
further
...
15 we can prove
Proposition 2
...
n pirates
k ≥ 2n) such
Assume
themselves (for some
pieces
...
40
...
n−1
Prove Proposition 2
...
The three pirates continued to raid ships
...
They, again, want to distribute these gold pieces among themselves
...
It may be possible that somebody does not receive any gold pieces, even that somebody takes all the gold
...
There are three possibilities corresponding to the distribution
where one of them gets all four gold pieces (three possibilities depending
on who gets all the gold)
...
There are 6
such possibilities: 3 choices on who gets three gold pieces, and for each choice
there are 2 choices on who of the remaining two pirates gets 1 gold piece (and
the last pirate does not get any gold pieces)
...
In the rst case they
have 3 choices on who gets no gold pieces (and the other two pirates get two
gold pieces each), in the second case they have 3 choices on who gets two
gold pieces (and the other two pirates get one gold piece each)
...
6
summarizes all 15 possibilities for distributing four gold pieces among the
three pirates
...
6: Possibilities to distribute 4 gold pieces among three pirates
...
Let us try to reduce this problem to
the other one
...
Let us create a situation where this condition arises naturally!
For example, if every pirate puts one gold piece from their own pocket to the
treasure chest
...
This is exactly the same distribution
problem as the rst was, and thus they must have the same answer, as well
...
17
...
Proof
...
gold pieces to distribute among themselves,
but now each pirate would need to get at least one gold piece (because they
2
...
They
can distribute
n+k
gold pieces among themselves with that condition in
n+k−1
-many ways by Theorem 2
...
Finally, by the symmetric property of
n−1
n+k−1
the binomial coe cients (Proposition 2
...
n−1
k
Finally, our three pirates (Anne Bonney, Black Bellamy and Calico Jack)
raid yet another ship
...
But this time, they did not contribute to obtaining the chest
equally
...
How many ways can they distribute
the gold pieces with these conditions?
Once again, we could try to reduce this new problem to one which we
solved already
...
17 rather than
to Theorem 2
...
Just think about it: it makes more sense to the pirates
to just give rst the conditional money to the people that deserve it
...
Then they will have four gold pieces to distribute among
the three of them, which can be done in
4+3−1
3−1
=
6
2
= 15-many
ways by
Theorem 2
...
Exercise 2
...
Write all possibilities where the three pirates distribute seven
gold pieces such that Black Bellamy gets at least one gold piece and Calico
Jack gets at least two gold pieces
...
Theorem 2
...
Assume
n
pirates want to distribute
themselves such that the rst pirate gets at least
k1
k
gold pieces among
gold pieces, the second
k2 gold pieces, etc
...
The number of ways
kn
pirate gets at least
at least
gold
pieces (where
they can do this
58
COUNTING
is
k − k1 − k2 − · · · − kn + n − 1
...
First, the pirates pay o all the conditional amounts
...
, the
k th
k1 − k2 − · · · − kn
conditions
...
gold pieces left to distribute, on which they have no more
By Theorem 2
...
We make two remarks here
...
This is quite customary
in Mathematics, that when we have proved a hard result, we simply use it
for similar situations, rather than trying to gure out a similar proof for each
similar case
...
That would represent to a situation where the
ith
pirate
was so lazy, that he actually hindered the raid, and therefore he should pay
some amount into the loot they obtained
...
42
...
7
59
Distributing money
(i)
k = 15, n = 4,
and the rst pirate gets at least one gold piece, the
second pirate gets at least two gold pieces, the third pirate gets at least
three gold pieces, and the fourth pirate gets at least four gold pieces;
(j)
k = 15, n = 5,
and the rst and third pirates get at least one-one
gold piece, and the fourth and fth pirates get at least three-three gold
pieces?
In the last part of this section, we consider equations with integer solutions
...
(2
...
any problems
...
Thus z = 1 or z = 2
...
Now, if y ≥ 3, then x ≥ 3, and
7 = x + y + z ≥ 2y + z ≥ 2 · 3 + 2 = 8 is a contradiction
...
2)
...
If y = 3 then x = 3, if y = 2 then x = 4, and if y = 1 then
x = 5
...
2) are
the solutions
...
(5, 1, 1) depending on which variable equals
of type (4, 2, 1): three choices to determine
There are three solutions of type
to 5
...
There are three solutions of type
(3, 3, 1)
depending on
which variable equals to 1, and there are three solutions of type
depending on which variable equals to 3
...
2)
...
7 collects all 15 solutions
...
7: Positive integer solutions of
x + y + z = 7
...
7 look exactly the same as the distributions of 7 gold pieces among three pirates such that each of them gets at least
one gold piece (see Table 2
...
This is not a coincidence
...
Then altogether they take all 7 gold pieces, that is, x+y +z = 7
...
Thus the positive integer solutions of the equation x+y +z = 7
gets
x
gold pieces, Black Bellamy gets
y
gold pieces, and Calico Jack gets
correspond to the distributions of 7 gold pieces among three pirates such that
each of them gets at least one gold piece
...
Corollary 2
...
Consider the equation
x1 + x2 + · · · + xn = k
...
3)
The number of integer solutions of (2
...
,
is
k − k1 − k2 − · · · − kn + n − 1
...
The integer solutions of (2
...
Assume
n pirates distributing k gold pieces among themselves such that the
rst pirate gets at least k1 gold pieces, the second pirate gets at least k2 gold
pieces, etc
...
Then each distribution of the gold pieces corresponds
there are
to an integer solution of (2
...
3) corresponds
to a distribution
...
18 the number of distributions is
k − k1 − k2 − · · · − kn + n − 1
...
8
61
Balls from urns
and so is the number of integer solutions of (2
...
Exercise 2
...
How many integer solutions do the following equations have?
(a)
x + y + z = 9,
where
x ≥ 1, y ≥ 1, z ≥ 1;
(b)
x + y + z = 8,
where
x ≥ 0, y ≥ 0, z ≥ 0;
(c)
x + y + z = 7,
where
x ≥ 0, y ≥ 0, z ≥ 0;
(d)
x + y + z = 11,
(e)
w + x + y + z = 9,
where
w ≥ 1, x ≥ 1, y ≥ 1, z ≥ 1;
(f )
w + x + y + z = 7,
where
w ≥ 0, x ≥ 0, y ≥ 0, z ≥ 0;
(g)
w + x + y + z = 12,
where
w ≥ 2, x ≥ 2, y ≥ 2, z ≥ 2;
(h)
w + x + y + z = 10,
where
w ≥ 0, x ≥ 1, y ≥ 2, z ≥ 3;
(i)
w + x + y + z = 15,
where
w ≥ 1, x ≥ 2, y ≥ 3, z ≥ 4;
(j)
v + w + x + y + z = 15,
Exercise 2
...
where
x ≥ 2, y ≥ 2, z ≥ 2;
where
v ≥ 1, w ≥ 0, x ≥ 1, y ≥ 3, z ≥ 3
...
Their mother gives Rudolf money
and tells him to buy 10 pieces of Túró Rudi
...
How many ways can Rudolf buy 10 Túró Rudi desserts this way?
2
...
In the usual Hungarian lottery, 5 numbers are
chosen randomly from 90
...
This problem can have four
dierent versions, depending on whether or not the order of the chosen balls
counts, and whether or not we put back a ball into the urn after pulling it
out
...
repetition, then the answer is clearly
90 balls to choose from
...
1
...
5):
for rst choice we have 90 balls to choose from, for second choice we have
89 balls to choose from (because we cannot choose what we chose rst), for
third choice we have 88 balls to choose from (because we cannot choose what
we chose rst or second), for fourth choice we have 87 balls to choose from
(because we cannot choose what we chose rst, second or third), nally, for
fth choice we have 86 balls to choose from (because we cannot choose what
we chose before)
...
85!
(90 − 5)!
Now, consider the case where the order does not count and we do not allow
repetition
...
Five balls have
5!-many
orders, thus the number of choices for choosing 5 balls out of 90
without any repetition such that the order does not count is
90!
=
85! · 5!
90
...
6
...
We claim that this is the same problem as 90 pirates
distributing 5 gold pieces among themselves (Section 2
...
Indeed, for every
gold distribution we can consider to choose those balls which have the same
number as the pirates who received gold pieces, exactly as many times as the
number of gold pieces they received
...
8
63
Balls from urns
3 gold pieces and the tenth pirate received two, this corresponds to choosing
the numbers
1, 1, 1, 10, 10
...
Thus, by Theorem 2
...
5
Table 2
...
Table 2
...
Say, we have
in a urn, and we want to choose
k
90+5−1
5
n
numbered balls
out of them, and we are interested in
the number of possible ways to do this
...
Let us consider
the four problems one by one
...
1
...
5): for rst choice we
have
n balls to choose from, for second choice we have (n − 1) balls to choose
from (because we cannot choose what we chose rst), etc
...
g
...
That is, the number of
choices we have is
n·(n−1)·· · ··(n−k +1) =
n!
n · (n − 1) · · · · · (n − k + 1) · (n − k)!
=
...
that is,
Now, consider the case
where the order does not count and we do not allow repetition
...
number of choices for choosing
k
So
k
balls have
balls out of
n
k!-many
orders, thus the
without any repetition such
that the order does not count is
n!
=
(n − k)! · k!
Again, this answer is correct if
k ≤ n,
n
...
This is the
same problem we discussed in Section 2
...
choose
k
balls out of
n
Finally, consider the last case:
such that repetition is allowed, and the order does
not count
...
7)
...
Similarly, for every choice of balls we have a distribution: a
pirate gets as many gold pieces as the number of times its corresponding
ball has been chosen
...
18 the number of possibilities to
choose
k
numbers out of
n
if repetition is allowed and the order does not
count is
n+k−1
n−1
n+k−1
...
9 collects these results in a condensed form
...
9: Choosing
k
balls out of
n
order counts
no repetition (n
no repetition (n
order does not count
< k)
0
0
≥ k)
n!
(n−k)!
k
n
k
n+k−1
k
with repetition
n
2
...
45
...
How many ways can we
balls out of the urn if
(a)
n = 9, k = 3,
with repetition, the order does not count;
(b)
n = 3, k = 9,
with repetition, the order does not count;
(c)
n = 10, k = 5,
without repetition, the order counts;
(d)
n = 5, k = 10,
without repetition, the order counts;
(e)
n = 45, k = 6,
without repetition, the order does not count;
(f )
n = 6, k = 45,
without repetition, the order does not count;
(g)
n = 100, k = 10,
with repetition, the order counts;
(h)
n = 10, k = 100,
with repetition, the order counts
...
1
Proofs by induction
In mathematics one often uses induction to prove general statements
...
Suppose we have a statement
depends on
n
...
Then we show that if the statement is true for all
possible values less than n, then the statement is also true for n
...
There is a very similar
notion called recursion
...
smallest possible value
The basic idea is that we can compute e
...
98!,
...
100!
if we have computed
99!,
Induction works in the same way, if we can prove a statement for
certain smaller instances, then we can prove it for large values as well
...
Now we study induction in more detail
...
1 (Mathematical Induction I)
...
S(1)
Suppose that
is true,
Let
S(n)
be a statement depend-
3
...
n ∈ N
...
Denote by
m the smallest such value
...
Since m is as small as possible, S(k) is true for 1 ≤ k < m
...
From part (a) and (b)
one obtains that the statement is true for S(m − 1 + 1) = S(m)
...
Proof
...
divides
n
8 − 1
...
Hence part (a) of the theorem
is ful lled
...
It remains to be proved
k
that S(k + 1) is true
...
k
Hence there exists an integer A such that 8 − 1 = 7 · A
...
We try to express 8k+1 − 1
k
k
using 8 − 1
...
Now we add 7 to obtain the right form on the left-hand side:
8k+1 − 1 = 7 · A · 8 + 7 = 7(8A + 1)
...
Another area where induction can often be applied is proving mathematical identities
...
Let us compute the sum of the rst
2
n
n
integers for
positive integers is
n ∈ { 1, 2, 3, 4, 5 }
68
PROOF TECHNIQUES
n
1
2
3
4
1
5
n
i=1 i
1 = 1·2
2
1 + 2 = 2·3
2
1 + 2 + 3 = 3·4
2
1 + 2 + 3 + 4 = 4·5
2
+ 2 + 3 + 4 + 5 = 5·6
2
So it seems that the formula is correct
...
We have that
2
S(1)
is true
...
positive integers is
is true for some
k ≥ 1,
that is,
k
i=
i=1
We have to prove that
of the rst
k+1
k(k + 1)
...
That is, we have to consider the sum
integers, which is
k+1
i = 1 + 2 +
...
+ k) + (k + 1)
...
+ k =
k(k + 1)
...
2
2
2
S(k + 1)
is true and we proved that the sum of the rst
n
integers is
n(n + 1)
2
for all
n ∈ N
...
1
...
You can nd such problems in the following section related
3
...
So it is useful to state the above theorem
in a dierent form as well
...
Theorem 3
...
Let S(n) be a statement depending on
(a)
S(n0 )
(b) if
Then
n ∈ N
...
n0 ≤ n ∈ N
...
It is easy to
1
3
see that the statement is false for n = 1
...
In this problem n0 = 4, so the rst step is to
As an application we prove that
prove that
34 > 43 + 3
...
Assume that
S(k)
is true for some
4 ≤ k ∈ N
...
We need to show that
S(k + 1)
is true, that is,
3k+1 > (k + 1)3 + 3
...
3k 3 + 9 > (k + 1)3 + 3 for k ≥ 4, then S(k + 1)
3
3
inequality 3k + 9 > (k + 1) + 3 as follows:
If we can prove that
We rewrite the
follows
...
k(2k 2 − 3k − 3) ≥ 0 for k ≥ 4
...
We have that k ≥ 4 so 2k − 3 ≥ 5, hence
It is su cient to show that
70
PROOF TECHNIQUES
k(2k − 3) is at least 20
...
the product
so we
We provide a third version of the original theorem about induction
...
3
pending on
(a)
(Mathematical Induction III)
n ∈ N
...
S(k − n0 + 1),
...
Then
S(n)
is true for all
S(n)
Let
be a statement de-
Suppose that
S(m0 ), S(m0 + 1)
...
are true,
are true for some
m0 + n0 − 1 ≤ k ∈ N,
then
m0 ≤ n ∈ N
...
We prove by induction that for all positive integer n
Now we apply induction to prove certain inequalities
...
S(n) be the statement that Tn < 2n
...
Assume that for some 3 ≤ k ∈ N the statements S(k − 2), S(k − 1)
and S(k) are true, that is,
Let
Tk−2 < 2k−2 ,
Tk−1 < 2k−1 ,
Tk < 2k
...
We should prove the inequality
Tk+1 < 2k+1
...
Thus
S(k + 1)
is true and we proved that
Tn < 2n
for all positive integers
n
...
1
71
Proofs by induction
To further demonstrate how to apply the latter version of induction we
consider a problem about an integer sequence
...
an = 3n − 2n for all n ≥ 1
...
with n0 = 2
...
We have that a1 = 1 by de nition and the formula yields 3 − 2 = 1,
so S(1) is true
...
Hence we can go further and consider part (b)
...
That is,
Prove that
ak−1 = 3k−1 − 2k−1 ,
ak = 3k − 2k
...
Since
k + 1 ≥ 3, by de nition ak+1 = 5ak − 6ak−1
...
Thus
S(k + 1)
is true and we have that
an = 3n − 2n
for all
n ≥ 1
...
It is not always the case as the
following problems show
...
It is not obvious that one can apply
induction here
...
One considers an
m
to solve the problem for small values
n = m2 ,
then a solution is not
m grid
...
g
...
A solution is given by
by
72
PROOF TECHNIQUES
Having a solution for
n=6
one can provide solutions for
n=6
n=9
n = 9, 12,
...
We have
an argument for part (b) in Mathematical Induction III
...
If S(k − 2), S(k − 1), S(k) is true, then S(k + 1) is true (since it follows from
S(k − 2) in this case)
...
We have considered the case n = 6
...
We note that the case n = 4 is easy since
This process works in general, if we have a solution for some
4 is a square
...
n=4
n=7
Finally we handle the remaining case, that is,
solution:
n = 8
...
1
73
Proofs by induction
Exercise 3
...
Prove that
9n − 1
Exercise 3
...
Prove that
52n−1 + 1
Exercise 3
...
Prove the following identity by induction
is divisible by 8 for all
is divisible by 6 for all
n
(2i − 1) = n2
...
4
...
5
...
6
Prove the following identity by induction
n
i3 =
i=1
Exercise 3
...
i(i + 1) =
i=1
Exercise 3
...
2
...
3
Prove the following identity by induction
n
i=1
Exercise 3
...
n(n + 1)
2
Prove the following identity by induction
n−1
Let
{ an }
n ∈ N
...
i(i + 1)
n+1
be a sequence de ned by
a1 = 1,
a2 = 8,
an = an−1 + 2an−2 ,
n ≥ 3
...
74
PROOF TECHNIQUES
Prove that
an =
Exercise 3
...
3 n
· 2 + 2 · (−1)n
...
11
...
be a sequence de ned by
a1 =
Prove by induction that
33
2
is an integer which is divisible by 3 for all
Exercise 3
...
√
3+
an ≤ 2
2,
2 + an−1
for all
Prove that for all
n ≥ 2
...
n∈N
there exists an
n-digit
integer
a1 a2
...
Exercise 3
...
F1 = F2 = 1
and
Fn =
Fn−1 + Fn−2 , n ≥ 3 (this sequence is the so-called Fibonacci sequence)
...
(a)
F1 + F2 +
...
+ Fn = Fn Fn+1 ,
(c)
F1 + F3 +
...
+ F2n = F2n+1 − 1
...
13
...
n ∈ N
...
3
...
2
Proofs by contradiction
In this section we study an important tool to prove mathematical theorems
...
There is a simple
logic behind, instead of proving that something must be true, we prove it
indirectly by showing that it cannot be false
...
From this assumption we try to obtain such a conclusion
which is known to be false
...
Let us consider a basic example
...
We provide an indirect proof
...
Rational numbers can be written as a for some a ∈ Z
b
and b ∈ N such that the greatest common divisor of a and b is 1
...
a
2=
...
2
2
2
2
We substitute this into the equation a = 2b and we get 4a1 = 2b
...
So we have that 2 divides b
...
Hence 2 divides the greatest
Hence
It follows that 2 divides
common divisor
...
In Section 1
...
are unique
...
Assume that there exist integers
q, q
a = qb + r,
a=qb+r,
and
r, r
such that
0 ≤ r < b,
0 ≤ r < b
...
It follows that
b
divides
r − r
...
So we have that
−b < r − r < b
...
We obtained that r − r = 0, that is, r = r
...
Since b > 0, it is clear that q − q = 0 must hold, hence q = q
...
There is only one integer in this interval which is a multiple of
Let us consider a proposition about prime numbers (a positive integer is
prime if it is greater than 1 and has no positive divisors other than 1 and the
number itself
...
Assume the opposite, that is, there exist prime numbers
p2 + q 2 = r 2
...
and
q
are odd primes, hence
p2 + q 2 = r 2
is even
...
The only even prime number is 2, so we have
r = 2
...
Since p and q are odd primes we have p, q ≥ 3
...
We proved that if p and q are odd
If
primes, then the statement must be true
...
p
It implies
q are even primes, that is, p = q = 2
...
A contradiction since r = 4
and
3
...
In this case our statement turns out
to be true
...
p
is even and
It is clear that
r
q
is odd
...
Our equation
which can be written as
2
2
4 + 4q1 + 4q1 + 1 = 4r1 + 4r1 + 1
...
q1 (q1 + 1) and r1 (r1 + 1)
r1 (r1 + 1) − q1 (q1 + 1) is an even integer, but
The product of two consecutive integers is even, so
are even
...
Now we prove a result related to prime numbers
...
Proposition 3
...
There are in nitely many prime numbers
...
Suppose that there are only nitely many primes, let say
p3 <
...
p1 < p2 <
Let us consider the integer
N = p1 p2 · · · pn + 1
...
It means that for some
1 ≤ i ≤ n
the prime
pi
divides
N
...
Thus
N
is not divisible by
pi ,
a contra-
diction
...
78
PROOF TECHNIQUES
Exercise 3
...
x + y > 10
Prove that if
for some
x, y ∈ Z,
then
x>5
or
y > 5
...
15
...
Exercise 3
...
Prove that
√
2+
√
3
Exercise 3
...
Prove that if
a, b
and
is irrational
...
18
...
Given
n
integers
such that
ai ≥
Exercise 3
...
Let
Fn
a1 , a2 ,
...
+ an
...
1 for all positive integer n
...
3
1≤
F1 = F2 = 1 and Fn =
Prove that gcd(Fn , Fn+1 ) =
Constructive proofs
In this section we deal with several problems for which a method can be
provided to create a solution
...
Let us be given a currency system with
distinct integer denominations
a1 < a 2 <
...
k ≥2
Which amounts can be
changed? This question yields the following linear Diophantine equation
a1 x1 + a2 x2 +
...
, x k
are non-negative integers
...
There are some natural questions to pose:
k = 2,
3
...
We will use these results to
answer the original question
...
Since
d
divides
d divides n, if there is a solution in integers
...
Therefore there is no
solution in integers
...
dierent solution, say (v1 , v2 )
...
It implies that
a1 (u1 − v1 ) = a2 (v2 − u2 )
...
Since d is the largest common divisor of a1 and
we obtain that gcd(b1 , b2 ) = 1
...
It is clear that b1 divides
for some
t ∈ Z
...
So we have
v2 −u2 = b1 t
Thus
v2 = u2 + b1 t,
and
v1 = u1 − b2 t
...
We have proved
that there is no solution if
gcd(a1 , a2 )
does not divide
n,
and if there is a
80
PROOF TECHNIQUES
solution, then there are in nitely many integer solutions
...
3 we
showed that one can use the Euclidean algorithm to determine integers
a1 x + a2 y = gcd(a1 , a2 ) = d
...
We obtain the following equation
x, y
n,
that is,
a1 x 1 + a2 x 2 = n
...
Therefore
(xn1 , yn1 )
is a solution of the equation
summarize what we obtained
...
5
...
has a solution if and only
gcd(a1 , a2 ) divides n
...
of the equation a1 x1 + a2 x2 = n,
is a solution of the equation
If
(u1 , u2 )
is a solution
u1 −
a1
a2
t, u2 +
t ,
gcd(a1 , a2 )
gcd(a1 , a2 )
are solutions of the equation
then
t∈Z
a1 x 1 + a2 x 2 = n
...
First we nd the greatest common divisor of 132 and 187
...
3
...
Since 11 divides 55 we know that there are
in nitely many integer solutions
...
We obtained that
11
...
It implies that
55
...
a1 x1 + a2 x2 = n in x1 , x2 ∈ Z
...
We can handle equations of the form
have
gcd(a1 , a2 ) = 1,
then we can
What can we say about this equation if we allow only non-negative integers?
Let us deal with the equation
7x1 + 11x2 = n
...
Thus we have that
(−3n, 2n)
is a solution to the equation
7x1 + 11x2 = n
...
82
PROOF TECHNIQUES
We would like to have non-negative solutions, hence
−3n
11
−2n
...
7
11
[ −2n , −3n ], then n can be repre7
11
−2n
Denote by In the set t |
≤ t ≤ −3n , t ∈ Z
...
n
In
n
In
n
In
n
In
n
In
1
∅
16
∅
31
∅
46
{ −13 }
61
{ −17 }
2
∅
17
∅
32
{ −9 }
47
{ −13 }
62
{ −17 }
3
∅
18
{ −5 }
33
{ −9 }
48
∅
63
{ −18 }
4
∅
19
∅
34
∅
49
{ −14 }
64
{ −18 }
5
∅
20
∅
35
{ −10 }
50
{ −14 }
65
{ −18 }
6
∅
21
{ −6 }
36
{ −10 }
51
{ −14 }
66
{ −18 }
7
{ −2 }
22
{ −6 }
37
∅
52
∅
67
{ −19 }
8
∅
23
∅
38
∅
53
{ −15 }
68
{ −19 }
9
∅
24
∅
39
{ −11 }
54
{ −15 }
69
{ −19 }
10
∅
25
{ −7 }
40
{ −11 }
55
{ −15 }
70
{ −20 }
11
{ −3 }
26
∅
41
∅
56
{ −16 }
71
{ −20 }
12
∅
27
∅
42
{ −12 }
57
{ −16 }
72
{ −20 }
13
∅
28
{ −8 }
43
{ −12 }
58
{ −16 }
73
{ −20 }
14
{ −4 }
29
{ −8 }
44
{ −12 }
59
∅
74
{ −21 }
15
∅
30
∅
45
∅
60
{ −17 }
75
{ −21 }
In
is not empty, that is, those integers can be represented in the form 7x1 +11x2 :
We can nd 7 consecutive integers indicated in the table for which the set
n = 60
x1 = (−3) · 60 − 11 · (−17) = 7, x2 = 2 · 60 + 7 · (−17) = 1,
n = 61
x1 = (−3) · 61 − 11 · (−17) = 4, x2 = 2 · 61 + 7 · (−17) = 3,
n = 62
x1 = (−3) · 62 − 11 · (−17) = 1, x2 = 2 · 62 + 7 · (−17) = 5,
3
...
Given a solution for
n = 74
etc
...
we can easily nd a solution for
We use this idea to provide solutions for all
and
The
Division algorithm says that if we divide an integer by 7, then the remainder
is between 0 and 6
...
That is, if we have an integer
in the form
7x1 + 11x2
with
we get
k ≥ 0
...
In a similar way one computes the general solutions for the remaining cases
...
So
the techniques applied previously can be used here
...
then the equation can be written
as
y1 + 7x3 = n
...
It remains to determine the integer solutions of the equation
y1 = 4x1 + 5x2 = n + 7t
...
for some
It is easy to check that
x1 = −n + 3t,
x2 = n − t
is a solution
...
7x3 = 23
...
Some solutions are indicated in the following
table
(s, t)
(x1 , x2 , x3 )
(0, 0)
(−23, 23, 0)
(−1, 0)
(−18, 19, 0)
(0, −1)
(−26, 24, 1)
(1, 0)
(−28, 27, 0)
(0, 1)
(−20, 22, −1)
(−1, −1)
(−21, 20, 1)
(1, 1)
(−25, 26, −1)
What about non-negative integer solutions? That is, if one asks for solutions such that
n
x1 , x2 , x3 ∈ N∪{ 0 }
...
3
...
We try to eliminate
s
from the rst
and the second equations
...
That is, we obtain that
−
n
≤ t ≤ 0
...
7
s
...
Let us denote the two intervals as Is = [− 2n , − n ] and
5
7
5
n
It = [− 7 , 0]
...
If the length of
the interval Is is at least 1 and similarly for It , then for sure there will be
n
2n
= 3n and the length of It is n
...
The length of Is is − +
5
7
35
7
have that the length of Is is at least 1 if n ≥ 12 and the length of It is at least
1 if n ≥ 7
...
It means that
if n ≥ 12, then the equation 4x1 + 5x2 + 7x3 = n has non-negative integer
solution
...
therefore
86
PROOF TECHNIQUES
n
integer(s) in
Is
integer(s) in
It
solution(s):
(x1 , x2 , x3 )
1
-
0
-
2
-
0
-
3
-
0
-
4
-1
0
(1, 0, 0)
5
-1
0
(0, 1, 0)
6
-
0
-
7
-2
-1,0
(0, 0, 1)
8
-2
-1,0
(2, 0, 0)
9
-2
-1,0
(1, 1, 0)
10
-2
-1,0
(0, 2, 0)
11
-3
-1,0
(1, 0, 1)
We proved that if
n > 6,
then the equation
4x1 + 5x2 + 7x3 = n
has non-
negative integer solution
...
20
...
for some non-negative integers
Exercise 3
...
n ≥ 24
Prove that all integers
x1 , x2
...
for some non-negative integers
in case of integers of the form
Exercise 3
...
a formula for the solution
Parametrize all integer solutions of the equation
4x1 + 6x2 + 9x3 = n
...
23
...
3
...
First we prove the simplest form of
the pigeonhole principle
...
4
87
Pigeonhole principle
Theorem 3
...
n+1
If
pigeons are placed into
n
pigeonholes, then there
exists a pigeonhole containing at least 2 pigeons
...
Assume that the statement is false
...
In this case the total number of pigeons is at most
n,
a
contradiction
...
We have the following
...
7
...
Proof
...
Assume that the
statement is false, that is, each pigeonhole contains at most
obtain that the total number of pigeons is at most
there are
mn + 1
mn,
m
pigeons
...
Finally we prove a version where the pigeonholes may contain dierent
number of pigeons
...
8
...
, mn
pigeons are placed into
m1 + m2 +
...
If
n
pigeonholes, then
one has that the ith pigeonhole contains at least
mi
pigeons
...
Suppose that the rst pigeonhole contains at most
m1 − 1
pigeons,
m2 − 1 pigeons etc
...
pigeonholes can be at most
(m1 − 1) + (m2 − 1) +
...
+ mn − n,
a contradiction since there are
m1 + m2 +
...
To apply the pigeonhole principle one has to decide what the pigeons are
...
It is important that we need more pigeons than pigeonholes
...
88
PROOF TECHNIQUES
Proposition 3
...
There is a nonzero multiple of 6 whose digits are all zeroes
and ones
...
We apply the pigeonhole principle and the Division algorithm
...
We can write these
qn · 6 + rn , where qn is the quotient and rn is the remainder,
so 0 ≤ rn < 6
...
, a5
...
, a5 are odd integers while 6 is even,
hence rn = 0 for all n
...
There
are only 5 pigeonholes (possible remainders) and 6 pigeons (integers an )
...
where
In this case
am2 − am1
is divisible by 6 and all
the digits are zeroes and ones
...
It is clear that
of 6
Proposition 3
...
subset of
A
Let
A
be a set containing
n
integers
...
We have a set containing
We de ne
n ≥ 2
is a multiple
n
...
, an
...
, ak } ,
k = 1, 2,
...
, Sn = A
...
We apply the Division algorithm to write sk = qk · n + rk ,
where 0 ≤ rk < n
...
+ ak = qk · n,
3
...
If no such
for
rk
and we have
n
k
Sk
n
...
The pigeonhole principle says that there are
at least two subsets (say
Sk
and
Sl , k < l)
for which
rk = rl
...
+ al
...
, al } is a multiple
n
...
24
...
Exercise 3
...
Prove that among 1500 people, at least four were born on
the same day of the year
...
26
...
Exercise 3
...
We choose 11 integers from the set
{ 1, 2,
...
Prove
that 2 of the chosen integers are consecutive
...
28
...
29
...
, 100 }
...
Prove that if we choose 51 distinct
then there are at least two integers such that one of them
is divisible by the other
...
30
...
31
...
5
A card trick
In this section we introduce a card trick, which is based on several mathematical ideas
...
To
understand how it works one should be familiar with the pigeonhole principle, proof by contradiction and some tiny amount of combinatorics
...
An assistant asks the audience to choose ve cards from a normal deck of
52 playing cards
...
They pass those ve
cards to the assistant, who reveals four of them to the magician, one remains
only known by the audience and the assistant
...
This mathematical card trick was invented by William Fitch Cheney Jr
...
How does this trick work?
1
First we apply the pigeonhole principle to
obtain a very important imformation
...
diAn
application of pigeonhole principle yields that at least 2 cards must be of
the same suit
...
− J − Q − K
...
ordering of cards, e
...
having the same suit,
There are two cards
It is possible to de ne a distance between them
...
The second observation is that either d(C1 , C2 ) ≤
6 or d(C2 , C1 ) ≤ 6
...
Given
can be proved indirectly
...
Then
3
4
J
10
5
9
6
8
there must be at least 14 cards having the
1 William
Wallace Lee,
Maths Miracles, Durham, N
...
(1950)
7
3
...
Let us consider an example
...
This fact
is used to decide which card is going to be at the top of the pile
...
The assistant will place card
Ci
at the top of the pile and
will be the hidden card
...
Here comes a tiny combinatorics involved, three cards can
be ordered in
3! = 6
dierent ways
...
The 52 cards are ordered following
the rules:
rule I
...
:
So we have
♣ < ♦ < ♥ < ♠,
A < 2 < 3 <
...
< Q♠ < K♠
...
Let
us denote by 1 the card having the lowest rank, by 3 the card having the
highest rank and by 2 the remaining one
...
Here
3♣, K♣
are two
cards having the same suit
...
The assistant has to encode 3
...
That is,
d(K♣, 3♣) = 3 ⇒ 5♥, 8♦, Q♠
...
Exercise 3
...
What card is being encoded by the following sequences of
four cards?
7♣, 3♦, J♦, A♠,
(b) J♦, 9♣, Q♥, 8♥,
(c) 9♥, 10♥, J♦, 6♦,
(d) 10♦, 4♠, 2♠, 5♦,
(e) 8♠, 7♦, 7♥, 3♥
...
33
...
(a)
Chapter 4
Pascal's triangle
Let us create a triangle from numbers in the following way
...
This we call row zero of the triangle
...
We start and end every row by 1, and in between we write numbers which
are the sums of the two numbers above them, that is, we write the sum of
the upper left and upper right numbers
...
Then in
the second row we write 1, 2, 1, such that 2 is in between the two 1's of the
rst row
...
(see Table 4
...
This way,
one can easily compute the numbers occurring in the triangle row after row
...
Let us now take a closer look to these numbers
...
They look like the binomial coe cients
6
...
, n
...
6
row the
This is true for the rst
0
0
= 1
...
2)
...
,
n
n
94
PASCAL'S TRIANGLE
Table 4
...
1
1
1
1
1
4
5
6
2
3
1
1
1
1
3
1
6
10
15
4
1
10
20
5
15
1
6
1
Table 4
...
0
0
1
0
2
0
3
0
4
0
5
0
6
0
2
1
3
1
4
1
5
1
6
1
1
1
3
2
4
2
5
2
6
2
2
2
3
3
4
3
5
3
6
3
4
4
5
4
5
5
6
4
6
5
6
6
How can we prove that the two triangles are one and the same?
One
way to do it would be to prove that they can be generated by the same
rule
...
Considering the
with
n
n
= 1
...
2, it starts by
n
0
= 1,
and it ends
Thus we only need to check whether every other number is
the sum of the two numbers above it
...
Thus, if we
k−1
k
n
that
= n−1 + n−1 , then the two triangles are indeed the same
...
1
...
k−1
k
Proof
...
1) into the right-hand side:
n−1
n−1
+
k−1
k
(n − 1)!
(n − 1)!
+
=
(k − 1)! · (n − 1 − (k − 1))! k! · (n − 1 − k)!
(n − 1)!
(n − 1)!
+
=
(k − 1)! · (n − k)! k! · (n − k − 1)!
(n − 1)! · k + (n − 1)! · (n − k)
(n − 1)! · (k + n − k)
=
=
k! · (n − k)!
k! · (n − k)!
n!
n
(n − 1)! · n
=
=
...
1
...
This proof is a correct one, but not necessarily satisfying
...
One might wonder if there is an
k
n
easier proof, which only uses the de nition of
...
Second proof of Proposition 4
...
Let
number of
k -element
subsets of
we know that the number of
hand, we count the
contain the element
A
A = { 1, 2,
...
On the one hand,
k -element
subsets of
A
is
n
...
those which
96
PASCAL'S TRIANGLE
k -element subsets of A containing n rst
...
, n − 1 }
...
Thus,
k−1
n−1
A has k−1 -many k -element subsets containing the element n
...
If
a k -element subset S of A does not contain n, then it contains k elements
n−1
from { 1, 2,
...
Such a subset can be chosen in
-many ways
...
As
k
a k -element subset either contains or does not contain the element n, the
n−1
number of k -element subsets of A is
+ n−1 , which therefore must be
k−1
k
element subset
the same number as
Exercise 4
...
4
...
k
Compute the rst twelve rows of Pascal's triangle
...
In this
integers n
...
(x + y)2
...
1)
(x + y)2 = (x + y) · (x + y) = x2 + xy + yx + y 2 = x2 + 2xy + y 2
...
This is the threefold product of (x + y) with itself,
3
that is, (x + y) = (x + y) · (x + y) · (x + y)
...
1)
...
4
...
(x + y)5 = (x + y)4 · (x + y) = (x4 + 4x3 y + 6x2 y 2 + 4xy 3 + y 4 ) · (x + y)
= x5 + x4 y + 4x4 y + 4x3 y 2 + 6x3 y 2 + 6x2 y 3 + 4x2 y 3 + 4xy 4 + xy 4 + y 5
= x5 + 5x4 y + 10x3 y 2 + 10x2 y 3 + 5xy 4 + y 5
...
Let us summarize our ndings:
(x + y)2 = x2 + 2xy + y 2 ,
(x + y)3 = x3 + 3x2 y + 3xy 2 + y 3 ,
(x + y)4 = x4 + 4x3 y + 6x2 y 2 + 4xy 3 + y 4 ,
(x + y)5 = x5 + 5x4 y + 10x3 y 2 + 10x2 y 3 + 5xy 4 + y 5 ,
(x + y)6 = x6 + 6x5 y + 15x4 y 2 + 20x3 y 3 + 15x2 y 4 + 6xy 5 + y 6
...
Indeed, the coe cients
(x + y)6 are 1 = 6 , 6 = 6 , 15 = 6 , 20 = 6 , 15 = 6 , 6 = 6 ,
0
1
2
3
4
5
1 = 6
...
This is always the
k
of
case, not only for the rst six powers
...
Theorem 4
...
k
...
Then
n n−2 2
n
x y + ··· +
x2 y n−2 + nxy n−1 + y n
2
n−2
98
PASCAL'S TRIANGLE
n = 0 and n = 1, as
x1 y 0 + 1 x0 y 1
...
Note rst, that the Binomial theorem holds for
well:
0
0
(x + y)0 = 1 =
can prove the theorem
for
n − 1,
x0 y 0 , (x + y)1 = x + y = 1
0
by induction on n
...
n − 1 n−1−k k
x
y
...
2)
=
k=0
n−1
n−1
n − 1 n−k k
n − 1 n−1−k k+1
x y +
x
y
k
k
k=0
n−2
n − 1 n−k k
n − 1 n−1−k k+1
x y +
x
y
+ yn
k
k
k=0
n
=x +
k=1
n−1
n−1
n − 1 n−k k
n − 1 n−k k
x y +
x y + yn
k
k−1
k=1
n
=x +
k=1
n−1
(4
...
3)
(x + y)n−1 :
n−1
n−1
+
k
k−1
= xn +
k=1
n−1
n n−k k
x y + yn =
k
= xn +
k=1
Here, we have separated
xn
and
yn
xn−k y k + y n
n
k=0
n n−k k
x y
...
2), then re-indexed
the second sum in (4
...
, n − 1)
of the two sums
...
4) we used the
generating rule of Pascal's triangle (Proposition 4
...
Exercise 4
...
Repeat the proof by writing out all sums
...
Moreover, the
4
...
Nevertheless, one can nd another argument, which explains better why
the binomial coe cients arise in the
Consider
nth
power
...
How do we obtain the coe cient 15 for
product of
(x + y)
x4 y 2 ?
Now,
(x + y)6
is the 6-fold
by itself:
(x + y)6 = (x + y) · (x + y) · (x + y) · (x + y) · (x + y) · (x + y)
...
Thus the coe cient of
the number of possibilities to choose four times the
out of the six factors
...
This can be
4 2
x y is 6 = 15
...
4
...
Therefore the coe cient of
Prove the Binomial Theorem using the argument provided
above
...
5
...
For
is 1, as well, thus
n n−2 2
x
· 1 + · · · + nx · 1n−1 + 1n
2
n n−2
x
+ · · · + nx + 1 =
2
n
k=0
n k
x
...
Note that this
provides a second proof for Proposition 2
...
100
PASCAL'S TRIANGLE
Alternatively, we can substitute
−y
instead of
y
in the Binomial theorem,
obtaining
(x − y)n = xn + nxn−1 · (−y) +
n n−2 2
x y − · · · + (−1)n−1 nxy n−1 + (−1)n y n
2
= xn − nxn−1 y +
n
n n−k k
x y
...
6
...
k
(−1)k
=
n n−2
x
· (−y)2 + · · · + nx · (−y)n−1 + (−y)n
2
Write
x = 1, y = −1
into the Binomial theorem
...
7
...
Exercise 4
...
In the binomial expansion of
ascending powers of
4
...
Then nd the coe cient of
x5
...
Throughout this Section, we will rst conjecture what identities hold by looking at the
rst 12 rows of Pascal's triangle
...
2 is essential
before continuing
...
2
101
Identities
Let us start by the sum of the numbers in a row:
1 = 1,
1 + 1 = 2,
1 + 2 + 1 = 4,
1 + 3 + 3 + 1 = 8,
1 + 4 + 6 + 4 + 1 = 16,
1 + 5 + 10 + 10 + 5 + 1 = 32,
1 + 6 + 15 + 20 + 15 + 6 + 1 = 64
...
This stetement is equivalent to the equality
n
n
n
n
n
n
+
+
+ ··· +
+
+
0
1
2
n−2
n−1
n
= 2n
...
14, then later
in Exercise 4
...
Now, we prove it a third way, using the generating rule of
Pascal's triangle
...
This idea can be used in the general case, as well
...
The statement holds
(in fact, we just calculated that it holds for
statement holds for
row is
2n
...
Assume now that the
as well
...
0
0
1
1
2
2
3
n
n
n
n
n
+
+
+
+
+
n−2
n−1
n−1
n
n
n
n
n
n
n
n
=2·
+
+
+ ··· +
+
+
0
1
2
n−2
n−1
n
= 2 · 2n = 2n+1
...
Then we observed that every
n
k
occurs twice in the sum (for
0 ≤ k ≤ n)
...
Let us use a similar reasoning to calculate the sum of the numbers in a
row, with alternating signs
...
0
1
2
n−1
n
It is easy to compute this sum for the rst couple rows:
1 = 1,
1 − 1 = 0,
1 − 2 + 1 = 0,
1 − 3 + 3 − 1 = 0,
1 − 4 + 6 − 4 + 1 = 0,
1 − 5 + 10 − 10 + 5 − 1 = 0,
1 − 6 + 15 − 20 + 15 − 6 + 1 = 0,
1 − 7 + 21 − 35 + 35 − 21 + 7 − 1 = 0
...
the alternating sum of the numbers in the
nth
4
...
9
...
Why?
Let us try to use the former argument to compute the alternating sum of
the numbers in the 8th row:
1 − 8 + 28 − 56 + 70 − 56 + 28 − 8 + 1 = 1 − (1 + 7) + (7 + 21) − (21 + 35)
+ (35 + 35) − (35 + 21) + (21 + 7) − (7 + 1) + 1 = (1 − 1) + (−7 + 7)
+ (21 − 21) + (−35 + 35) + (35 − 35) + (−21 + 21) + (7 − 7) + (−1 + 1) = 0
...
Exercise 4
...
n
(−1)k ·
k=0
n
k
Prove that the alternating sum of the
=
nth
row is 0, that is,
n
n
n
n
−
+ · · · + (−1)n−1 ·
+ (−1)n ·
0
1
n−1
n
= 0
...
3
...
Consider the alternating sum of the
nth
= (−1)k ·
row (for
n ≥ 1),
n−1
...
0
0
1
1
2
n−1
n−1
n−1
n−1
+ (−1)k−1 ·
+
+ (−1)k ·
+
k−2
k−1
k−1
k
n−1
n−1
n−1
n−1
n−1
n−1
=
−
+ −
+
+
−
0
0
1
1
2
2
n−1
n−1
+ (−1)k−2 ·
+ (−1)k−1 ·
k−2
k−2
+
...
k
k
+ (−1)k−1 ·
First, we replaced
n
0
=1
by
n−1
0
= 1,
n
n
and
=1
by
n−1
n−1
= 1,
then we
used the generating rule of Pascal's triangle
...
The only term remaining is
n−1
...
3
...
We can
nd a pattern here, as well:
12 = 1,
12 + 12 = 2,
12 + 22 + 12 = 6,
12 + 32 + 32 + 12 = 20,
12 + 42 + 62 + 42 + 12 = 70,
12 + 52 + 102 + 102 + 52 + 12 = 252,
12 + 62 + 152 + 202 + 152 + 62 + 12 = 924
...
2, we
can observe that the results are the numbers occurring in the middle column
...
4
...
5)
k=0
n
k
2
=
n
0
2
+
n
1
2
+ ··· +
n
n−1
2
+
n
n
2
=
2n
...
2
105
Identities
Proof
...
The right hand side gives away a clue:
2n
n
is the number of ways to choose
n elements out of a 2n-element set (say
S = { 1, 2,
...
Our plan is to prove that the left hand side of (4
...
Let S1 = { 1, 2,
...
, 2n }
...
If we choose 0 element from S1 , then we must choose n
n
elements from S2
...
If we choose 1
0
n
element from S1 , then we must choose n − 1 elements from S2
...
If we choose 2 elements from S1 , then we must
1
n
n
choose n − 2 elements from S2
...
In
2
general, if we choose k elements from S1 , then we must choose n − k elements
n
n
from S2
...
In the end, if we choose
k
n elements from S1 , then we must choose 0 element from S2
...
Thus, choosing n elements out of 2n can be done in
n
0
the following number of ways:
n
n
n
n
n
n
n
·
+
·
+ ··· +
·
0
n
1
n−1
n
0
n
n
·
...
5):
n
n
n
n
n
n
n
·
+
·
+ ··· +
·
0
n
1
n−1
n
0
n
=
k=0
n
k
2
=
n
0
2
n
+
1
2
n
+ ··· +
n−1
2
n
n
·
k
n−k
=
k=0
n
+
n
2
...
5) counts the number of ways of choosing
out of a
a
2n-element
2n-element
set (or alternatively, the number of
set), and therefore must be equal
...
n elements
n-element
subsets of
106
PASCAL'S TRIANGLE
Exercise 4
...
l
k=0
(4
...
l
so that (4
...
5)?
We could have used the Binomial theorem to prove (4
...
4
...
k
=
k=0
Then the right hand side of (4
...
We
xn y n , as well
...
n
·
k=0
When do we obtain
by itself ? Take for example
factor, this must be multiplied by
y
n
n n−k k
x y
k
xn
xn y n
...
n
n
, the coe cient of y in the
0
n
n
second factor is
, thus this multiplication contributes by
· n to the
n
0
n
n n
2n
n−1
coe cient of x y in (x + y)
...
The coe cient of x y in the rst factor is n , the coe cient of
1
n
xy n−1 in the second factor is n−1 , thus this multiplication contributes by
n
n
· n−1 to the coe cient of xn y n in (x + y)2n
...
The coe cient of x
y in the rst factor is n , the coe cient of
k
n
k n−k
x y
in the second factor is
, thus this multiplication contributes by
n−k
n n
n−1
4
...
That is, the coe cient of
n
n
·
...
Applying the symmetry of Pascal's triangle (that is,
=
k
n
), we obtain (4
...
12
...
n
Solve Exercise 4
...
After dealing with sums of rows, consider sums where we move diagonally
upwards
...
For
m=0
it is pretty easy:
n
n−1
1
0
+
+ ··· +
+
0
0
0
0
For
m=1
= n + 1
...
1
...
2
3
3·2·1
Here, we used Exercise 3
...
108
PASCAL'S TRIANGLE
It is quite clear that by increasing
m,
we would have harder and harder
time to calculate the obtained sums
...
3·2
n+1
,
1
n+1
n+1
,
,
2
3
n
k
respectively
...
This is indeed the case
...
5
...
7)
k=m
k
m
=
m
m+1
n
+
+ ··· +
m
m
m
Proof
...
=
Fix
n+1
...
right hand side is
that the statement
n−1
k
m
k=m
n = m the left hand side is simply
m+1
= 1, and the statement holds
...
m+1
This is the induction hypothesis
...
Consider the sum
n
k=m
k
m
=
n
k
k=m m :
m
m+1
n−1
n
+
+
+ ··· +
m
m
m
m
n
=(m+1), by the induction hypothesis
=
n
n
+
m+1
m
=
n+1
...
2
109
Identities
Here, we rst used the induction hypothesis, then the generating rule of
Pascal's triangle (Proposition 4
...
Again, the induction proof clearly settles that our conjecture was true,
but it does not clarify the reason why this identity holds
...
7), we can understand what is behind
the curtain
...
5
...
n+1
m+1
Since
is the number of ways choosing
m+1
n-element set, this is what we will try to nd on the
well
...
, n, n + 1 }
...
choose m
elements
...
, m },
this can be done in
If we choose
elements out
m
-many ways
...
, m + 1 }, this can be done in
m + 3 as the largest chosen number, then we
need to choose m elements out of the (m + 2)-element set { 1, 2,
...
In general, if we choose k + 1 as
m
the largest chosen number (for some m ≤ k ≤ n), then we need to choose m
k
elements out of the k -element set { 1, 2,
...
If we choose n as the largest chosen number, then we need to choose m
elements out of the (n − 1)-element set { 1, 2,
...
Finally, if we choose n + 1 as the largest chosen number,
m
then we need to choose m elements out of the n-element set { 1, 2,
...
If we choose
m
this can be done in
choose
(m + 1)
n
-many ways
...
Thus the two numbers must
110
PASCAL'S TRIANGLE
be equal, as they count the same thing
...
m+1
=
Note, that from this identity we immediately obtain a formula for the
sum of integer numbers and for the sum of squares
...
38 (for
k can be expressed
k ≥ 2)
...
Similarly,
1
n
k =1+
k=1
k=2
n
=1+
k=2
k2 =
k+1
2
+
k
2
by
n
k+1
k
+
2
2
k=2
n
=
(n + 1) · n
,
2
=
k+1
k
+
2
2
2
1 + 2 + ··· + n =
n+1
2
n
2
k+1
k
+
+
2
2
2
k=2
k=2
n
=
k=1
n
k+1
k
+
2
2
k=2
n+1
=
k=2
n
k
k
+
2
2
k=2
n+2
n+1
+
3
3
(n + 2) · (n + 1) · n (n + 1) · n · (n − 1)
+
=
3·2
3·2
n · (n + 1)
=
· ((n + 2) + (n − 1))
3·2
n · (n + 1) · (2n + 1)
=
...
13
...
m
4
...
14
...
Prove that every number in row
for the rst and last) is divisible by
p
...
p
is
Chapter 5
Recurrence sequences
In this chapter we consider an important mathematical tool, the so-called
recurrence
...
5
...
k=1
That is, we have the de nition
if
n = 1,
n · (n − 1)!
n! =
1
if
n > 1
...
4! = 4 · 3 · (3 − 1)!
...
Binomial coe cients can be de ned via recurrence
...
k
k−1
5
...
5
3
We apply the above de nition to compute
5
3
4
3
We only need to determine
3
3
Since by de nition
= 1,
We have that
2
2
=
2
0
=1
5
3
3
3
+
3
2
3
3
+
...
2
and
3
2
3
1
3
2
and
3
...
1
0
=
=
2
1
k=n
4
4
+
...
Therefore
=1+1+2
= 1 + 2 + 2 + 1
...
Geometric progressions can be de ned using recurrence
...
Let
gn
be a
A generic term of the sequence
is given by the formula
gn = rgn−1 ,
where
r is the common ratio of the sequence
...
Now one may try to prove it by
induction
...
There are given three pegs (A, B and
initially stacked in decreasing size on peg
to transfer the
n
disks to peg
C
...
C)
and a tower of
disks,
The objective of the puzzle is
There are only a few rules
•
one can only move one disk per move,
•
one can only move the top disk of a stack,
•
If
n
one can not move a larger disk on top of a smaller disk
...
Let us deal with the case of 2 disks
...
Now we move the disk from peg
A
Finally, we move the disk from peg
to peg
B
C
...
5
...
Since no moves are
we have that T0 = 0, and the previous two
T2 = 3
...
In Tn−1 moves we can transfer the n − 1 smaller disks
from peg A to peg B
...
In total this strategy requires 2Tn−1 + 1 moves
...
If we follow another
strategy, then we must move the largest disk at some point and the n − 1
smallest disks must be on a single peg (requiring Tn−1 moves)
...
It means that Tn ≥ 2Tn−1 + 1, therefore
from peg
A
Tn
to peg
Tn = 2Tn−1 + 1
...
First we move the 2 smallest disks from peg
T2 = 3
steps
...
It can be done in
116
RECURRENCE SEQUENCES
STEP 3:
Now we can transfer the largest disk to peg
C
...
STEP 5:
STEP 6:
STEP 7:
Since
T3 = 7 we have found a solution with minimal number of moves
...
The following table contains the rst few values of
Tn
...
2
Linear recurrence relations of order
k
117
n Tn
n
Tn
n
Tn
0
0
4
15
8
255
1
1
5
31
9
511
2
3
6
63
10
1023
3
7
7
127
11
2047
One can easily observe that these values are 1 less than a power of 2, that
is, we expect that
5
...
It can be proved by induction
...
an ∈ S
For example
1, 2, 4, 8, 16, 32, 64,
...
De nition 5
...
relation of order
A sequence
k
{ an } ∞
n=0
is said to satisfy a linear recurrence
if
an = cn−1 an−1 + cn−2 an−2 +
...
, cn−k , bn
are some constants
...
In
a0 , a1 ,
...
For example the sequence appeared in case of Tower of Hanoi is a sequence
of order 1:
T0 = 0,
Tn = 2Tn−1 + 1
for
n ≥ 1
...
2
...
If
u = 1,
then
an = a0 + nv,
otherwise
an = un a0 +
Proof
...
u−1
then the de ning equation simpli es as follows
an = an−1 + v
...
The initial value of the sequence is
Using the above formula for
an
a0
...
Hence the statement is clearly true for
statement is true for
n = k,
n = 1, 2
and 3
...
n = k + 1 is that ak+1 = a0 + (k + 1)v
...
By induction we obtain that
The statement for
de nition we
recurrence
ak+1 = a0 + kv + v = a0 + (k + 1)v,
which is the desired result for
Now assume that
u = 1
...
We apply induction again
...
5
...
Assume that the statement
that is,
ak = uk a0 +
uk − 1
v
...
Using the
We need to show that the statement is true for
uk+1 −1
v
...
u−1
u−1
um − 1 = (u − 1) · (um−1 + um−2 +
...
+ u + 1
u−1
k
u = 1
...
+ u)v + v = (uk +
u−1
uk−1 +
...
Finally we obtain that
for
k+1
ak+1 = u
k
a0 + (u + u
k−1
+
...
It is easy to compute an explicit formula for the sequence
the problem of Tower of Hanoi
...
Tn = un T0 +
for
n ≥ 1,
The theorem implies that
un − 1
2n − 1
v = 2n · 0 +
· 1 = 2n − 1
...
related to
120
RECURRENCE SEQUENCES
We apply the theorem and we have
an = 2n · 3 +
2n − 1
· 2 = 2n · 3 + 2n+1 − 2 = 5 · 2n − 2
...
about higher order linear recurrence relations?
What
To make the presentation
simpler we will consider homogeneous linear recurrence relations of order
where
(5
...
So we study the structure of the recurrence given by
an = cn−1 an−1 + cn−2 an−2 +
...
, cn−k
Theorem 5
...
s, t
cn−k = 0, n ≥ k,
are some constants
...
1) and
are constants
...
1)
...
Since
k,
Un
and
Vn
satisfy (5
...
+ cn−k Un−k ,
Vn = cn−1 Vn−1 + cn−2 Vn−2 +
...
Substituting these formulas into the de nition of
Wn
we get
Wn =s(cn−1 Un−1 + cn−2 Un−2 +
...
+ cn−k Vn−k ) =
cn−1 (sUn−1 + tVn−1 ) + cn−2 (sUn−2 + tVn−2 ) +
...
+ cn−k Wn−k
...
1)
...
2
Linear recurrence relations of order
k
121
The previous theorem suggests a strategy to determine explicit formula
for higher order linear homogeneous recurrence relations
...
What kind of solutions should we look for? Here we
need some numerical experiences
...
2
...
Let us consider the ratio of consecutive elements of the sequence
...
951
2
5
6
≈ 3
...
6
7
≈ 2
...
154
8
≈ 3
...
At the beginning of this chapter we studied sequences
for which the ratio of consecutive elements is a constant, these are geometric progressions
...
If
gn
is a sequence given by the formula
gn = rgn−1 ,
where
r
is the common ratio of the sequence with initial value
have that
gn = g0 rn
...
gn
g0 ,
then we
is a geometric progression
...
122
RECURRENCE SEQUENCES
It follows that
g0 rn = 2g0 rn−1 + 3g0 rn−2
...
After dividing by
g0 rn−2
we get
r2 = 2r + 3
...
r
is a root of the quadratic polynomial
One can determine the roots by the well-known formula, which
is in our case
2±
That is, the roots are
3
and
−1
...
2
We have two dierent solutions of the
recurrence relation and Theorem 5
...
n
n
s3 + t(−1)
...
We get a system of equations in two unknowns
W0 = 2 ⇒ s · 30 + t · (−1)0 = 2,
W1 = 2 ⇒ s · 31 + t · (−1)1 = 2
...
The second equation can be written
as 3s + (2 − s)(−1) = 2, that is, 4s = 4 and we get that s = 1, t = 1
...
Thus Wn = an
...
We may try to apply the above method to determine an explicit formula for
the famous Fibonacci sequence:
F0 = 0,
F1 = 1,
Fn = Fn−1 + Fn−2 ,
n ≥ 2
...
2
Linear recurrence relations of order
Let
gn
k
123
be a geometric progression such that
Assume that
gn
gn = g0 rn
for some
g0
and
r
...
It follows that
r2 = r + 1
...
2
be a linear combination of the appropriate geometric progressions,
that is,
Wn = s ·
It remains to nd
s
and
t
√
1− 5
2
√
1+ 5
2
n
+t·
n
...
The above equations imply that
√
1− 5
2
s·
We immediately get that
s·
t = −s
...
2
Therefore
−s·
s=
√
1+ 5
2
√
− 5
, so
5
= 1
...
The explicit formula in
5
case of the Fibonacci sequence is
√
− 5
Fn =
·
5
√
1− 5
2
n
√
5
+
·
5
√
1+ 5
2
n
...
We de ne
an
as
a0 = 5,
a1 = −3,
a2 = 11,
an = −an−1 + 4an−2 + 4an−3 ,
The sequence
since
an
an
n ≥ 3
...
We try to nd
a geometric progression
gn = g0 rn
satisfying the above recurrence
g0 rn = −g0 rn−1 + 4g0 rn−2 + 4g0 rn−3
...
So we obtain
r3 + r2 − 4r − 4 = 0
...
We may try
to nd some special roots e
...
integral roots
...
If
r
is an integer, then the expression on the left-hand side is a multiple of
two integers
...
That is
Evaluate the cubic polynomial at these values:
r
r3 + r2 − 4r − 4
-4
-36
-2
0
-1
0
1
-6
2
0
4
60
r ∈ { −4, −2, −1, 1, 2, 4 }
...
2
Linear recurrence relations of order
k
We are lucky, there are 3 integral roots:
−2, −1
125
and 2
...
3 that any linear combinations of the geometric progressions
2n will satisfy the same recurrence relation as an
...
Our task is to x s, t and u such that
and
W0 = a0 = 5,
W1 = a1 = −3,
W2 = a2 = 11
...
s+t+u=5
−2s − t + 2u = −3
4s + t + 4u = 11
...
To do so
we multiply the rst equation by 4:
4s + 4t + 4u = 20
−2s − t + 2u = −3
4s + t + 4u = 11
...
The system of equations can be simpli ed now:
s+u=2
−2s + 2u = 0
...
s = u,
so from the rst equation we have
The explicit formula for the sequence
an
is
(−2)n + 3 · (−1)n + 2n
...
Without providing the details of the theory
126
RECURRENCE SEQUENCES
we note that it is also possible to handle such cases
...
We have that
rn
and
nrn
are solutions of
the same recurrence
...
nm−1 rn
are solutions of the same recurrence
...
u0 = 4,
u1 = −1,
u2 = −1,
u3 = −43,
un = 5un−1 − 6un−2 − 4un−3 + 8un−4 ,
The corresponding quartic polynomial
as
3
(r + 1)(r − 2)
n ≥ 4
...
Therefore we de ne
s · (−1)n + t · 2n + xn · 2n + yn2 · 2n
...
We get that
s = 4 − t,
written
hence
3t + 2x + 2y = 3
3t + 8x + 16y = −5
9t + 24x + 72y = −39
...
2
Linear recurrence relations of order
k
Using the rst equation we can eliminate
127
t
from the second and the third
equations
...
The above system has the solution
s = 3
...
We get that
t=1
and
Thus
un = 3 · (−1)n + 2n + n · 2n − n2 · 2n
...
is an integer sequence and 3 divides
un
for
n ≥ 1
...
9), but now we apply
the theory of linear recurrence sequences
...
If
√
√
3+ 33
3− 33
and
are roots of some
we have an appropriate recurrence, then
2
2
same closed-form solution
...
From this polynomial we have the following recurrence relation
6un−2
...
un−1 , un−2 have integral coe cients in the
recurrence relation, the sequence un is an integral sequence
...
Since
u0
and
u1
are integers and
128
RECURRENCE SEQUENCES
Exercise 5
...
Find the shortest sequence of moves that transfers a tower of
4 disks from peg
Exercise 5
...
A
to peg
C
...
3
...
and
Find an explicit formula for the following sequence de ned
by:
an = 4an−1 − 3an−2
Exercise 5
...
n≥2
for
a0 = 1, a1 = 13
...
5
...
Find an explicit formula for the following sequence de ned
by:
an = 6an−1 − 11an−2 + 6an−3
Exercise 5
...
for
n≥3
and
a0 = 0, a1 = 0, a2 = 1
...
7
...
Find an explicit formula for the following sequence de ned
by:
an = 5an−1 − 3an−2 − 9an−3
Exercise 5
...
n≥3
and
a0 = 3, a1 = 4, a2 = 29
...
9
...
Prove that the sequence de ned by
(4 −
√ n
√
2) + (4 + 2)n ,
contains only integers divisible by 2
...
1
Introduction
1
...
A = { 3, 4, 6, 7, 8 } , B = { 2, 4, 5, 6, 8 }
and
We have that
A \ B = { 3, 7 }
C ∩ B = { 2, 4, 5, 8 }
...
1
...
(A ∩ B) = { 4, 6 }
(C ∩ B) = { 4, 5, 8 }
...
1
...
(A \ B) = { 1, 3, 7 }
(C \ B) = { 1, 3 }
...
1
...
(b) The elements of the set are 0, 1 and 4
...
1
...
1
...
1
131
Introduction
(c)
A
B
C
(d)
A
B
C
(e)
A
B
C
(f )
132
SOLUTIONS
A
B
C
1
...
The conditions for
|A ∩ B|, |A ∩ C|
and
|B ∩ C|
are satis ed
...
We let A \ (B ∪ C) = { 3, 4 }
...
that
We obtain that
A
B
3,4
5,6
1,2
7,8
C
1
...
7 we get:
6
...
9 (a)
i = 4 + 5 + 6 + 7,
(b)
5
2
i=1 (i
(c)
4
i=1
(d)
1
2≤i≤5 2i
(e)
i
i∈S (−1) , where
1
...
2i,
+ 1),
(b)
1 + 4 + 7 + 10 =
(c)
1
4
1
+ 2 +1+2+4=
2
i=−2
(d)
1
4
1
− 2 +1−2+4=
2
i
i=−2 (−2)
...
11 (a)
i = (−4) · (−3) · (−2) · (−1),
(b)
4
2
i=1 (i )
(c)
3
i=1
(d)
1
−2≤i≤3 2i
(e)
i
i∈S (−1) , where
1
...
is
(−1)2 · (−1)4 · (−1)6 · (−1)7
...
13 The values are
0! = 1,
1! = 1,
2! = 2,
3! = 6,
4! = 24,
5! = 120,
6! = 720,
7! = 5 040,
8! = 40 320
...
14 The values are
5 + 3! = 5 + 6 = 11,
(5 + 3)! = 8! = 40 320,
4 − 2 · 3! = 4 − 2 · 6 = 4 − 12 = −8,
(4 − 2) · 3! = (4 − 2) · 6 = 2 · 6 = 12,
4 − (2 · 3)! = 4 − 6! = 4 − 720 = −716,
3 · 2! = 3 · 2 = 6,
(3 · 2)! = 6! = 720,
4 · 3! = 4 · 6 = 24,
4! · 5 = 24 · 5 = 120
...
15 Let
Sn = { k | k
is a positive integer, k
Then it is easy to see that
union of
Sn−1
and
{ n }
...
, n }
...
k∈Sn−1
6
...
(n−1)!
Nevertheless, the claim is true for
n = 1,
as well:
1! = 1 = 1 · 1 = 1 · 0!
...
16 (a) We obtain that
678 = 1 · 567 + 111
567 = 5 · 111 + 12
111 = 9 · 12 + 3
12 = 4 · 3 + 0
...
We work backwards to compute
x
and
3 = 111 − 9 · 12
= 111 − 9 · (567 − 5 · 111) = −9 · 567 + 46 · 111
= −9 · 567 + 46 · (678 − 567) = 46 · 678 − 55 · 567
...
(b) We get that
803 = 2 · 319 + 165
319 = 1 · 165 + 154
165 = 1 · 154 + 11
154 = 14 · 11 + 0
...
Now we nd
x
and
y:
11 = 165 − 154
= 165 − (319 − 165) = −319 + 2 · 165
= −319 + 2 · (803 − 2 · 319) = 2 · 803 − 5 · 319
...
(c) In this case the computations go as follows
2701 = 1 · 2257 + 444
2257 = 5 · 444 + 37
444 = 12 · 37 + 0
...
We determine
x
and
y:
37 = 2257 − 5 · 444
= 2257 − 5(2701 − 2257) = −5 · 2701 + 6 · 2257
...
(d) The summary of the computations:
3397 = 1 · 1849 + 1548
1849 = 1 · 1548 + 301
1548 = 5 · 301 + 43
301 = 7 · 43 + 0
...
It remains to compute
x
and
y:
43 = 1548 − 5 · 301
= 1548 − 5(1849 − 1548) = −5 · 1849 + 6 · 1548
= −5 · 1849 + 6(3397 − 1849) = 6 · 3397 − 11 · 1849
...
6
...
17 Write 21 in base 2 rst
...
Now, 4
is the highest 2-power not greater than 5,
5 = 1 · 4 + 1, and we continue
with the remainder 1
...
Thus
2110 = 1 · 16 + 1 · 4 + 1 · 1 = 1 · 24 + 1 · 22 + 1 · 20 = 101012
...
Here, 27 is the highest 3-power not greater
than 50,
50 = 1 · 27 + 23,
and we continue with the remainder 23
...
Now, 3 is the highest 3-power not
greater than 5,
5 = 1 · 3 + 2,
and we continue with the remainder 2
...
Thus
5010 = 1 · 27 + 2 · 9 + 1 · 3 + 2 · 1 = 1 · 33 + 2 · 32 + 1 · 31 + 2 · 30 = 12123
...
Now, 256 is the highest 16-power not
greater than 2814 (the next 16-power is 4096),
2814 = 10 · 256 + 254,
and we continue with the remainder 254
...
Finally, 1 is the highest 16-power not greater than
14,
14 = 14 · 1 + 0
...
1
...
21 = 10 · 2 + 1,
10 = 5 · 2 + 0,
5 = 2 · 2 + 1,
2 = 1 · 2 + 0,
1 = 0 · 2 + 1
...
Now, rewrite
5010
into base 3
...
The remainders backwards are 1, 2, 1, 2, thus
5010 = 12123
...
250 = 31 · 8 + 2,
31 = 3 · 8 + 7,
3 = 0 · 8 + 3
...
1
...
1
139
Introduction
1111012 = 6110 ,
211023 = 20010 ,
12345 = 19410 ,
12347 = 46610 ,
12348 = 66810 ,
7778 = 51110 ,
3458 = 22910 ,
20128 = 103410 ,
45658 = 242110 ,
11238 = 59510 ,
6668 = 43810 ,
7418 = 48110 ,
CAB16 = 324310 ,
BEE16 = 305410 ,
EEE16 = 382210 ,
4D416 = 123610 ,
ABC16 = 274810 ,
9B516 = 248510 ,
DDD16 = 354910 ,
3F 216 = 101010
...
(c)
11213 = 4310 = 1010112 ,
43125 = 58210 = 14617 ,
6548 = 42810 = 5259 ,
AD216 = 277010 = 110357 ,
5438 = 35510 = 1110113 ,
5439 = 44410 = 1211103
...
1
141
Introduction
4D316 = 100110100112 = 23238 ,
ABC16 = 1010101111002 = 52748 ,
F EE16 = 1111111011102 = 77568 ,
9B516 = 1001101101012 = 46658 ,
3F 216 = 11111100102 = 17628
...
2
Counting
2
...
Then if we rearrange the
summands ( rst with last, second with one but last, etc
...
n−1 n+3
n+1
+
+
= (n + 1) + (n + 1) +
...
= (n + 1) ·
2
2
2
+
If
n is even, then after rearranging the summands, no term will remain:
1 + 2 + · · · + (n − 1) + n = (1 + n) + (2 + n − 1) +
...
+ (n + 1) = (n + 1) ·
(n + 1) · n
n
=
...
2 If everyone shakes hands with three other, then they do not shake hand
with exactly one person
...
The rst person does not shake hand with someone
...
That leaves one person, who does not shake
hand with someone else, but everybody else has already been accounted
for about not shaking hands with somebody
...
This argument does not work if someone is allowed to shake hands
with someone else more than once
...
Use the same argument we used for proving Corollary 2
...
If we sum
up all the handshakes for everyone, we obtain
5 · 3 = 15,
as each of
the 5 people shakes hand with 3 others
...
2
143
Counting
to divide it by 2
...
This contradiction proves that it is
not possible that each of 5 people shakes hand with 3 others
...
handshakes for everyone, we obtain
shakes hand with 3 others
...
But
21/2
is not an integer, while the number of handshakes should
be an integer
...
2
...
kisses by the same
formula we use for handshakes
...
All four boys kiss all four girls on the cheek, which is
4 · 4 = 16
more
kisses
...
2
...
If there are ve packs, each of them containing odd
many rabbits, then altogether in the ve packs there are odd many
rabbits (odd+odd+odd+odd+odd is odd)
...
3 · 3 · 1 · 1 · 1
...
(b) It is possible, e
...
3 · 3 · 1 · 1 · 1 · 1 · (−1) · 1 · (−1),
9 · 1 · (−1) · 1 · (−1) · 1 · (−1) · 1 · (−1)
...
g
...
If the product of integer numbers is 9, then all of
them are odd
...
2
...
1 and obtain
1 + 2 + 3 + · · · + 23 + 24 =
24 · 25
= 300
...
One needs to calculate
the denominator, as we just calculated the numerator
...
Thus the fraction we needed to compute is
300
−12
= −25
...
2
2
...
Thus, the number
of
n-digit
positive integers in base 2 is
1 · 2 · · · · · 2 = 2n−1
...
Thus we can choose a in 9-many ways and b in 10-many ways,
and hence the number of three-digit palindrome numbers is 9 · 10 = 90
...
7 If
For determining the at most three-digit palindrome numbers, we need
to nd the one-digit long and two-digit long palindrome numbers
...
two-digit palindrome numbers: the
there are
9 + 9 + 90 = 108
aa10
There are exactly 9
numbers for
a = 0
...
Now, consider the number of
n-digit
palindrome numbers in base
k
...
Thus we need to count how many ways can we
choose the rst half
...
Then the rst digit is the same
as the last digit and diers from 0: there are
(k − 1)-many
possibilities
6
...
The second digit is the same as the one but
k -possibilities to choose this digit, etc
...
Thus, altogether the number of
n-digit base k palindrome numbers (for even n) is
last: there are
(k − 1) · k · · · · · k = (k − 1) · k n/2−1
...
Thus, altogether the number of
k
palindrome numbers (for odd
n)
n-digit
base
is
(k − 1) · k · · · · · k = (k − 1) · k (n−1)/2
...
8 There are 44 letters in the Hungarian alphabet, therefore there are
44n -many n letter long words in Hungarian by Theorem 2
...
That
5
7
10
is, 44 , 44 , 44 -many 5, 7, 10 letter long words can be created, respectively
...
9 There are three possibilities for every game, there are 14 games, thus
the number of required tickets is
3 · 3 · · · · · 3 = 314 = 4 782 969
...
10 We apply Theorem 2
...
Now, we allow spaces, thus the alphabet contains 27 letters
...
Thus, the number of possibilities is
2720 · 2 · 2710 · 108
...
2
...
The subsets of
The subsets of
{ Alice,
are
{ } = ∅, { a }, { b }, { c }, { a, b }, { a, c },
Beth, Carrie } are
{ Carrie }, { Alice, Beth }, { Alice,
{ Alice, Beth, Carrie }
...
The subsets of
All sets have 8 subsets
...
2
...
The set
2
...
That way, we obtain
2 · 2 · 2 = 8 subsets
...
These are the subsets of
{ a, b, c }
...
14 There are 8 subsets of
6
...
subsets of { a, b, c } with the element d added to them
...
15 The binary representation of the subsets of
{ a, b, c, d }
These are the
can be seen in
Table 6
...
Table 6
...
16 After computing the binary representation, we just add the elements
corresponding to the places where the digits are 1
...
17 After computing the binary representation, we just add the elements
corresponding to the places where the digits are 1
...
set of
of
2
...
decimal number
binary number
49
1100012
subset of
S
{ a0 , a4 , a5 }
2
...
decimal number
binary number
101
subset of
11001012
S
{ a0 , a2 , a5 , a6 }
2
...
decimal number
binary number
199
110001112
subset of
S
{ a0 , a1 , a2 , a6 , a7 }
2
...
2 on page 149
...
22 The number of permutations of
{ 1, 2, 3, 4 }
is
4! = 24
...
23 The number of permutations of
{ a, b, c, d }
is
4! = 24
...
2
149
Counting
Table 6
...
24 The number of permutations of 8 people is
8! = 40 320
...
150
SOLUTIONS
The boys can sit on their seats in
5! = 120-many
ways
...
Altogether, they can sit in
6 · 120 = 720-many
3! = 6-
ways
...
25 The number of anagrams of `retinas' is the same as the number of
permutations of the letters `r', `e', `t', `i', `n', `a' and `s'
...
2
...
This way, there will be
5! = 120-many
coloured anagrams of
puppy, the same as the number of permutations of ve dierent elements
...
For example the group `puppy' would contain `puppy',
`puppy', `puppy', `puppy', `puppy', `puppy'
...
The rst `p' can be coloured by 3 dierent
colours, the next `p' (right after the `u') can be coloured by two dierent colours (it cannot be coloured by the same colour as the rst `p'),
then the last `p' should be coloured by the remaining colour
...
Similarly, there are 6
coloured versions of every anagram
...
These are `pppuy', `pppyu', `ppupy',
`ppypu', `ppuyp', `ppyup', `puppy', `pyppu', `pupyp', `pypup', `puypp',
`pyupp', `upppy', `ypppu', `uppyp', `yppup', `upypp', `ypupp', `uyppp',
`yuppp'
...
27
(a) The word `college' contains 7 letters, two of them are `e's and two
of them are `l's, thus the number of anagrams is
7!
5 040
=
= 1 260
...
2!
2
6
...
2! · 2! · 2!
2·2·2
(d) The expression `discrete mathematics' contains 19 letters, two of
them are `i's, two of them are `s's, two of them are `c's, three of
them are `e's, three of them are `t's, two of them are `m's and two
of them are `a's, thus the number of anagrams is
19!
121 645 100 408 832 000
=
2! · 2! · 2! · 3! · 3! · 2! · 2!
2·2·2·6·6·2·2
= 105 594 705 216 000
...
2
...
Let us create the (not meaningful) word `aaaaabbbbccc',
and consider its anagrams
...
This anagram represents a distribution of
the bouquets among the triplets:
if a letter is `a' in the anagram,
the corresponding bouquet will be taken by Alice, if a letter is `b' in
the anagram, the corresponding bouquet will be taken by Beth, if a
letter is `c' in the anagram, the corresponding bouquet will be taken by
Carrie
...
This gives a one-to-one
152
SOLUTIONS
correspondence between the possible distributions of the bouquets and
the anagrams of `aaaaabbbbccc'
...
8 the number
of distributions is
12!
479 001 600
=
= 27 720
...
Imagine that the triplets put the 12 bouquets in some
order, and then Alice takes the rst 5, Beth takes the next four, and
Carrie takes the last three
...
Of course, some of these orders
give the same result: if we only permute the rst ve elements or the
next four elements, or the nal three elements, then clearly everyone
obtains exactly the same bouquets
...
That is, the number of possible distributions
is
479 001 600
12!
=
= 27 720
...
29 The two numbers are equal, as the following calculation shows
22!
22 · 21 · 20 · 19 · 18 · 17 · 16!
=
= 22 · 21 · 20 · 19 · 18 · 17
...
30 Altogether there are
n!
possible orders for the
number of permutations of
n
n
elements (this is the
elements)
...
Those cases will be considered the same where the rst
k
k
elements are the same (and in the same order)
...
We can name every group with the order
of the rst
k
elements
...
In one group there are those permutations, where the order
of the rst
k
elements is the same, thus they only dier in the last
6
...
There are (n − k)! possible permutations of the last
(n − k) elements, therefore every group contains (n − k)! orderings of
the n elements
...
2
...
9 the number of possibilities
(a) for the rst eight cars is
22 · 21 · 20 · 19 · 18 · 17 · 16 · 15 = 12 893 126 400,
(b) for the rst ten cars is
22 · 21 · 20 · 19 · 18 · 17 · 16 · 15 · 14 · 13 = 2 346 549 004 800
...
32 By Theorem 2
...
154
SOLUTIONS
2
...
5! · 85!
5! · 85!
5!
2
...
3 on page 201
...
35 By the de nition
n
0
n
1
n
2
n
n−2
=
=
=
=
=
n
n−1
n
n
=
=
n!
1
1
n!
=
=
= = 1,
0! · (n − 0)!
0! · n!
0!
1
n · (n − 1)!
n
n
n!
=
=
= = n,
1! · (n − 1)!
1! · (n − 1)!
1!
1
n!
n · (n − 1) · (n − 2)!
n · (n − 1)
n · (n − 1)
=
=
=
,
2! · (n − 2)!
2! · (n − 2)!
2!
2
n · (n − 1) · (n − 2)!
n · (n − 1)
n!
=
=
(n − 2)! · (n − (n − 2))!
(n − 2)! · 2!
2!
n · (n − 1)
,
2
n!
n · (n − 1)!
n
n
=
=
= = n,
(n − 1)! · (n − (n − 1))!
(n − 1)! · 1!
1!
1
n!
1
1
n!
=
=
= = 1
...
36 Using Table 6
...
34, it is not hard to determine the
required sums:
0
k=0
1
k=0
2
k=0
3
k=0
4
k=0
0
k
=
0
0
1
k
=
1
1
+
0
1
2
k
=
2
2
2
+
+
0
1
2
3
k
=
3
3
3
3
+
+
+
0
1
2
3
4
k
=
4
4
4
4
4
+
+
+
+
0
1
2
3
4
= 1,
= 1 + 1 = 2,
= 1 + 2 + 1 = 4,
= 1 + 3 + 3 + 1 = 8,
6
...
2
...
Here
n−1
,
2
and this is an integer number if and only if
n
n
2
2 n,
that is, if and only if
is odd
...
38 Using the formula for
n+1
n
+
2
2
n+1
2
and
n
2
we have
n2 + n n2 − n
(n + 1) · n n · (n − 1)
+
=
+
2
2
2
2
2
2
2
n +n+n −n
2n
=
=
= n2
...
, Pn
...
Then
they want to divide it into n parts by putting sticks between gold pieces
...
The rightmost part will go to Pn
...
What is left from the rst stick
is for P1 , what is between the rst and second sticks is for P2 , etc
...
They can put
2
...
They cannot put a stick before the rst
gold piece, because then
P1
would not get any pieces
...
Finally, they cannot put two sticks between the
same two gold pieces, because then one of the pirates would not get
156
SOLUTIONS
n−1
any gold piece
...
That is, they need to nd which
they put sticks to
...
This can be
k−1
-many ways
...
40 Let every pirate take one gold piece right at the very beginning
...
Moreover, now
every pirate needs one more gold piece
...
15:
n pirates want to distribute k − n gold
pieces such that everyone gets at least one gold piece
...
15
this can be done in
k−n−1
-many ways
...
41 All 15 possibilities are written in Table 6
...
2
...
18, we obtain
(a)
9−1
3−1
8
2
=
= 28,
(b)
8+3−1
3−1
=
10
2
= 45,
7+3−1
3−1
=
9
2
= 36,
11 − 3 − 1
3−1
=
7
2
= 21,
(c)
(d)
(e)
9−1
4−1
=
8
3
= 56,
(f )
7+4−1
4−1
=
10
3
= 120,
6
...
(j)
15 − 1 − 1 − 3 − 3 + 5 − 1
5−1
=
2
...
19, we obtain that the number of solutions is
(a)
9−1
3−1
8
2
=
= 28,
(b)
8+3−1
3−1
=
10
2
= 45,
7+3−1
3−1
=
9
2
= 36,
11 − 3 − 1
3−1
=
7
2
= 21,
(c)
(d)
(e)
9−1
4−1
8
3
=
= 56,
(f )
7+4−1
4−1
=
10
3
= 120,
7
3
= 35,
(g)
12 − 4 − 1
4−1
=
158
SOLUTIONS
(h)
10 − 1 − 2 − 3 + 4 − 1
4−1
7
3
=
= 35,
(i)
15 − 1 − 2 − 3 − 4 + 4 − 1
4−1
8
3
= 56,
11
4
= 330
...
44 It is the same problem as the gold distribution: imagine that everybody
of the three siblings gets the brand they like
...
There are
10−1
3−1
=
9
2
= 45-many
ways to do this by Theorem 2
...
2
...
9 we obtain that the number of choices is
(a)
9+3−1
3
=
11
3
= 165,
9+3−1
9
=
11
9
= 55,
(b)
(c)
10!
= 30 240,
5!
(d)
0,
(e)
45
6
= 8 145 060,
(f )
0,
6
...
160
6
...
1 The statement
S(n)
is that 8 divides
9n − 1
...
S(1) is true and S(2) is true as well
...
It remains to prove that S(k + 1) is true
...
Hence there exists an integer A
k
k+1
such that 9 − 1 = 8 · A
...
We have that
9(9k − 1) = 8 · A · 9
...
That is, 8 divides
9k+1 − 1
...
3
...
We compute
52n−1 + 1
for some small values:
52·1−1 + 1 = 6 = 1 · 6,
52·2−1 + 1 = 126 = 21 · 6
...
Assume
k ∈ N
...
We multiply this latter equation by
52 :
52 · 52k−1 + 52 = 6 · A · 52
...
S(k + 1)
on the left-hand side,
So we subtract 24 to obtain
52k+1 + 1 = 6 · A · 52 − 24 = 6(25A − 4)
...
3
161
Proof Techniques
It follows that 6 divides
proved that
S(n)
52k+1 + 1,
hence
is true
...
For
n ∈
we have
n
i=1 (2i
n
− 1)
1
1 = 12
2
1 + 3 = 22
3
1 + 3 + 5 = 32
4
1 + 3 + 5 + 7 = 42
5
1 + 3 + 5 + 7 + 9 = 52
Hence the given formula provides correct answers
...
3
...
Assume that
S(k)
S(n)
n2
...
i=1
It remains to show that
S(k + 1)
is true, that is,
k+1
(2i − 1) = (k + 1)2
...
+ (2k − 1)) + (2k + 1)
...
+ (2k − 1)) = k 2 ,
so we obtain
(1 + 3 +
...
Thus the statement
S(k + 1)
is true and the result follows
...
4 We consider here the sum of the rst
n
squares, which is
12 + 22 +
...
The statement
S(n)
is that
n
i2 =
i=1
n(n + 1)(2n + 1)
...
as the sum of the rst
n = 1, since 12 =
k ≥ 1, that is,
k(k + 1)(2k + 1)
...
Assume that
6
squares increased
k+1
k + 1 squares can be written
2
by (k + 1) , that is, we have
k
2
i2
i =
i=1
+ (k + 1)2
...
6
The right-hand side equals to
k(k + 1)(2k + 1) 6(k + 1)2
(k + 1) (k(2k + 1) + 6(k + 1))
+
=
=
6
6
6
(k + 1)(2k 2 + 7k + 6)
(k + 1)(k + 2)(2k + 3)
=
=
...
3
...
n
cubes in the following table for
n ∈
6
...
S(1), S(2), S(3) and S(4) are true
...
We try
S(k + 1) is true
...
i=1
By the induction hypothesis we can write the right-hand side as
k(k + 1)
2
2
+ (k + 1)3 =
(k + 1)2 2
(k + 4k + 4) =
4
S(k + 1)
integers n
...
6 Let
S(n)
be the statement that
i(i + 1) =
i=1
n = 2,
(k + 1)(k + 2)
2
2
...
3
then the left-hand side is
1
i(i + 1) = 2,
i=1
164
SOLUTIONS
and the right-hand side is
is true for some
1·2·3
, hence
3
1 ≤ k ∈ N
...
Assume that
S(k + 1)
S(k)
says that
k (k + 1) (k + 2)
...
3
Therefore
S(k + 1)
is true and the identity
n−1
i(i + 1) =
i=1
n
...
7 Let
S(n)
be the statement that
n
i=1
If
n = 1,
(n − 1) n (n + 1)
3
1
n
=
...
1
1
= ,
i(i + 1)
2
1
, hence
2
S(1)
The statement
k+1
i=1
is true
...
i(i + 1)
k+2
says that
S(k)
is
6
...
=
(k + 1)(k + 2)
k+2
=
Therefore
S(k + 1)
is true and the identity
n
i=1
1
n
=
i(i + 1)
n+1
is valid for all positive integers
n
...
8 Let us compute the rst few elements of the sequence
n
an
1
1
2
8
3
a2 + 2a1 = 10
4
a3 + 2a2 = 26
5
a4 + 2a3 = 46
Now we compute the values of the formula
3
2
· 2n + 2 · (−1)n
for
n∈
{ 1, 2, 3, 4, 5 }
n
3 n
2
2
+ 2(−1)n
1
2
26
5
46
· 2n + 2 · (−1)n for n ∈ { 1, 2, 3, 4, 5 }
...
2
ak−1 =
The statement for
3
k+1 is that ak+1 = 2 ·2k+1 +2·(−1)k+1
...
Hence by the induction hypotheses we obtain
ak+1 =
3 k
· 2 + 2 · (−1)k + 2
2
3 k−1
·2
+ 2 · (−1)k−1
...
We showed that the given
formula is correct
...
9 We note that there is a solution in Chapter 5 which does not use induction
...
Our statement
S(n)
is
that the number
f (n) =
3−
√
33
2
n
+
3+
√
33
n
2
is an integer and it is a multiple of 3
...
If
n = 1,
then we get that
and it is a multiple of 3
...
So it is an integer
then we have
√
√
9 − 6 33 + 33 9 + 6 33 + 33
+
= 21
...
Assume that
S(k −
are true for some 2 ≤ k ∈ N
...
3
167
Proof Techniques
that is, we have
√
33
2
√
3 + 33
2
2
3−
3−
=3·
2
3+
=3·
√
2
√
33
+ 6,
33
+ 6
...
What about
f (k + 1) =
3−
√
33
3−
√
33
k+1
+
2
k−1
3·
2
√
3 − 33
3·
2
k
+
3−
√
3+
33
k+1
=
2
33
2
√
3 + 33
2
√
+6
k
3+
+
√
33
k−1
3·
2
+6· 3−
√
33
k−1
2
+
√
33
2
√
3 + 33
2
3+
3f (k) + 6f (k − 1)
...
3
...
4142
2
≈ 1
...
9615
4
≈ 1
...
9975
S(n) be the statement that an ≤ 2
...
Assume that S(k) is true for some k ≥ 1, that is, ak ≤ 2
...
By de nition of the sequence we
Let
have
ak+1 =
√
2 + ak
...
By the induction hypothesis
The statement
for all
S(k + 1) has been proved and thus we have that an ≤ 2
n ∈ N
...
Therefore the statement is true for n = 1
...
There are only four possible
3
...
If
integers
a1 a2 ∈ { 11, 12, 21, 22 }
...
Assume that the statement is true
that is, there exists a
2k
...
ak
for k + 1
...
ak = 2k · A
...
ak = 1a1 a2
...
ak = 2a1 a2
...
We can rewrite the above integers as follows
10k + a1 a2
...
ak = 2 · 10k + 2k · A = 2k (2 · 5k + A)
...
In this case
1a1 a2
...
is even
...
ak
is a
(k + 1)-digit
number which is a multiple of
2k+1
...
3
169
Proof Techniques
3
...
n
Let us consider the sum of the rst
elements for
n ∈ { 1, 2, 3, 4, 5 }
n = 1 : 1,
n = 2 : 1 + 1 = 2,
n = 3 : 1 + 1 + 2 = 4,
n = 4 : 1 + 1 + 2 + 3 = 7,
n = 5 : 1 + 1 + 2 + 3 + 5 = 12
...
1 ≤ k ∈ N, that is,
It is easy to see that the identity holds for
that the statement is true for some
F1 + F2 +
...
Consider the sum of the rst
k+1
Fibonacci numbers
F1 + F2 +
...
By induction hypothesis we get
F1 + F2 +
...
By de nition
Fk+1 + Fk+2 = Fk+3 ,
hence
F1 + F2 +
...
Therefore the identity holds for all positive integers
...
+ Fn
for
n ∈ { 1, 2, 3, 4, 5 }
n = 1 : 1 2 = 1 = F1 F2 ,
n = 2 : 1 2 + 1 2 = 2 = F2 F3 ,
n = 3 : 12 + 12 + 22 = 6 = F3 F4 ,
n = 4 : 12 + 12 + 22 + 32 = 15 = F4 F5 ,
n = 5 : 12 + 12 + 22 + 32 + 52 = 40 = F5 F6
...
1 ≤ k ∈ N, that is,
That is, the identity is valid for
statement is true for some
Assume that the
2
2
2
F1 + F2 +
...
Let us deal with the sum
2
2
2
2
F1 + F2 +
...
Applying the induction hypothesis we obtain
2
2
2
2
2
(F1 + F2 +
...
+ Fk ) + Fk+1 = Fk+1 Fk+2
...
(c) Here we consider the identity
F1 + F3 +
...
n = 1, then the left-hand side is F1 = 1 and the right-hand side is
F2 = 1
...
Assume that for some 1 ≤ k ∈ N
If
the identity is valid, that is,
F1 + F3 +
...
In case of
k+1
terms we have
F1 + F3 +
...
By induction we get
(F1 + F3 +
...
Thus the identity is valid for all positive integers
...
+ F2n = F2n+1 − 1
...
3
171
Proof Techniques
n = 1, then the left-hand side is F2 = 1 and the right-hand side is
F3 − 1 = 2 − 1 = 1
...
Assume that for some
1 ≤ k ∈ N the identity holds, that is,
If
F2 + F4 +
...
Let us handle the sum for
k+1
terms, that is, the sum
F2 + F4 +
...
It can be written as
(F2 + F4 +
...
Thus the identity has been proved for all positive integers
...
13 (a) First compute
F3n
for some
n,
let say for
n = 1, 2, 3
...
F3n is even for n = 1, 2, 3
...
For k + 1 we have F3(k+1) = F3k+3
...
By induction
F3k
is even, so
2 · F3k+1 + F3k
is even
...
(b) If
n = 1,
Assume that
then
F5k
F5·1 = 5
...
k + 1 we
That is, the property holds for
is a multiple of 5 for some
1 ≤ k ∈ N
...
It is clear that 5 divides
3F5k
5F5k+1
and induction hypothesis implies that
is a multiple of 5
...
k + 1
...
F5n
We proved
is a multiple of 5 for all
172
SOLUTIONS
3
...
Assume that
x ≤ 5
and
y ≤ 5
...
3
...
Then for some k ∈ Z
n2 − 2 = 4k
...
It follows that n is
n = 2n1 for some integer n1
...
1
After dividing the equation by 2 we get
2(n2 − k) = 1,
1
a contradiction since 2 does not divide 1
...
Then
√
√
a
2 + 3 = b for some a ∈ Z and b ∈ N
there exist a and b such that
and the greatest common divisor of a and b is 1
...
16 Assume the opposite, that is, the number
√
a2
2+2 6+3 = 2
...
2b2
On the right-hand side there is a rational number, so to get a contra-
√
diction we have to prove that
√
6
is irrational
...
√
c
6 is rational
...
We obtain that
6d2 = c2 ,
that is,
c
is even
...
6d2 = 4c2 ⇒ 3d2 = 2c2
...
3
173
Proof Techniques
We have that 2 divides
It means that
that
√
6
d2
3d2
...
We have proved
√
is irrational and thus we have that
2+
√
3
is irrational
...
17 Suppose the opposite of the statement, that is, there exists
p ∈ Z, q ∈ N
and
gcd(p, q) = 1
p
q
a
Multiply the equation by
q2
d2
...
q
to obtain (we note that
q = 0)
ap2 + bpq + cq 2 = 0
...
In this case ap2 is even, bpq is even
2
2
2
and cq is odd
...
Now
2
assume that p is odd and q is even
...
Again we get a contradiction
...
We get that ap is odd, bpq is odd and
cq 2 is odd, so ap2 + bpq + cq 2 is odd, a contradiction
...
The
Assume that
statement follows
...
18 Assume that the statement is false, that is,
a1 + a2 +
...
+ an
a2 <
,
n
a1 <
...
...
+ an
...
+ an < n ·
a1 + a2 +
...
+ an
...
174
SOLUTIONS
3
...
integer
n
Assume that there exists a positive
for which
gcd(Fn , Fn+1 ) = d > 1
...
Then
d divides the dierence
of these two Fibonacci numbers
...
Since
d
divides the left-hand side we obtain that
hand side, that is,
d | Fn−1
...
d | Fn−2
...
Since Fn−1 − Fn−2 = Fn−3 we obtain
In this way we get that
d | Fn−2 , so d | (Fn−1
that d divides Fn−3
...
Hence for consecutive Fibonacci
numbers Fn and Fn+1 we have
gcd(Fn , Fn+1 ) = 1
...
20 First we solve the equation
5x1 + 7x2 = 1 in integers x1 , x2
by applying
the Euclidean algorithm
...
By Theorem 3
...
non-negative solutions we need
3n
7
2n
−2n + 5t ≥ 0 ⇒ t ≥
...
3
175
Proof Techniques
So we have the following inequalities
3n
2n
≤t≤
...
Denote by In the set t | 2n ≤ t ≤ 3n , t ∈ Z
...
However for all
n ∈ { 24, 25, 26, 27, 28 }
we have solutions
...
3
...
Hence we have a particular solution
(x1 , x2 ) = (−n, n)
in case of the equation
4x1 + 5x2 = n
...
To have non-negative solutions one needs
−n
5
−n
n + 4t ≥ 0 ⇒ t ≥
...
4
5
t | −n ≤ t ≤ −n, t ∈ Z
4
5
...
n
In
n
In
n
In
1
∅
6
∅
11
∅
2
∅
7
∅
12
{ −3 }
3
∅
8
{ −2 }
13
{ −3 }
4
{ −1 }
9
{ −2 }
14
{ −3 }
5
{ −1 }
10
{ −2 }
15
{ −3 }
n = 11 cannot be represented in the appropriate form
...
In case of 13 we have
So we get that
13 = 4 · 2 + 5 · 1
...
Thus, if
n = 4K + 1,
then
(x1 , x2 ) = (K − 1, 1), K ≥ 1
...
22 We can rewrite the equation as
2(2x1 + 3x2 ) + 9x3 = n
and another possibility is as follows
4x1 + 3(2x2 + 3x3 ) = n
...
So we have
4x1 + 3y1 = n
...
3
177
Proof Techniques
A particular solution is
(n, −n),
therefore we get
x1 = n + 3t,
y1 = −n − 4t
for some
t ∈ Z
...
This equation
(n − 2t, −n), therefore we obtain that
We have that
has a particular solution
x2 = n − 2t + 3s,
x3 = −n − 2s
for some
s, t ∈ Z
...
3
...
It is as follows
x1 = n + 3t,
x2 = n − 2t + 3s,
x3 = −n − 2s
for some
s, t ∈ Z
...
We easily obtain upper bound for
s
and lower bound for
n
≤ t,
3
n
− ≥ s
...
That is,
−5n ≤ 9s,
4t ≤ −n
...
De ne the
5n
, − n ] and It = [− n , − n ]
...
Therefore the equation has a non-negative integer solution if n ≥ 18
...
Now we have lower bound for
n
integer(s) in
Is
s
and upper bound for
integer(s) in
It
solution(s):
(x1 , x2 , x3 )
1
-
-
-
2
-1
-
-
3
-
-1
-
4
-2
-1
(1, 0, 0)
5
-
-
-
6
-3
-2
(0, 1, 0)
7
-
-2
-
8
-4
-2
(2, 0, 0)
9
-5
-3
(0, 0, 1)
10
-5
-3
(1, 1, 0)
11
-6
-3
-
12
-6
-4,-3
(0, 2, 0), (3, 0, 0)
13
-7
-4
(1, 0, 1)
14
-7
-4
(2, 1, 0)
15
-8
-5,-4
(0, 1, 1)
16
-8
-5,-4
(1, 2, 0), (4, 0, 0)
17
-9
-5
(2, 0, 1)
6
...
3
...
There are 367 people (playing the role of pigeons)
...
3
...
There are 1500 people and
1500
366
≈ 4
...
That means that at least
4 people were born on the same day of the year
...
26 We de ne the pigeonholes as disjoint subsets of the set
{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 } ,
that is,
{ 1, 12 } , { 2, 11 } , { 3, 10 } , { 4, 9 } , { 5, 8 } , { 6, 7 }
...
We have six pigeonholes and
seven pigeons, therefore there exists a subset containing two selected
integers
...
3
...
We de ne the pigeonholes as
follows:
{ 1, 2 } , { 3, 4 } , { 5, 6 } , { 7, 8 } , { 9, 10 } ,
{ 11, 12 } , { 13, 14 } , { 15, 16 } , { 17, 18 } , { 19, 20 }
...
Thus the statement is true
...
28 We divide the unit square into four smaller squares:
q q
q
q
q
The subsquares are the pigeonholes and the points are the pigeons
...
The largest distance in a subsquare is the length of
√
2/2
...
3
...
There are 50 odd integers in the
interval
[1, 2,
...
That is,
2a1 · b divides
among the 51 integers there are at least two with the same
we have two integers
a2
2 · b
...
If
a1 < a 2 ,
then
The statement is proved
...
30 We apply Theorem 3
...
Here the pigeonholes are the grades, so
m2 students who get grade 2
etc
...
Hence we take m1 = m2 = m3 = m4 = m5 = 4
...
students who get grade 1,
be at least 16 students in the class
...
31 We note that it is possible to place 14 bishops such that they cannot
hit each other, a solution is given by
6
...
A natural idea is to
divide the 64 chess squares into 14 groups such that if two bishops are
in the same group then they can hit each other
...
32 (a) The rst card is
7♣,
hence the suit of the hidden card is
distance can be obtained from the following table
distance
order of the 3 cards
1
3♦, J♦, A♠
2
3♦, A♠, J♦
3
J♦, 3♦, A♠
4
J♦, A♠, 3♦
5
A♠, 3♦, J♦
6
A♠, J♦, 3♦
♣
...
= 1
...
(b) The suit of the secret card is
is
card)
♦
since the rst card in the sequence
It remains to decode the distance of the secret card and
distance
order of the 3 cards
1
9♣, 8♥, Q♥
2
9♣, Q♥, 8♥
3
8♥, 9♣, Q♥
4
8♥, Q♥, 9♣
5
Q♥, 9♣, 8♥
6
J♦ :
Q♥, 8♥, 9♣
We get that the distance is 2, so the secret card is
(c) It is clear that the suit of the hidden card is
K♦
...
We can determine
the distance using the following table
distance
order of the 3 cards
1
6♦, J♦, 10♥
2
6♦, 10♥, J♦
3
J♦, 6♦, 10♥
4
J♦, 10♥, 6♦
5
10♥, 6♦, J♦
6
10♥, J♦, 6♦
In this case the distance is 6, therefore the hidden card is
(d) The rst card is
2♥
...
to gure out the distance
...
3
183
Proof Techniques
distance
order of the 3 cards
1
5♦, 2♠, 4♠
2
5♦, 4♠, 2♠
3
2♠, 5♦, 4♠
4
2♠, 4♠, 5♦
5
4♠, 5♦, 2♠
6
4♠, 2♠, 5♦
4♠, 2♠, 5♦, hence the distance
is 3♦
...
Thus the announced hidden card
(e) It is easy to see that the suit of the hidden card is
♠
...
Therefore the hidden card
is
10♠
...
33 (a) We need two cards having the same suit
...
If the hidden card is
7♣,
then we have to encode 4 using the cards
2♦ < 5♦ < A♠
...
If the secret card is
5♦, then the distance to encode is 3, which is 2,1,3
...
(b) The assistant chooses
d(J♦, A♦) = 3
...
We have that
One encodes distance 3 as 2,1,3
...
(c) The hidden card is
8♠,
the distance is 1, therefore the assistant
hands the four cards in the following order to the magician
7♠, A♣, 6♦, K♥
...
3♠, 7♠ ⇒
hidden card:
7♠,
distance:
4,
(II)
...
7♠, 9♠ ⇒
hidden card:
9♠,
distance:
2
...
3♠, 8♦, 9♠, 7♣,
(II)
...
7♠, 7♣, 3♠, 8♦
...
J♦, Q♦ ⇒
hidden card:
Q♦,
(II)
...
6
...
J♦, 7♥, 10♥, 3♠,
(II)
...
186
6
...
1 We prove that the two triangles are the same by induction
...
For n = 0 the two triangles have
0
the same zero row:
= 1
...
We prove that the two triangles contain the same
numbers in the nth row, as well
...
Now, consider the k th element of the nth
0
n
row for an arbitrary 1 ≤ k ≤ n − 1
...
By the induction hypotheses, row n − 1
prove that the
is the same in Pascal's triangle and in the triangle of the Binomial
(k − 1)st element of row (n − 1) is n−1 ,
k−1
n−1
the k th element of row (n − 1) is
...
1 we have
k
n−1
n−1
n
+ k = k
...
This is true for arbitrary 1 ≤ k ≤ n − 1,
thus the nth row of Pascal's triangle is the same as the nth row of the
coe cients
...
This nishes the induction proof,
the two triangles are the same
...
2 The rst twelve rows of Pascal's triangle can be seen in Table 6
...
n = 0 and n = 1, as well: (x + y)0 =
(x + y)1 = x + y = 1 x1 y 0 + 1 x0 y 1
...
Assume that the statement holds for
4
...
1
1
This is the induction hypothesis
...
4
187
Pascal's triangle
(x + y)n−1 :
(x + y)n = (x + y)n−1 · (x + y)
n−1
n − 1 n−2
x y + ··· +
xy n−2 + y n−1 · (x + y)
1
n−2
n − 1 n−2
n−1
= xn−1 +
x y + ··· +
xy n−2 + y n−1 · x
1
n−2
n − 1 n−2
n−1
+ xn−1 +
x y + ··· +
xy n−2 + y n−1 · y
1
n−2
n − 1 n−1
n − 1 2 n−2
= xn +
x y + ··· +
xy
+ xy n−1
1
n−2
n − 1 n−2 2
n−1
+ xn−1 y +
x y + ··· +
xy n−1 + y n
1
n−2
n − 1 n−1
n − 1 2 n−2
n−1
= xn +
x y + ··· +
xy
+
xy n−1
1
n−2
n−1
n − 1 n−1
n − 1 n−2 2
n−1
+
x y+
x y + ··· +
xy n−1 + y n
0
1
n−2
n−1
n−1
= xn +
+
xn−1 y +
...
k
k−1
n−1
n−1
··· +
+
xy n−1 + y n
n−1
n−2
=
xn−1 +
(6
...
1
k
n−1
(x + y)n−1 using the induction hypothesis,
by (x + y) by expanding the brackets
...
, n −
Here, we have expanded
and multiplied it
collected together
1, n
...
1) we used the generating rule of Pascal's triangle
(Proposition 4
...
4
...
, a1 , a0
...
(x + y)(x + y)
...
Thus the co-
xn−k y k is the number of possibilities to choose (n − k)-times
the x and k -times the y out of the n factors
...
This can be done in
n
n−k k
-many ways
...
k
k
e cient of
4
...
k
4
...
k
6
...
7 Using the Binomial theorem we obtain
8
8
(x + y) =
k=0
8 8−k k
x y = x8 + 8x7 y + 28x6 y 2 + 56x5 y 3
k
+ 70x4 y 4 + 56x3 y 5 + 28x2 y 6 + 8xy 7 + y 8 ,
8
8
(x − y) =
k=0
8 8−k
x
(−y)k = x8 − 8x7 y + 28x6 y 2 − 56x5 y 3
k
+ 70x4 y 4 − 56x3 y 5 + 28x2 y 6 − 8xy 7 + y 8 ,
10
(a + 1)
10
=
k=0
10
· a10−k · 1k = a10 + 10a9 + 45a8 + 120a7
k
+ 210a6 + 252a5 + 210a4 + 120a3 + 45a2 + 10a + 1,
5
5
(b − 3) =
k=0
5 5−k
b
(−3)k = b5 − 15b4 + 90b3
k
− 270b2 + 405b − 243,
5
(1 + 2/x)5 =
k=0
6
(a + b)6 =
k=0
5
· 15−k ·
k
2
x
k
=1+
10 40 80 80 32
+ 2 + 3 + 4 + 5,
x
x
x
x
x
6 6−k k
a b = a6 + 6a5 b + 15a4 b2 + 20a3 b3
k
+ 15a2 b4 + 6ab5 + b6 ,
5
5
(1 + x) =
k=0
5
· 15−k · xk = 1 + 5x + 10x2
k
+ 10x3 + 5x4 + x5 ,
4
4
(3a + 4b) =
k=0
4
· (3a)4−k · (4b)k = (3a)4 + 4 · (3a)3 · (4b)
k
+ 6 · (3a)2 · (4b)2 + 4 · (3a) · (4b)3 + (4b)4 = 81a4
+ 432a3 b + 864a2 b2 + 768ab3 + 256b4 ,
4
4
(3 − 2x) =
k=0
4
· 34−k · (−2x)k = 34 − 4 · 33 · (2x) + 6 · 32 · (2x)2
k
− 4 · 3 · (2x)3 + (2x)4 = 81 − 216x + 216x2 − 96x3 + 16x4
...
8 By the Binomial theorem
1−
x
2
9
9
=
k=0
9
x
· 19−k · −
2
k
4
...
(−1)3 · 9 /23 x3 =
3
5 9
5
The coe cient of x is (−1) ·
/25 =
5
Here, the fourth term corresponds to
−84/8x3 = −21/2x3 = −10
...
−126/32 = −63/16 = −3
...
9
k
x3 ,
that is,
is odd, then every binomial coe cient occurs twice in the sum:
once with positive sign, and once with negative sign
...
(−1)n−k
...
4
...
0
0
1
1
2
n−1
n−1
n−1
+ (−1)n−1 ·
+
+ (−1)n ·
n−2
n−1
n−1
n−1
n−1
n−1
n−1
n−1
n−1
=
−
+ −
+
+
−
0
0
1
1
2
2
n−1
n−1
+ (−1)n−2 ·
+ (−1)n−1 ·
n−2
n−2
n−1
n−1
+ (−1)n−1 ·
+ (−1)n ·
n−1
n−1
= 0 + 0 + 0 + · · · + 0 + 0 = 0
...
Then we observed
that every
n−1
k
occurs twice in the sum: rst with a positive sign, then
right after it with a negative sign (for
0 ≤ k ≤ n − 1)
...
6
...
11 Again, we give a combinatorial meaning to both sides of (4
...
right hand side gives a clue:
elements out of an
n+m
l
The
is the number of ways to choose
(n + m)-element
l
set, say
S = { 1, 2,
...
, n + m }
...
6) is the number
l-element subsets of S , as well
...
, n } and S2 =
{ n + 1, n + 2,
...
Now, try to count the number of ways to
choose l elements of S by counting how many elements we choose from
S1 and from S2
...
We can do this in
· m -many ways
...
We
n
m
can do this in
· l−1 -many ways
...
We can do this in
n
m
· l−2 -many ways
...
We can do this in
· l−k k
many ways
...
We can do this in
· m -many ways
...
k
l−k
That is, both sides of (4
...
and use the symmetry of Pascal's triangle
n
, then we obtain exactly equation (4
...
n−k
4
...
k
Then the right hand side of (4
...
xn+m−l y l ,
as well
...
xn−k y k by
Now, let us compute the coe cient of
xn+m−l y l
n
n
k=0 k
n−k k
when we multiply
m
k=0
m m−k k
x
y
k
When do we obtain
m
m
k=0 k
xm−k y k
?
0 ≤ k ≤ l the term x y in the rst factor must be multim−l+k l−k
plied by x
y from the second factor
...
That is, the coe cient of xn+m−l y l in
(x + y)n+m is
l
n
m
·
...
6):
n
k=0
n
m
·
k
l−k
n+m
...
13 We can try to prove the identity by induction on
identity holds, as the left hand side is
n+1
0
m−1
k=0
= 1,
n
0
= 1,
m
...
m−1
This is the induction hypothesis
...
n
n+1
n+m−1
n+m
+
+ ··· +
+
0
1
m−1
m
=(n+m), by the induction hypothesis
m−1
=
n+m
n+m
+
m−1
m
=
n+m+1
...
Assume that the identity holds for
n+k
k
For
...
4
193
Pascal's triangle
Here, we rst used the induction hypothesis, then the generating rule
of Pascal's triangle (Proposition 4
...
We can spare ourselves an induction proof if we use
n+k
k
=
n+k
...
5
...
14 The
k th
element of row
p
is
p
k
=
p!
...
1 ≤ k ≤ p − 1, the
strictly less than p
...
k
is not a prime, then this property does not necessarily hold
...
37 we have n
n
...
10
5
= 252,
194
6
...
1 We use the notation as follows 1: the largest disk, 2: the second largest
disk, 3: the second smallest disk, 4: the smallest disk
...
it is denoted as
A
peg
B
peg
while peg
B
C
0
{ 1, 2, 3, 4 }
{}
{}
1
{ 1, 2, 3 }
{4}
{}
2
{ 1, 2 }
{4}
{3}
3
{ 1, 2 }
{}
{ 3, 4 }
4
{1}
{2}
{ 3, 4 }
5
{ 1, 4 }
{2}
{3}
6
{ 1, 4 }
{ 2, 3 }
{}
7
{1}
{ 2, 3, 4 }
{}
8
{}
{ 2, 3, 4 }
{1}
9
{}
{ 2, 3 }
{ 1, 4 }
10
{3}
{2}
{ 1, 4 }
11
{ 3, 4 }
{2}
{1}
12
{ 3, 4 }
{}
{ 1, 2 }
13
{3}
{4}
{ 1, 2 }
14
{}
{4}
{ 1, 2, 3 }
15
{}
{}
{ 1, 2, 3, 4 }
5
...
Let
gn
be a geometric progression with the
above mentioned property such that
gn = g0 rn
for some
g0
and
r
...
Solving the quadratic equation yields that
r = 2
or 5
...
De ne
Wn
as
6
...
We try to x
s
t
and
such that
W0 = a0
and
W1 = a1
...
Therefore
s + t = 0,
2s + 5t = 2
...
The solution of the above system of equations is
Hence
5
...
3
3
be a geometric progression satisfying the same recurrence rela-
an
such that
gn = g0 rn
for some
g0
and
r
...
That is,
r ∈ { 1, 3 }
...
The additional conditions imply that
W0 = a0 = 1,
W1 = a1 = 13
...
We get the solution
s = −5, t = 6
...
an
is
196
SOLUTIONS
5
...
We de ne
for some
g0
and
r,
gn = g0 r n
which is a geometric progression
...
It is a cubic polynomial
...
If there is an
integral root, then it divides 2
...
r
-2
0
1
0
2
(x + 1) · (x + 2),
0
-1
The cubic polynomial
r3 + 2r2 − r − 2
12
r3 + 2r2 − r − 2
can be written as
(x − 1) ·
that is, there are three integral roots
...
The corresponding system of linear equations is
s + t + u = 0,
−2s − t + u = 1,
4s + t + u = 2
...
We eliminate
It is easy to see that
an
is
s
3s = 2
...
3
u = 5/6 and t = −3/2
...
3
2
6
6
...
5 The solution is similar to the previous one, so we only provide some
details of the computation
...
r
r3 − 6r2 + 11r − 6
−6
−504
−3
−120
−2
−60
−1
−24
1
0
2
0
3
0
6
60
The three roots of the equation are 1, 2 and 3
...
Wn = s · 1n + t ·
The initial values should be equal as well, hence
s + t + u = 0,
s + 2t + 3u = 0,
s + 4t + 9u = 1
...
Therefore
u = 1/2, t = −1
and
s = 1/2
...
2
2
5
...
Following the
method we described we get a quadratic polynomial
r2 − 4r + 4 = (r − 2)2
...
That is,
Wn = s · 2n + tn · 2n
...
It is clear that
s = −1
and
t = 1
...
5
...
There are 6 possible integral roots, the divisors of 9, that is,
r
r3 − 5r2 + 3r + 9
−9
−1152
−3
−72
−1
0
1
8
3
0
9
{ ±9, ±3, ±1 }
...
Dividing the polynomial
r3 −5r2 +3r +9 by (r +1)·(r −3) we get r −3 and the remainder
is 0
...
There is a double root, so
Wn
is de ned as
s · (−1)n + t · 3n + un · 3n
...
5
199
Recurrence sequences
Substituting
n = 0, 1, 2
yields
s + t = 3,
−s + 3t + 3u = 4,
s + 9t + 18u = 29
...
So we have the solution
for
an
s = 2, t = 1
and
u = 1
...
5
...
u1 = 5
...
If there is such a recurrence, then the cor-
and
recurrence satis ed
responding quadratic polynomial is
√
5−3 5
r−
2
·
√
5+3 5
r−
2
= r2 − 5r − 5
...
Now we have that
un
is an integer for all
n
and
un
is a multiple of 5 if
n ≥ 1
...
9 We have a sequence
un = (4 −
√
3)n + (4 +
√
3)n ,
n ≥ 0
...
The quadratic polynomial
r−4+
√
2 · r−4−
√
2 = r2 − 8r + 14
is the polynomial corresponding to the appropriate recurrence relation
...
n ≥ 2
...
5
Recurrence sequences
201
Table 6
...
202
SOLUTIONS
Table 6
...
Anne Bonney
Black Bellamy
Calico Jack
4
1
2
0
5
2
0
1
6
3
2
2
3
1
3
1
4
2
0
4
3
1
1
5
0
2
5
2
3
2
2
1
4
0
3
4
2
2
3
1
3
3
1
2
4
1
1
12
1
11
1
66
10
1
55
9
1
220
45
8
1
165
36
7
1
495
120
28
6
1
330
84
21
5
1
792
210
56
15
4
1
462
126
35
10
3
1
924
252
70
20
6
2
1
462
126
35
10
3
1
792
210
56
15
4
1
330
84
21
5
1
495
120
28
6
1
165
36
7
1
220
45
8
1
55
9
1
66
10
1
11
1
12
1
1
1
6
...
5: First twelve rows of Pascal's triangle
Title: Colllege Discrete Mathematics
Description: A lecture note by Hovart Gabor. It is gonna help you alot.
Description: A lecture note by Hovart Gabor. It is gonna help you alot.