Homework Assignment 1
CSCI 2405
Spring 2020
Section 001

Due: 2/5

  1. Let P(n) be the statement

    13 + 23 + … + n3 = (½n(n+1))2

    for a positive integer n. The goal is to show that P(n) is true for every positive integer n using Peano Induction.

    1. What is statement P (1)?

       

    2. Show that P (1) is true.

       

    3. What is the induction hypothesis of a proof using Peano Induction that P (n) is true for all positive integers n? Write it out using the definition of P (n).

       

    4. What do you need to prove in the inductive step to prove that P (n) is true for all n?

       

    5. Complete the inductive step.

       

  2. Let P (n) be the statement that n! < nn, where n is an integer that is greater than 1.

    1. What is statement P (2)?

       

    2. Show that P (2) is true.

       

    3. What is the induction hypothesis of a proof using Peano Induction that P (n) is true for all integers n ≥ 2? Write it out using the definition of P (n).

       

    4. What do you need to prove in the inductive step to prove that P (n) is true for all n?

       

    5. Complete the inductive step.

       

    1. Find a formula for

      1/(1⋅2) + 1/(2⋅3) + 1/(3⋅4) + … 1/(n(n+1))

      by examining the values of that expression for small values of n.

       

    2. Prove that the formula you derived in step (a) is true for all nonnegative integers n.

       

  4. Prove that 3 divides n3 + 2n for all positive integers n.

     

  5. Prove that, for every positive integer n,

    ∑nk=1k2k = (n − 1)2n+1 + 2
     

  6. What is wrong with the following "proof"?

    Theorem. For every positive integer n, ∑ni=1i = ½(n + ½)2

    Proof. By Peano Induction on n.

    Basis step. The formula holds for n = 1.

    Inductive step. Suppose that

    ∑ni=1 i = ½ (n + ½ )2.

    But

    ∑n+1i=1 i =  (∑ni=1 i) + (n + 1).

    So, by the induction hypothesis,

    ∑n+1i=1i  =  ½ (n + ½ )2 + n + 1
     =  ½ (n2 + n + ¼) + n + 1
     =  ½ (n2 + 3n + 9/4)
     =  ½ (n + 3/2)2
     =  ½ ((n + 1) + ½ )2

    which completes the inductive step.

     

  7. Suppose there are n people in a group, each aware of a scandal nobody else in the group knows about. These people communicate by telephone. When two people in the group talk, they share information about all scandals each knows about. For example, after the first call, two people each know about two scandals. The gossip problem asks for G (n), the minimum number of telephone calls that are needed for all n people to learn about all of the scandals.

    Show, using Peano Induction, that G (n) ≤ 2n − 4, for all n ≥ 4. (Hint. In the inductive step have a person call a particular person at the start and end.)

     

  8. Let P (n) be the statement that a postage of n cents can be formed using just 4-cent stamps and 7-cent stamps. The goal is to show, using strong induction, that P (n) is true for all integers n ≥ 18.

    1. Show that P (18), P (19), P (20) and P (21) are all true.

       

    2. What is the induction hypothesis of a proof by strong induction that P (n) is true for all integers n ≥ 18?

       

    3. What do you need to prove in the inductive step?

       

    4. Complete a proof of the inductive step for k ≥ 21.

       

    1. Determine which amounts of postage that can be formed using just 3-cent and 10-cent stamps.

       

    2. Prove your answer to (a) using Peano Induction. Be sure to state explicitly your basis cases, the induction hypothesis and the inductive step.

       

    3. Prove your answer to (a) using strong induction. State explicitly your basis steps, the induction hypothesis and the induction step.

       

  10. Suppose you begin with a pile of n stones. You complete a sequence of steps. As you go, you write down a sequence of numbers. At each step, you select a pile of stones that has k > 1 stones in it, split that pile into two smaller piles, having r and s stones in them, and add the product rs to the sequence of numbers. You keep going until all of the piles have only one stone.

    Show that, no matter how you do the steps, the sum of the numbers in the sequence when you are done is n(n − 1)/2.

     

  11. What is wrong with the following "proof" by strong induction?

    Theorem. For every nonnegative integer n, 5n = 0.

    Proof.

    Basis step. 5⋅0 = 0

    Inductive step. Suppose that 5j = 0 for all nonnegative integers j where 0 ≤ j ≤ k. Choose i and j so that k + 1 = i + j, where i and j are natural numbers that are less than k + 1. By the induction hypothesis, 5(k+1) = 5(i + j) = 5i + 5j = 0 + 0 = 0.

     

  12. Find f (2), f (3), f (4) and f (5) if f  is defined recursively by f (0) = f (1) = 1 and, for n = 1, 2, …,

    1. f (n + 1) = f (n) − f (n − 1)

       

    2. f (n + 1) = f (n)⋅f (n − 1)

       

    3. f (n + 1) = f (n)2 + f (n − 1)3

       

  13. Let S be the set of ordered pairs of nonnegative integers defined recursively as follows.

    Basis. (0, 0) ∈ S

    Recursive step. If (a, b) ∈ S then (a + 2, b + 3) ∈ S and (a + 3, b + 2) ∈ S.

    Use strong induction to show that, if (a, b) ∈ S then a + b is divisible by 5.