HW5 Proofs and Induction

In this assignment,

You will work with recursively defined sets and functions and prove properties about them, practicing induction and other proof strategies.

Instructions and academic integrity reminders for all homework assignments in CSE20 this quarter are on the class website and on the hw1-definitions-and-notations assignment.

You will submit this assignment via Gradescope (https://www.gradescope.com) in the assignment called “hw5-proofs-and-induction”.

Resources: To review the topics you are working with for this assignment, see the class material from Weeks 5 through 7. We will post frequently asked questions and our answers to them in a pinned Piazza post.

In your proofs and disproofs of statements below, justify each step by reference to a component of the following proof strategies we have discussed so far, and/or to relevant definitions and calculations.

• A counterexample can be used to prove that \(\forall x P(x)\) is false.

• A witness can be used to prove that \(\exists x P(x)\) is true.

• Proof of universal by exhaustion: To prove that \(\forall x \, P(x)\) is true when \(P\) has a finite domain, evaluate the predicate at each domain element to confirm that it is always T.

• Proof by universal generalization: To prove that \(\forall x \, P(x)\) is true, we can take an arbitrary element \(e\) from the domain and show that \(P(e)\) is true, without making any assumptions about \(e\) other than that it comes from the domain.

• To prove that \(\exists x P(x)\) is false, write the universal statement that is logically equivalent to its negation and then prove it true using universal generalization.

• Strategies for conjunction: To prove that \(p \land q\) is true, have two subgoals: subgoal (1) prove \(p\) is true; and, subgoal (2) prove \(q\) is true. To prove that \(p \land q\) is false, it’s enough to prove that \(p\) is false. To prove that \(p \land q\) is false, it’s enough to prove that \(q\) is false.

• Proof of Conditional by Direct Proof: To prove that the implication \(p \to q\) is true, we can assume \(p\) is true and use that assumption to show \(q\) is true.

• Proof of Conditional by Contrapositive Proof: To prove that the implication \(p \to q\) is true, we can assume \(\neg q\) is true and use that assumption to show \(\neg p\) is true.

• Proof of disjuction using equivalent conditional: To prove that the disjunction \(p \lor q\) is true, we can rewrite it equivalently as \(\lnot p \to q\) and then use direct proof or contrapositive proof.

• Proof by Cases: To prove \(q\) when we know \(p_1 \lor p_2\), show that \(p_1 \to q\) and \(p_2 \to q\).

• Proof by Structural Induction: To prove that \(\forall x \in X \, P(x)\) where \(X\) is a recursively defined set, prove two cases:

  Basis Step:	Show the statement holds for elements specified in the basis step of the definition.
  Recursive Step:	Show that if the statement is true for each of the elements used to construct new elements in the recursive step of the definition, the result holds for these new elements.

• Proof by Mathematical Induction: To prove a universal quantification over the set of all integers greater than or equal to some base integer \(b\):

  Basis Step:	Show the statement holds for \(b\).
  Recursive Step:	Consider an arbitrary integer \(n\) greater than or equal to \(b\), assume (as the induction hypothesis) that the property holds for \(n\), and use this and other facts to prove that the property holds for \(n+1\).

• Proof by Strong Induction To prove that a universal quantification over the set of all integers greater than or equal to some base integer \(b\) holds, pick a fixed nonnegative integer \(j\) and then:

  Basis Step:	Show the statement holds for \(b\), \(b+1\), …, \(b+j\).
  Recursive Step:	Consider an arbitrary integer \(n\) greater than or equal to \(b+j\), assume (as the strong induction hypothesis) that the property holds for each of \(b\), \(b+1\), …, \(n\), and use this and other facts to prove that the property holds for \(n+1\).

• Proof by Contradiction

  To prove that a statement \(p\) is true, pick another statement \(r\) and once we show that \(\neg p \to (r \wedge \neg r)\) then we can conclude that \(p\) is true.

  Informally The statement we care about can’t possibly be false, so it must be true.

Assigned questions

1. Recall the definitions from class about factoring and divisibility: when \(a\) and \(b\) are integers and \(a\) is nonzero, \(a\) divides \(b\) means there is an integer \(c\) such that \(b = ac\) . In this case, we say \(a\) is a factor of \(b\), \(a\) is a divisor of \(b\), \(b\) is a multiple of \(a\), \(a | b\). We define the function \(PosFactors: \mathbb{Z}^+ \to \mathcal{P}(\mathbb{Z}^+)\) by \[PosFactors (n) = \{ x \in \mathbb{Z}^+ \mid x\text{ is a factor of } n\}\]

   ---

   Sample calculation that can be used as reference for the detail expected in your answer when working with this function:

   The function application \(PosFactors(4)\) evaluates to \[PosFactors (4) = \{ 1,2,4\}\] because the only possible positive factors of \(4\) are \(1,2,3,4\) (the positive integers less than or equal to \(4\)) and when we divide we get: \[\begin{aligned} 4 &= 4 \cdot 1 + 0 \qquad \text{so $4$ is a factor of $4$}\\ 4 &= 3 \cdot 1 + 1 \qquad \text{so $3$ is not a factor of $4$}\\ 4 &= 2 \cdot 2 + 0 \qquad \text{so $2$ is a factor of $4$}\\ 4 &= 1 \cdot 4 + 0 \qquad \text{so $1$ is a factor of $4$} \end{aligned}\]

   ---

   1. (Graded for correctness¹) Give a witness that proves the statement \[\exists x \in \mathbb{Z}^+ ~\forall y \in \mathbb{Z}^+ ~\left(~x \in PosFactors(y)~\right)\] Justify your choice of witness by explanations that include references to the relevant definitions.

   2. (Graded for correctness) Give a counterexample that disproves the statement \[\forall n \in \mathbb{Z}^+ ~\left(~ PosFactors(n) \subseteq PosFactors(n+1)~\right)\] Justify your choice of counterexample by explanations that include references to the relevant definitions.

   3. (Graded for fair effort completeness) Consider the following attempted proof.

      Attempted proof: For arbitrary integers \(a, b, c\), assume towards a direct proof that \((a+b) | c\). We need to show that \(a|c\) and \(b | c\). Let \(n\) be the integer \(c \text{\bf ~div~} (a+b)\). Since \((a+b) | c\), by definition of divides, \(n | c\) and \(n\) is an integer. Since \(c = 1 \cdot n \cdot (a+b)\), \((n \cdot (a+b) ) | c\). Rewriting by distributing multiplication over addition, we have \(na | c\) and \(nb | c\). Since \(a | na\) and \(na | c\), we have \(a | c\). Similarly, since \(b | nb\) and \(nb | c\), we have \(b | c\). Thus, we have proved both conjuncts and the proof is complete.

      Select the statement below that the attempted proof is trying to prove.

      1. \(\forall a \in \mathbb{Z}^+ ~\forall b \in \mathbb{Z}^+ ~\forall c \in \mathbb{Z} ~( ~( ~a|c ~\lor~b |c~) ~\to~ (a+b) |c~)\)

      2. \(\forall a \in \mathbb{Z}^+ ~\forall b \in \mathbb{Z}^+ ~\forall c \in \mathbb{Z} ~( ~( ~a|b ~\land~a |c~) ~\to~ a |(b+c)~)\)

      3. \(\forall a \in \mathbb{Z}^+ ~\forall b \in \mathbb{Z}^+ ~\forall c \in \mathbb{Z} ~(~ (a+b) | c ~\to ~( ~a|c ~\land~b |c~)~)\)

      Identify the first major error in the attempted proof and explain why it is incorrect.

      Next, disprove the statement the attempted proof was attempting to prove.

      Extra practice; not for credit: prove or disprove the other two statements.

2. In this question, we’ll consider the function which calculates the sum of the first \(n\) positive integers.

   1. (Graded for fair effort completeness²)

      Give a recursive definition of this function, including domain, codomain and both the basis step and recursive step of the rule. That is, fill in the blanks \[sumOfFirst: \underline{~~domain~~} \to \underline{~~codomain}\] given by \[\begin{aligned} &\textbf{Basis step}: \underline{\text{fill in basis step}} \\ &\textbf{Recursive step}: \underline{\text{fill in recursive step}} \end{aligned}\]

      Notation: Using summation, this function can be written \(sumOfFirst(n) = \sum_{i=1}^n i\).
      

   2. (Graded for fair effort completeness) It turns out that the value of this function can also be calculated explicitly (without recursion)³. You will prove this by completing the proof of the identity \[\forall n \in \mathbb{Z}^+ ~\left(~sumOfFirst(n) = \frac{n(n+1)}{2} \right)\]

      Fill in the missing parts of the proof of this statement:
      Proof: We proceed by mathematical induction on the set of positive integers.

      Basis Step: Choose \(n = 1\) as the basis step. Using the Basis Step in the recursive definiton of \(sumOfFirst\), \(sumOfFirst(1) = 1\). Plugging \(n\) into the RHS of the desired formula, \(\frac{1 (1+1)}{2} = \frac{2}{2} = 1\). Since LHS=RHS, the Basis step is complete.

      Recursive Step: Consider an arbitrary \(k \geq 1\). We assume (as the induction hypothesis) that fill in the blank here.

      We want to show that \(sumOfFirst(k+1) = \frac{(k + 1) \cdot ((k + 1) + 1)}{2}\).

      Fill in the rest of the proof here.
      

   3. (Graded for fair effort completeness) When calculating the runtime of an algorithm, nested for loops sometimes lead to program runtimes that involve the sum of the first \(n\) positive integers. To estimate the rate of growth of this runtime, it is useful to find an upper bound for this function in terms of a simpler function. Use the explicit formula from the earlier parts of this question and mathematical induction to prove \[\forall n \in \mathbb{Z}^+~ \left(~sumOfFirst(n) \leq n^2 \right)\]

3. Recall the definition of linked lists that we discussed in class.

   Define the function \(count\) which returns the number of occurrences of a datum in the list. Formally, \(count: L \times \mathbb{N} \to \mathbb{N}\), where \[\begin{aligned} \textbf{Basis Step:} \qquad &\textrm{If } m \in \mathbb{N},~~ count(~( [], m)~ ) = 0 \\ \textbf{Recursive Step:} \qquad &\textrm{If } l \in L\textrm{ and }n \in \mathbb{N} \textrm{ and }m \in \mathbb{N} \textrm{, then } \\ &count(~(~(n, l),m~)~ ) = \begin{cases} 1 + count(~(l,m)~) &\text{if $n=m$} \\ count(~(l,m)~) &\text{otherwise} \\ \end{cases} \end{aligned}\]

   A mystery function is defined by \(mystery : L \times \mathbb{N} \to L\), where

   \[\begin{aligned} \textbf{Basis Step:} \qquad &\textrm{If } m \in \mathbb{N},~~ mystery(~( [], m)~ ) = [] \\ \textbf{Recursive Step:} \qquad &\textrm{If } l \in L\textrm{ and }n \in \mathbb{N} \textrm{ and }m \in \mathbb{N} \textrm{, then } \\ &mystery(~(~(n, l),m~)~ ) = \begin{cases} l &\text{if $n=m$} \\ mystery(~(l,m)~) &\text{otherwise} \\ \end{cases} \end{aligned}\]

   1. (Graded for correctness) Prove that \[\forall m \in \mathbb{N}~ \exists l \in L ~\left( count(~(l,20)~) = m~ \right)\]

   2. (Graded for correctness) Give an example input \(x\) to the function such that \[mystery( ~(~ x ~,~ 2~) ~) = []\] For full credit, include all intermediate steps of the function application that justifies your choice of \(x\), with brief justifications for each.

   3. (Graded for correctness) Evaluate the function application \[mystery( ~(~ (2, (0, (2, []) ) ) ~,~ 2~) ~)\] For full credit, include all intermediate steps of the function application, with brief justifications for each.

   4. (Graded for fair effort completeness for English statements and correctness in use of syntax for symbolic statements) Describe the rule of the function \(mystery\) in English. Then, write a true statement that describes an invariant using both the functions \(mystery\) and \(count\). Express this invariant both symbolically and in English.