hw5-proofs-and-induction

CSE20S24

Due: 5/21/24 at 5pm (no penalty late submission until 8am next morning)

In this assignment, you will work with recursively defined sets and functions and prove properties about them, practicing induction and other proof strategies.

Relevant class material: Weeks 5,6,7.

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

For all HW assignments: These homework assignments may be done individually or in groups of up to 3 students. Please ensure your name(s) and PID(s) are clearly visible on the first page of your homework submission, start each question on a new page, and upload the PDF to Gradescope. If you’re working in a group, submit only one submission per group: one partner uploads the submission through their Gradescope account and then adds the other group member(s) to the Gradescope submission by selecting their name(s) in the “Add Group Members” dialog box. You will need to re-add your group member(s) every time you resubmit a new version of your assignment.

Each homework question will be graded either for correctness (including clear and precise explanations and justifications of all answers) or fair effort completeness. You may collaborate on “graded for correctness” questions only with CSE 20 students in your group; if your group has questions about a problem, you may ask in drop-in help hours or post a private post (visible only to the Instructors) on Piazza. For “graded for completeness” questions: collaboration is allowed with any CSE 20 students this quarter; if your group has questions about a problem, you may ask in drop-in help hours or post a public post on Piazza.

All submitted homework for this class must be typed. You can use a word processing editor if you like (Microsoft Word, Open Office, Notepad, Vim, Google Docs, etc.) but you might find it useful to take this opportunity to learn LaTeX. LaTeX is a markup language used widely in computer science and mathematics. The homework assignments are typed using LaTeX and you can use the source files as templates for typesetting your solutions.

Integrity reminders

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.

