Reasoning: An Introduction to Logic, Sets, and Functions

1.

1. Prove by induction that, for n ≥ 3, the sum of the interior angles of a convex polygon of n vertices is (n – 2)⋅π. Recall that a convex polygon is a polygon every one of whose interior angles is less than π (180°).

Consider:

(A) (B)

(A) is convex. (B) isn’t, because of the angle labeled λ. It is an inside angle, but it is larger than 180°.

The first step in writing our proof should be a clear articulation of P(n). Write one.

The next step is the base case. What value of n should be used for the base case?

Now write your proof that P holds of the base case.

Now write your proof of the inductive step. You must prove:

For n ≥ 3, if P(n) then P(n+1).

2.

Prove that, for n ≥ 1, \((\sum_{i = 1}^{n}{\ (4i - 3)) = n(2n - 1)}\text{.}\)

Start by writing an explicit statement of P(n).

Base case. Prove it.

Induction step: Write out the specific claim that we must prove.

Now write out the proof.

3.

Prove that, for n ≥ 1, the product of any n odd integers is odd.

We need to start by writing an explicit statement of P(n). Before we can do that, we need to define a notation for products. We’ll use this:

\(\prod_{i = 1}^{n}{f(i)}\) is the product, as i goes from 1 to n, of f(i).

Π is to multiplication what Σ is to addition.

So let oi be the ith odd number in some arbitrary list of odd numbers. (Note that they don’t have to come in order: 1, 3, 5, … . Our claim applies to any n odd numbers.) Then:

\(\prod_{i = 1}^{n}o_{i}\) is the product of the n odd numbers in the given list.

Using this notation, write a definition of P(n).

Base case. Prove it.

Induction step: Write out the specific claim that we must prove.

Write out the proof of the inductive step.

4.

This problem is interesting, but harder than most of the ones we’ve done. We suggest that you try it, but do not get worried if you’re not sure you’ve got it.

Define the harmonic numbers hi, for i ≥ 1 as:

hi = \(1 + \frac{1}{2} + \ \frac{1}{3} + \ldots + \ \frac{1}{i}\)

Or, using summation notation, we can say:

hi = \(\sum_{j = 1}^{i}\left( \frac{1}{j} \right)\)

These numbers have been studied for hundreds of years, as has the infinite harmonic series:

\(1 + \frac{1}{2} + \ \frac{1}{3} + \frac{1}{4} + \ \frac{1}{5} + \ldots\)

The harmonic series does not converge to any fixed value. As i grows, so does hi, although it does grow very slowly. In this problem, we’ll use mathematical induction to prove that this is so. To do that, we’ll prove a claim about the harmonic numbers hk, where k is a power of two. Specifically:

For any integer n ≥ 0, \(h_{2^{n}\ }\)≥ 1 + \(\frac{n}{2}\)

First, you may want to convince yourself that this claim is believable. Write out the values of \(h_{2^{0}}\text{,}\) \(h_{2^{1}}\text{,}\) and \(h_{2^{2}}\text{.}\)

Let n = 2. What is \(h_{2^{n}}\) (i.e., h4) to 2 decimal places?

To check our claim, what is 1 + \(\frac{n}{2}\) ? (n is still 2.)

So, at least in the case of n = 2, we have that \(h_{2^{n}\ }\)≥ 1 + \(\frac{n}{2}\text{.}\)

Now on to our proof. Write out an explicit statement of the proposition P that we are trying to prove.

Base case: Prove P(0).

Induction step: We need to prove:

(\(h_{2^{n}\ }\)≥ 1 + \(\frac{n}{2}\)) → (\(h_{2^{n + 1}\ }\)≥ 1 + \(\frac{n + 1}{2}\))

Write this proof.