Math 241 Homework Assignment 5
1. Prove that for all natural numbers, n,
Solution
The proof is by induction on k with hypothesis
base case: To prove H(0),
induction step: Assume H(k). Now,
(expand)  
(IH)  
(multiply by 1 = 6/6)  
(add fractions)  
(factor (k + 1))  
(combine like terms) 

(factor 2k^2 + 7k + 6)  
(arithmetic) 
This completes the induction case and the proof of the problem.
2. Prove that for all natural numbers, n,
Solution
The proof is by induction on k with hypothesis
Recall that
base case:
induction step: AssumeNow,
(expand)  
(induction hypothesis)  
(rearrange sums)  
distribute (k + 1)!  
(simplify)  
(meaning of ‘!’)  
(as desired) 
This proves H(k + 1) and completes the induction.
3. Prove that for all natural numbers n, 6 evenly divides n^3 − n.
Solution
The proof is by induction on k ∈N with hypothesis “6 evenly devides n^3 − n”
Base Case (H[0]). 0^3 − 0 = 0, which is evenly divisible by 6.
Induction (H[k] > H[k + 1]). Assume that k^3 − k is evenly divisible by 6.
Now,
Expanding (k + 1)^3  
Combining like terms  
Distributing k  
Factoring k^2 + 3k + 2 
By Proposition A (below) this number is divisible by 3. And since at least
one
of k, k + 1, or k + 2 is an even number, it is also divisible by 2. That is,
k(k + 1)(k + 2) = 2 · 3 · q, for some q, and is therefore divisible by 6.
Proposition A. For all n ∈ N, n(n + 1)(n + 2) is divisible by 3.
Proof: by induction on n with hypothesis, 3p for some p.
Base Case: 0 · 1 · 2 = 0 = 3 · 0.
Induction Case: Assume k(k + 1)(k + 2) = 3p for some p.
(distributing over k + 3)  
(Induction Hypothesis)  
(distributing the 3) 
Comment: It is reasonable to say that this proposition is obvious and need not be proven.
4. Prove that for all natural numbers n > 4, 2^n > n^2.
Solution
The proof is by induction on k with hypothesis
base case: To prove H(5),
induction step: Assume 2^k > k^2. Now,
(induction hypothesis, used twice)  
The induction is finished once it is established that for any natural number
n > 4,
n^2 > 2n + 1. This fact is proved in the lemma below.
lemma For all n > 3,n^2 > 2n + 1.
proof: The proof is by induction on k with hypothesis k^2 >2k +1 .
base case:
induction step: Assume k^2 > 2k + 1, k > 3. Then
(induction hypothesis)  
(k > 1)  
(arithmetic)  
(arithmetic) 
This completes the induction and the proof of the lemma.
The proof of the lemma completes the proof of the problem.
5. Hint: Solving this problem requires more than a straightforward algebraic
derivation.
Think outside the box.
Prove that for all natural numbers n,
Solution
Solution Needed
6. Recall that the choose function, defined
is the number of different ways to choose r objects from a set
of s objects. Prove
that for all n ∈N,
Solution
Solution needed.
7. For n ∈N, let Q, P_{1}, P_{2}, . . . , P_{n} be propositions. Prove the following:
Solution
Solution Needed
8. Consider the program
Use Theorem 4.2 and invariant assertion
to prove that this program computes the quotient and remainder of A and B.
Solution
According to Theorem 4.2, it we can show that assertion I
is true when P first
reaches and that executing the loop body
leaves I true, then when P ends, I
will be true and the test “r≥B” will be false.
Thus, there are three things to prove: Note: Blue
comments need not be included
because they are implied by the use of Theorem 4.2
1. Initialization (Base Case):
Since we have just assigned 0 to q and A to r we have
qB + r = 0 · B + A = A.
2. Invariance (Induction Case):
The loop body computes new values for program variablesand
(valid because r≥B). So we have
(substituting for r' and q')  
(simplifying)  
(assumption) 
as desired.
3. Termination: It remains to show thatimplies
the postcon
dition,But in this case the two formulas are
identical, so the implication is tautologically valid.
9. Supplemental Problem Comment: This is neither a calculus question nor
a logic puzzle
At last! You’ve gotten out of the dorms and into an apartment. Life can
begin.
You get moved in and a few days later are looking for a brownie pan. When
you open the cabinet door, you see a 12inch by 12inch pan, just perfect for
your cooking needs. That’s the good news.
Unfortunately, there are four cockroaches in the pan, one at each corner. Now
you may not have known this, but cockroaches are very amorous creatures,
and will always move directly toward the object of their affection. Each of the
four in your pan is attracted to the one in the adjacent corner, going
counterclockwise.
So all four cockroaches simultaneously start walking toward the one
that attracts them. As a result, they start spiraling toward the center of the
pan (See the diagram below).
Question: How far will the cockroaches travel?
Solution
Each cockroach travels the length of one side of the square pan, 12 inches in
the
problem as stated.
To gain the necessary insight, you have to look at the problem from the (any)
cockroach’s point of view. From that perspective,
(a) the cockroach is moving directly toward its target, perpendicular to the
(tangent) of the target’s path of travel. We know from geometry that this
is the shortest path it can take.
(b) We also know (from common sense), that the total distance a cockroach
travels is d = α + β, where
α is the distance it has already traveled and
β is how far it has yet to go. When the cockroach
takes a step, α and β
change by the same distance s, but d = (α + s) + (β
− s) is is unchanged
These two properties are invariant—they do not change throughout cockroach’s
trip from the corner of the pan to its destination. From the cockroach’s point
of
view, it is the pan that is turning, not itself. So by (a), above, it is
invariantly
traveling along the shortest path to its destination; and the total distance (b)
is
invariant also. Initially, d = 12 inches, so that is how far it travels.
Remark: The Comment at the beginning of the problem says that you don’t
need calculus to solve the problem, but this is not entirely true. What
you do need is a grasp of the underlying concepts of calculus. The
solution is only valid in the limit. The true distance is some multiple
of the number of discrete steps taken by the cockroach. Twelve
inches is the limit of that number as the length of each stride becomes
infinitesimal.^{1}
One can reasonably argue (as I suspect your Calculus instructor
would) that the “solution” given above needs to be verifyed by a
rigorous mathematical formulation by which the limit value can be
calculated. It is merely an idea about how to approach the proof.
It is worthwhile to set up that formulation. One the other hand, if
you were to write a program to approximate the limit, discovering
the problem’s invariants key to the computing the answer.
End Remark
^{1}Here’s an interesting fact about cockroaches. Most insects have two forms of
locomotion
or gaits. One is walking in which two outer legs and to opposite middle leg work
in unison.
The three legs act as a tripod, and the two tripods alternate, propelling the
the insect forward
in a bipedal manner. The other gait is metachronal: the legs on either side
thrust in sequence,
resulting in a “wave” traversing from front to back, like the legs of a
centipede or caterpillar.
Cockroaches are unusual insects in that they have three gaits. In flight, a
cockroach can
literally run on its two hind legs, keeping the other four raised off the
ground.