# Discrete Structures Homework Assignment 2 Solutions

**Exercise 1** (10 points). Show that the sum of the
first n odd natural numbers is n^{2}.

**Solution** The proof is by induction. The induction
basis is trivial, the first odd natural

number is 1 so the sum is 1, and 1^{2} = 1 of course. Now assume that the sum of
the first k

odd numbers is k^{2}. The (k + 1)-st odd number is 2k + 1, and by the induction
hypothesis

the sum of the first k +1 odd numbers is k^{2} +2k+1. This is equal to (k +1)^{2}
and the claim

thus holds for k + 1. This completes the proof.

**Exercise 2 **(10 points). What’s wrong with the
following induction proof?

We prove that for any n ∈ N and any a ∈ R, a^{n} = 1. The
proof proceeds by

strong induction. For the induction basis, a^{0} = 1 and the claim holds. Assume

that the claim holds for all k up to n. Then

This proves the claim.

**Solution** In the very first induction step we are
assuming that the claim holds for n = 0

and need to prove correctness for n = 1. At that point the proof assumes that
the claim also

holds for n = −1, which was never proved and is not correct in general.

**Exercise 3 **(10 points). Prove by induction that,
for any set A, |2^{A}| = 2^{|A|}.

Solution The induction is on the cardinality. For the induction basis, any set
of cardinality

0 is the empty set; its power set is {ø}, so
. Assume the claim holds for n = k,

so for any set A such that |A| = k, |2^{A}| = 2^{|A|}. Any set A′ of k + 1 elements
can be seen as

a set A of k elements plus one new element e. A set S ∈ 2^{A′} either contains e
or not. Sets

that do not contain e are subsets of A and their number is 2^{|A|} by the
induction hypothesis.

For a set S ∈ 2^{A′} that contains e, consider S_{0} = S \ {e}. S_{0} ∈ 2^{A} and every
element of 2^{A}

can be uniquely obtained in this way. Thus the number of sets S ∈ 2^{A′} that
contain e is also

2^{|A|}. Together this implies that |2^{A′} | = 2×2^{|A|} = 2^{|A|+1} = 2^{|A′|}. This
concludes the induction

step and proves the claim.

**Exercise 4** (10 points). Prove Bernoulli’s
inequality: For any n ∈ N and r ∈ R, such that

r > −1,

(1 + r)^{n} ≥ 1 + rn.

**Solution **By induction on n. For the induction
basis, n = 0 and (1 + r)^{0} ≥ 1 + r0 since

1 ≥ 1. Assume that the claim holds for n = k, so (1 + r)^{k} ≥ 1 + rk. We need to
prove the

inequality to k + 1. The induction hypothesis implies

(1 + r)^{k+1} ≥ (1 + rk)(1 + r) = 1 + rk + r + r^{2}k ≥ 1 + rk
+ r = 1 + r(k + 1)

The first inequality follows from the assumption 1 + r ≥
0, which allows us to multiply the

inequality by 1 + r without changing the sign. The second inequality follows
since r^{2}k ≥ 0.

This proves the induction step and concludes the proof.

**Exercise 5 **(10 points). Prove the strong induction
principle from the principle of induction.

Conclude that the two principles are equivalent. (That is, anything that can be
derived from

one, can also be derived from the other.)

**Solution **Given a set A of positive integers, assume
the conditions for the strong induction

principle:

• 1 ∈ A. (1)

• If {1, 2, . . . , k} ⊆ A then k + 1 ∈ A.
(2)

hold for the set A. We must show that A = N^{+}, and we will do this by ordinary
induction.

Let P(n) be the following proposition:

“{1, 2, . . . , n} ⊆ A.”

For the base case, P(1) follows trivially from (1). Now
assume P(n) holds, and consider

P(n+1). From our induction hypothesis and (2), n+1 ∈ A, or in other words P(n)
implies

that {1, 2, . . . , n + 1} ⊆ A, which means P(n + 1)
is true. By the induction principle, P(n)

holds for all positive integers n, so N^{+} ⊆ A. But A
is a set of positive integers, so A = N^{+}.

This proves the result.

The other direction (proving the induction principle from
the principle of strong induc-

tion) is similar but easier.

**Exercise 6 **(10 points). Suppose f(i, j) is a
function of i and j, and n ∈ N^{+}. Prove or give

a counterexample:

If the sums are replaced with products, does your conclusion change?

**Solution **They are indeed equal, as we’ll show by
induction on n. For the base case, n = 1

