Java Reference
In-Depth Information
2.16 Write a recursive algorithm to print all of the subsets for the set of the first n
positive integers.
2.17 The Largest Common Factor (LCF) for two positive integers n and m is
the largest integer that divides both n and m evenly. LCF(n, m) is at least
one, and at most m, assuming that n m. Over two thousand years ago,
Euclid provided an efficient algorithm based on the observation that, when
n mod m 6= 0, LCF(n, m) = LCF(m, n mod m). Use this fact to write two
algorithms to find the LCF for two positive integers. The first version should
compute the value iteratively. The second version should compute the value
using recursion.
2.18 Prove by contradiction that the number of primes is infinite.
2.19
(a) Use induction to show that n
2
n is always even.
(b) Give a direct proof in one or two sentences that n
2
n is always even.
(c) Show that n
3
n is always divisible by three.
(d) Is n
5
n
aways divisible by 5? Explain your answer.
2.20 Prove that
p
2 is irrational.
2.21 Explain why
n
X
n
X
n
X
i =
(ni + 1) =
(ni):
i=1
i=1
i=0
2.22 Prove Equation 2.2 using mathematical induction.
2.23 Prove Equation 2.6 using mathematical induction.
2.24 Prove Equation 2.7 using mathematical induction.
2.25 Find a closed-form solution and prove (using induction) that your solution is
correct for the summation
X
n
3
i
:
i=1
2.26 Prove that the sum of the first n even numbers is n
2
+ n
(a) by assuming that the sum of the first n odd numbers is n
2
.
(b) by mathematical induction.
2.27 Give a closed-form formula for the summation
P
i=a
i where a is an integer
between 1 and n.
2.28 Prove that Fib(n) < (
5
3
)
n
.
2.29 Prove, for n 1, that
X
n
i
3
=
n
2
(n + 1)
2
4
:
i=1
2.30 The following theorem is called the Pigeonhole Principle.
Theorem2.10
When n + 1 pigeons roost in n holes, there must be some
hole containing at least two pigeons.