Assigned questions

  1. Mathematical and strong induction for properties of numbers.

    1. (Graded for completeness) 1 Consider each of the following statements and attempted proofs below. Pretend you are the TA/tutor for CSE 20 and grade each of these attempts. In particular, you should give each one a score out of \(5\) points and justify your decisions with specific, actionable, and justified feedback; your explanations should be convincing but brief. Here is the rubric2 you should use:

      5 points

      Induction proof includes correctly executed base case and recursive step (with induction hypothesis, IH, clearly and correctly defined and used). Uses clear and correct calculations and references to definitions in both steps, including using the IH, to conclude both.

      4 points

      Induction proof includes base case and recursive step (with induction hypothesis clearly and mostly correctly defined and used), where base case attempted but incomplete OR, incorrect base element chosen but valid proof made for chosen element, OR induction hypothesis incorrectly stated but correctly used.

      3 points

      Any one of the following: (1) Induction proof with correctly executed base case and recursive step that demonstrates connection between induction hypothesis and property being true for \(n+1\), some missing or incorrect logical glue; (2) Induction proof with missing base case and correctly executed recursive step.

      2 points

      Any one of the following: (1) Induction proof includes attempts at correct steps of an induction proof (base case, recursive step), with significant logical gaps and/or errors; (2) correctly executed base case with missing / incorrect recursive step,

      1 point

      Demonstrates knowledge of proof techniques (e.g. attempts some proof type other than induction, but uses some proof technique correctly) and/or structure of induction argument.

      1. Statement: “the sum of the first \(n\) positive odd integers is \(n^2\)"

        Attempted Proof:

        Base Case: \(n = 1\)
        First odd number is \(1\); \(1^2 = 1\). True.
        \((n + 1)^2 = n^2 + 2n + 1\)
        \(n^2\) is the sum of the first \(n\) odd numbers, and \(2n + 1\) is the next odd number in the sequence, therefore \((n + 1)^2 =\) the sum of the first \(n + 1\) odd numbers.

      2. Statement: “For every nonnegative integer \(n\), \(3 | n\)." (Recall that the \(\mid\) symbol is used to mean “divides” or “is a factor of”.)

        Attempted Proof:

        Attempted Proof: We proceed by strong mathematical induction.

        Basis step: Indeed, \(3 | 0\) because there is an integer, namely \(0\) such that \(0 = 3\cdot 0\).

        Induction step: Let \(k\) be arbitrary. Assume, as the strong induction hypothesis, that for all nonnegative integers \(j\) with \(0 \leq j \leq k\), that \(3 | j\). Write \(k+1 = m + n\), where \(m,n\) are integers less than \(k+1\). By the induction hypothesis, \(3 | m\) and \(3 | n\). That is, there are integers \(a,b\) such that \(m = 3a\) and \(n=3b\). Therefore, \(k+1 = (3a) + (3b) = 3 (a+b)\). We can choose \(a + b\), where we know \(a + b \in \mathbb{Z}\), to show that \(3 | (k+1)\), as required.

    2. (Graded for completeness) Decide whether each statement above is true or false, give correct and complete induction proofs for the true statement(s) and disprove by counterexample for the false statement(s).

  2. (Graded for correctness) Games and induction. The game of Nim-Var is a two-player game (which is a variant of Nim). At the start of the game, there are two piles, each containing \(n\) jelly beans (\(n\) is a positive integer). On a player’s turn, that player picks one of the two piles and does one of the following: either

    The player to take the last jelly bean wins. Use strong induction to prove that the second player always has a winning strategy in Nim-Move. A complete and correct solution will first identify what the strategy is, and then prove that following this strategy will lead the second player to win the game (no matter what the first player chooses to do at each turn).

  3. Linked Lists. Recall the recursive definition of the set of linked lists of natural numbers (from class) \[\begin{array}{ll} \textrm{Basis Step: } & [] \in L \\ \textrm{Recursive Step: } & \textrm{If } l \in L\textrm{ and }n \in \mathbb{N} \textrm{, then } (n, l) \in L \end{array}\] and the definitions of the function which gives the length of a linked list of natural numbers \(length: L \to \mathbb{N}\) \[\begin{array}{llll} \textrm{Basis Step:} & & length(~[]~) &= 0 \\ \textrm{Recursive Step:} & \textrm{If } l \in L\textrm{ and }n \in \mathbb{N}\textrm{, then } & length(~(n, l)~) &= 1+ length(l) \end{array}\] the function \(append : L \times \mathbb{N} \to L\) that adds an element at the end of a linked list \[\begin{array}{llll} \textrm{Basis Step:} & \textrm{If } m \in \mathbb{N}\textrm{ then } & append(~([], m)~) & = (m, [])\\ \textrm{Recursive Step:} & \textrm{If } l \in L\textrm{ and }n \in \mathbb{N}\textrm{ and }m \in \mathbb{N}\textrm{, then } & append(~(~(n, l), m~)~) &= (n, append(~(l, m)~)~) \end{array}\] and the function \(prepend : L \times \mathbb{N} \to L\) that adds an element at the front of a linked list \[prepend(~(l, n)~) = (n, l)\]


    Sample response that can be used as reference for the detail expected in your answer: To evaluate the result of \(length(~(4,(2,(7,[])))~)\) we calculate: \[\begin{aligned} length(~(4,(2,(7,[])))~) &= 1 + length ( ~(2,(7,[]))~) \\ & \qquad \qquad \text{using recursive step of definition of $length$, with $n=4, l=(2,(7,[]))$} \\ &= 1 + 1 + length ( ~(7,[])~) \\ & \qquad \qquad \text{using recursive step of definition of $length$, with $n=2, l=(7,[])$} \\ &= 1 + 1 + 1+ length ( ~[]~) \\ & \qquad \qquad \text{using recursive step of definition of $length$, with $n=7, l=[]$} \\ &= 1 + 1 + 1 + 0\\ & \qquad \qquad \text{using basis step of definition of $length$, since input to $length$ is $[]$} \\ \end{aligned}\]


    In this question, we’ll consider the combination of these functions with a new function, one that removes the element at the front of the list (if there is any). We define \(remove: L \to L\) by \[\begin{array}{ll} \textrm{Basis Step: } & remove([]) = [] \\ \textrm{Recursive Step: } & \textrm{If } l \in L\textrm{ and }n \in \mathbb{N} \textrm{, then } remove(~(n, l)~) = l \end{array}\]

    1. (Graded for correctness) What is the result of \(remove(~append(~(prepend~(~(~(10,[]), 5~)~), 20)~)~)\)? For full credit, include all intermediate steps with brief justifications for each.

    2. (Graded for correctness) Prove the statement \[\forall l \in L \left(~ remove( prepend(~(l,0)~)) = l ~\right)\]

    3. (Graded for correctness) Disprove the statement \[\forall l \in L \left(~ remove( append(~(l,0)~)) = l ~\right)\]

  4. Primes, divisors, and proof strategies. For each statement below, identify the main logical structure or connective of the statement, list the proof strategies that could be used to prove and to disprove a statement with that structure, then identify whether the statement is true or false and justify with a proof of the statement or its negation. (Graded for correctness of identification of logical structure and proof strategies and evaluation of statement (is it true or false?) and fair effort completeness of the proof)


    Sample response that can be used as reference for the detail expected in your answer:

    Consider the statement: There is a greatest negative integer.

    The main logical structure for this statement is that it is an existential statement, as we can see by translating it to symbols: \[\exists g \in \mathbb{Z}^{-} \forall x \in \mathbb{Z}^{-} ( g \geq x)\] To prove an existential statement, the main proof strategy we could use is to find a witness. Proof by cases and proof by contradiction could also be used, because both can be used to prove any statement (no matter its logical structure).

    To disprove an existential statement, we would need to prove its negation, which (using DeMorgan’s Laws) can be written as a universal statement. Therefore, to disprove this statement the strategies we could use are universal generalization or structural induction (because \(\mathbb{Z}^{-}\) is a recursively defined set) or proof by cases or proof by contradiction. Notice that proof by exhaustion is not possible because the domain is not finite.

    The statement is true, as we can see from the witness \(g = -1\), since it is in the domain \(\mathbb{Z}^{-}\) and when we evaluate \[\forall x \in \mathbb{Z}^{-} ( -1 \geq x)\] we can proceed by universal generalization and take an arbitrary negative integer \(x\), which by definition means \(x < 0\), and since \(x\) is an integer, guarantees \(x \leq -1 = g\), as required.


    1. The quotient of any even number with any nonzero even number is even.

    2. There are two odd numbers (not necessarily distinct) whose sum is even.

    3. The greatest common divisor of 5 and 23 is 1 and the greatest common divisior of 7 and 19 is 1.

    4. There are two positive integers greater than 20 that have the same greatest common divisor with 20. Note: typo fixed, originally said “greatest common division” instead of “greatest common divisor”.


  1. This means you will get full credit so long as your submission demonstrates honest effort to answer the question. You will not be penalized for incorrect answers. To demonstrate your honest effort in answering the question, we expect you to include your attempt to answer *each* part of the question. If you get stuck with your attempt, you can still demonstrate your effort by explaining where you got stuck and what you did to try to get unstuck.↩︎

  2. According to the Merriam Webster definition, a rubric is “a guide listing specific criteria for grading or scoring academic papers, projects, or tests”. For CSE 20, you can see the rubrics we use to grade assignments and exams on Gradescope: next to your submission for each question you will find the rubric items and associated point values. The highlighted items are the ones we select to describe your work; these correspond to the score assigned for the question.↩︎