CMPS 211 Homework Assignment 7, Fall 2014
American University of Beirut · Discrete Structures · 2 pages
More CMPS 211 files
- Homework 3 with Solution · Spring 2016Homework · with solutionView
- Homework 6 with Solution · Spring 2016Homework · with solutionView
- Homework 1 with Solution · Spring 2016Homework · with solutionView
- Homework 4 with Solution · Spring 2016Homework · with solutionView
- Homework 5 with Solution · Spring 2016Homework · with solutionView
- Homework 1 · Fall 2015HomeworkView
- Homework 3 · Fall 2015HomeworkView
- Homework 1 Solution · Fall 2015Homework · with solutionView
Show the text of this homework
American
University
of
Beirut
Department
of
Computer
Science
CMPS
211
–
Discrete
Mathematics
–
Spring
13/14
Please solve the following exercises and submit BEFORE 9:00 am of
Monday 31st, March.
Exercise 1
(10 points)
a) Find
a
formula
for
1
2 + 1
4 + 1
8 + ⋯ + 1
2!
by
examining
the
values
of
this
expression
for
small
values
of
n.
b) Prove
the
formula
you
conjectured
in
part
(a).
Exercise 2
(10 points)
Prove that 6 divides n3 − n whenever n is a nonnegative integer.
Exercise 3
(10 points)
What is wrong with this “proof”?
“Theorem” For every positive integer n,
𝑖 =
!!!
!
!
!
.
!
!!!
Then
𝑖 = (
𝑖) + 𝑘 + 1 .
!
!!!
!!!
!!!
By this inductive hypothesis,
𝑖 =
!!!
!
!
!
+ 𝑘 +
!!!
!!!
1 =
!!!!!!
!
!
+ 𝑘 + 1 =
!!!!!!!
!
!
=
!!!
!
!
!
=
!!! !!
!
!
!
, completing the inductive step.
Exercise 4
(10 points)
Suppose that m and n are positive integers with m > n and f is a function from {1,2,...,m}
to {1,2,...,n}. Use mathematical induction on the variable n to show that f is not one-to-
one.
American
University
of
Beirut
Department
of
Computer
Science
CMPS
211
–
Discrete
Mathematics
–
Spring
13/14
Exercise 5
(20 points)
a) Determine which amounts of postage can be formed using just 4-cent and 7-cent
stamps.
b) Prove your answer to (a) using the principle of mathematical induction. Be sure to
state explicitly your inductive hypothesis in the inductive step.
c) Prove your answer to (a) using strong induction. How does the inductive hypothesis in
this proof differ from that in the inductive hypothesis for a proof using mathematical
induction?
Exercise 6
(10 points)
Use strong induction to show that every positive integer n can be written as a sum of
distinct powers of two, that is, as a sum of a subset of the integers 20 =1,21 =2,22 =4, and
so on. [Hint: For the inductive step, separately consider the case where k + 1 is even and
where it is odd. When it is even, note that (k + 1)/2 is an integer.]
Exercise 7
(10 points)
Prove using induction that 2𝑛! − 10𝑛 + 4 is non negative whenever 𝑛 is an integer and
𝑛 ≥ 5.
Exercise 8
(10 points)
Prove using induction that if 𝐴!, 𝐴! … 𝐴! and 𝐵 are sets then
(A1∩A2∩···∩An)∪B = (A1∪B)∩(A2∪B)∩···∩(An∪B).
Exercise 9
(10 points)
Use mathematical induction to prove that 9 divides n3 + (n + 1)3 + (n + 2)3 whenever n
is a nonnegative integer.