and both sides of the equation are f (1, 1), so they’re equal. Assume the claim
holds for

n = k. For n = k + 1, the left hand side is

The last (single) sum is obtained by separating the case i = k + 1 from the
double sum.

Also, the right hand side is

Note that the second sum in the second line evaluates to 0 because it has no
terms: the

starting value i = k + 1 is greater than the ending value i = k.

By our induction hypothesis,
so the left and

right hand sides are equal in the case n = k + 1 and the claim holds. This
proves the result

by induction.

If the sums are replaced with products, a completely
analogous proof is possible (we just

replace with
and + with ×). So the result holds in this
case too.

**Exercise 7 **(20 points). Many roots are irrational:

(a) Prove that ,
, and are
irrational. (Hint: For , use the fact that
every

integer is of the form 3n, 3n + 1, or 3n + 2.) Why doesn’t the same proof
technique

imply that is irrational?

(b) Prove that +
and +
are irrational.

Solution

(a) Let’s start with the proof that is
irrational. Following the proof that is
irrational

in the notes, we start by assuming is
actually a rational number p/q, where p and q

are integers with no common divisor and q ≠ 0, and show this leads to a
contradiction.

Squaring,

Now (from the hint) every integer is of the form 3n, 3n +
1 or 3n + 2, and the squares

in the three cases are 9n^{2}, 9n^{2} + 6n + 1 and 9n^{2} + 12n + 4. The first is
divisible by

3 and the second and third leave a remainder of 1 when divided by 3. So a
perfect

square is a multiple of 3 if and only if its square root is divisible by 3. In
other words,

p must be divisible by 3, say p = 3k for some integer k. But then

9k^{2} = 3q^{2}

or q^{2} = 3k^{2}

and by the same argument, q must also be divisible by 3.
This contradicts our assump-

tion that p and q have no common divisor , and so
must, in fact, be irrational.

Identical proofs work for and
once we have proved that a number is
divisible

by 5 if and only if its square is divisible by 5, and likewise for 6.

This technique does not work for
because an integer of the form 4n + 2 (which
is

not divisible by 4) has the square 16n^{2} + 16n + 4 (which is divisible by 4). So
our

“if and only if” condition cannot be proved. Of course, we know that
= 2 is very

rational indeed.

(b) For +,
we square to obtain If this was a rational

number p/q, we would have = (p − 5q)/2q,
which is a rational number. But we’ve

proved in the first part that is irrational,
which proves the result by contradiction.

For + ,
the same method works , only we use the fact that
is irrational.

**Exercise 8 **(20 points). Consider n lines in the
plane so that no two are parallel and no

three intersect in a common point. What is the number of regions into which
these lines

partition the plane? Prove.

**Solution** The answer must be some function of n, which we’ll denote by F(n). We
can

consider putting down the lines one after the other on the plane (in any
arbitrary order ),

with the total number of regions increasing at each step. After putting the
first n − 1 lines

we have F(n − 1) regions. When we draw the nth line, we know it must intersect
all of the

other n−1 lines since no two lines are parallel. Since no three share an
intersection, this new

line has exactly n−1 intersection points with the other lines. These
intersections mean that

the new line goes through n of the existing regions of the plane (at every
intersection point,

the line leaves one existing region and enters another, and doesn’t change
regions before the

first intersection, after the last, or between any two intersections). The new
line divides each

region through which it passes into two, so n new regions are created. So

F(n) = F(n − 1) + n

It’s easy enough to expand this sum as:

(recall the sum of the first n natural numbers)

Now when there are no lines, there is only one region (the
whole plane), so F(0) = 1. So

This, however, is not a formal proof! Rather, that was an
outline of the kind of reasoning

you could use to realize that the right answer is n(n + 1)/2 + 1. The actual
proof proceeds

by induction.

For the basis, with 0 lines there is 1 region so the claim
holds. Now assume it holds

for n = k. When we draw the (k + 1)-st line, we know it must intersect all of
the other

k lines since no lines are parallel. Since no three share an intersection, this
new line has

exactly k intersection points with the other lines. These intersections mean
that the new

line goes through k + 1 of the existing regions of the plane and divides each of
those in two,

such that k + 1 new regions are created. Adding this to the existing tally gives
a total of

k+1+k(k+1)/2+1 = (k^{2}+3k+2)/2+1 = (k+1)(k+2)/2+1 = (k+1)((k+1)+1)/2+1

lines, so the claim holds for k + 1. This completes the proof by induction.

Prev | Next |