COMP 280 Assignment 8

The following totals to 75 points, plus 10 points extra credit.

1. (10 points) Rosen 6th ed. 4.2 #14

   Suppose you begin with a pile of n stones and split this pile into n piles of one stone each by successively splitting a pile of stones into two smaller piles. Each time you split a pile you multiply the number of stones in each of the two smaller piles you form, so that if these piles have r and s stones in them, respectively, you compute rs. Show that no matter how you split the piles, the sum of the products computed at each step equals n(n-1)/2.

2. (10 points extra credit) Rosen 6th ed. 4.2 #18

   Use strong induction to show that when a convex polygon P with consecutive vertices v₁, v₂, …, v_n is triangulated into n-2 triangles, the n-2 triangles can be numbered 1, 2, …, n-2 so that v_i is a vertex of triangle i for i = 1, 2, …, n-2.

3. (10 points)

   Show that anything provable by strong induction is also provable by weak induction. I.e., assume we know how to prove ∀n.P(n) by strong induction. Then provide a Q() such that ∀n.Q(n) is an equivalent statement and can be proved using weak induction.

4. (20 points) Rosen 6th ed. 4.2 #22ab

   Let P(n) be the statement that when nonintersecting diagonals are drawn inside a convex polygon with n sides, at least two vertices of the polygon are not endpoints of any of these diagonals.

   1. Show that when we attempt to prove P(n) for all integers n with n≥3 using strong induction, the inductive step does not go through.
   2. Show that we can prove that P(n) is true for all integers n with n≥3 by proving by strong induction the strong assertion Q(n), for n≥4, where Q(n) states that whenever nonintersecting diagonals are drawn inside a convex polygon with n sides, at least two non-adjacent vertices are not endpoints of any of these diagonals.

5. (10 points) Rosen 6th ed. 4.3 #30

   Prove that in a bit string, the substring 01 occurs at most one more time than the substring 10.

   E.g., in the bit string 0101, the substring 01 occurs twice, and the substring 10 occurs once.

6. (10 points) Rosen 6th ed. 4.3 #36

   The reversal of a string is the string consisting of the symbols of the string in reverse order. The reversal of the string w is denoted by w^R

   Use structural induction to prove that (w₁w₂)^R = w₂^Rw₁^R.

   E.g., when w₁=abc and w₂=de, this implies that (abcde)^R = (de)^R(abc)^R.

7. (15 points) Rosen 6th ed. 4.3 #46

   Use generalized induction as was done in Example 15 to show that if a_m,n is defined recursively by a_1,1 = 5 and a_m,n = a_m-1,n+2 if n=1 and m>1, and a_m,n-1+2 if n>1, then a_m,n = 2(m+n)+1 for all (m,n) ∈ ℤ⁺×ℤ⁺.