Week 6

CSE 390Z

November 5, 2024

Welcome in!

Grab your nametag and the workshop problems from the back

​

Talk with your neighbors:

What classes do you plan to take winter quarter?

Announcements

Past Assignments

• Quick Check 5 Late Due: Wednesday Nov. 7
• Homework Corrections 1 Late Due: Wednesday Nov. 7

Assignments

• Quick Check 6 Due: Tuesday Nov. 12, 11:59 PM

Reminder: Grading Structure

• Course is credit/no-credit
• Each assignment is satisfactory (S) / not satisfactory (N)
• All concept-based assignments are graded on effort, not correctness
• 3 slots in Gradescope to resubmit an assignment you received an N on
• Can be used to submit an assignment late that you never made an initial submission for

​

​

​

Workshop Participation: 7 of 9

Quick Checks: 7 of 9

Skills Assessments: 4 of 4

Exam Preparation: 2 of 2

A Special Announcement

• Mid-Quarter Review Session!
• Friday, November 8th
• 12:00PM - 1:00PM @ Gates 121
• Course staff will spend an hour reviewing important concepts for the 390Z practice midterm and 311 midterm
• Predicate translations - Induction
• We’ll prepare content to go through, but you can bring any questions you have as well!
• Earn workshop participation credit!
• If you’ve missed a couple of workshops up to this point, you can come to the review session to make it up and get credit.
• It’s a win-win! You’re (probably) going to be here anyway!

Mid-Quarter Feedback

We appreciate your feedback!

Conceptual Review: Induction

​

Induction

General idea: Show that knocking down one domino will cause the next domino to fall.

Induction

General idea: Show that knocking down one domino will cause the next domino to fall.

A toy example: Prove that if the first domino falls, then all dominos will fall.

​

Let k be any arbitrary domino in this sequence.

Let P(x) := “Domino x will fall.”

​

Essentially, induction involves assuming P(k) and showing P(k+1).

​

In other words, we do a direct proof for P(k) → P(k+1)!

Induction

General idea: Show that knocking down one domino will cause the next domino to fall.

P(1) → P(2) → … → P(k-2) → P(k-1) → P(k) → P(k+1) → P(k+2) ... etc…

Induction Steps - Weak Induction

1. Let P(n) be … We will show that P(n) is true for all n ≥ 0 by induction.
2. Base case: Prove P(0)
3. Inductive Hypothesis: Suppose P(k) is true for an arbitrary int. k ≥ 0
4. Inductive Step: Show P(k+1)
5. By induction, we have shown that P(n) is true for all n ≥ 0.

Q0 Walkthrough

Induction with inequalities: Question 0

Prove by induction on n that for all integers n ≥ 4, the inequality n! > 2ⁿ is true.

​

​

Prove by induction on n that for all integers n ≥ 4, the inequality n! > 2ⁿ is true.

1). Let P(n) be "n! > 2ⁿ ". We will prove P(n) is true for all n ∈ N, n ≥ 4, by induction

​

Prove by induction on n that for all integers n ≥ 4, the inequality n! > 2ⁿ is true.

1). Let P(n) be "n! > 2ⁿ ". We will prove P(n) is true for all n ∈ N, n ≥ 4, by induction

2). Base Case: (n = 4): 4! = 24 and 2⁴ = 16, since 24 > 16, P(4) is true.

​

​

​

Prove by induction on n that for all integers n ≥ 4, the inequality n! > 2ⁿ is true.

1). Let P(n) be "n! > 2ⁿ ". We will prove P(n) is true for all n ∈ N, n ≥ 4, by induction

2). Base Case: (n = 4): 4! = 24 and 2⁴ = 16, since 24 > 16, P(4) is true.

Do not start with 4! > 2⁴. That is backwards reasoning because that is what we are trying to prove

​

​

Prove by induction on n that for all integers n ≥ 4, the inequality n! > 2ⁿ is true.

1). Let P(n) be "n! > 2ⁿ ". We will prove P(n) is true for all n ∈ N, n ≥ 4, by induction

2). Base Case: (n = 4): 4! = 24 and 2⁴ = 16, since 24 > 16, P(4) is true.

3). Inductive Hypothesis: Suppose that P(k) is true for some arbitrary integer k ∈ N, k ≥ 4.

4). Inductive Step: Goal: Show P(k + 1), i.e. show (k + 1)! > 2^k+1

​

​

Prove by induction on n that for all integers n ≥ 4, the inequality n! > 2ⁿ is true.

1). Let P(n) be "n! > 2ⁿ ". We will prove P(n) is true for all n ∈ N, n ≥ 4, by induction

2). Base Case: (n = 4): 4! = 24 and 2⁴ = 16, since 24 > 16, P(4) is true.

3). Inductive Hypothesis: Suppose that P(k) is true for some arbitrary integer k ∈ N, k ≥ 4.

4). Inductive Step: Goal: Show P(k + 1), i.e. show (k + 1)! > 2^k+1

(k + 1)! = k! · (k + 1) [expanding factorial]

.

.

​

Prove by induction on n that for all integers n ≥ 4, the inequality n! > 2ⁿ is true.

1). Let P(n) be "n! > 2ⁿ ". We will prove P(n) is true for all n ∈ N, n ≥ 4, by induction

2). Base Case: (n = 4): 4! = 24 and 2⁴ = 16, since 24 > 16, P(4) is true.

3). Inductive Hypothesis: Suppose that P(k) is true for some arbitrary integer k ∈ N, k ≥ 4.

4). Inductive Step: Goal: Show P(k + 1), i.e. show (k + 1)! > 2^k+1

(k + 1)! = k! · (k + 1) [expanding factorial]

> 2^k · (k + 1) (By I.H., k! > 2^k )

.

.

​

Prove by induction on n that for all integers n ≥ 4, the inequality n! > 2ⁿ is true.

1). Let P(n) be "n! > 2ⁿ ". We will prove P(n) is true for all n ∈ N, n ≥ 4, by induction

2). Base Case: (n = 4): 4! = 24 and 2⁴ = 16, since 24 > 16, P(4) is true.

3). Inductive Hypothesis: Suppose that P(k) is true for some arbitrary integer k ∈ N, k ≥ 4.

4). Inductive Step: Goal: Show P(k + 1), i.e. show (k + 1)! > 2^k+1

(k + 1)! = k! · (k + 1) [expanding factorial]

> 2^k · (k + 1) (By I.H., k! > 2^k )

> 2^k · 2 (Since k ≥ 4, so k + 1 ≥ 5 > 2)

.

​

Prove by induction on n that for all integers n ≥ 4, the inequality n! > 2ⁿ is true.

1). Let P(n) be "n! > 2ⁿ ". We will prove P(n) is true for all n ∈ N, n ≥ 4, by induction

2). Base Case: (n = 4): 4! = 24 and 2⁴ = 16, since 24 > 16, P(4) is true.

3). Inductive Hypothesis: Suppose that P(k) is true for some arbitrary integer k ∈ N, k ≥ 4.

4). Inductive Step: Goal: Show P(k + 1), i.e. show (k + 1)! > 2^k+1

(k + 1)! = k! · (k + 1) [expanding factorial]

> 2^k · (k + 1) (By I.H., k! > 2^k )

> 2^k · 2 (Since k ≥ 4, so k + 1 ≥ 5 > 2)

= 2^k+1 (exponent properties)

​

Prove by induction on n that for all integers n ≥ 4, the inequality n! > 2ⁿ is true.

1). Let P(n) be "n! > 2ⁿ ". We will prove P(n) is true for all n ∈ N, n ≥ 4, by induction

2). Base Case: (n = 4): 4! = 24 and 2⁴ = 16, since 24 > 16, P(4) is true.

3). Inductive Hypothesis: Suppose that P(k) is true for some arbitrary integer k ∈ N, k ≥ 4.

4). Inductive Step: Goal: Show P(k + 1), i.e. show (k + 1)! > 2^k+1

(k + 1)! = k! · (k + 1) [expanding factorial]

> 2^k · (k + 1) (By I.H., k! > 2^k )

> 2^k · 2 (Since k ≥ 4, so k + 1 ≥ 5 > 2)

= 2^k+1 (exponent properties)

5). Conclusion: So by induction, P(n) is true for all n ∈ N, n ≥ 4.

Q2 Walkthrough

Induction with Divides: Problem Set Question 2

Prove that 9 | (n³ + (n + 1)³ + (n + 2)³) for all n > 1 by induction

​

Prove that 9 | (n³ + (n + 1)³ + (n + 2)³) for all n > 1 by induction.

1). Let P(n) be “9 | n³ + (n + 1)³ + (n + 2)³”. We will prove P (n) for all integers n > 1 by induction on n.

​

Prove that 9 | (n³ + (n + 1)³ + (n + 2)³) for all n > 1 by induction.

1). Let P(n) be “9 | n³ + (n + 1)³ + (n + 2)³”. We will prove P (n) for all integers n > 1 by induction on n.

2). Base Case (n = 2): 2³ + (2 + 1)³ + (2 + 2)³ = 8 + 27 + 64 = 99 = 9 · 11, so 9 | 2³ + (2 + 1)³ + (2 + 2)³, so P(2) holds.

​

​

​

Prove that 9 | (n³ + (n + 1)³ + (n + 2)³) for all n > 1 by induction.

1). Let P(n) be “9 | n³ + (n + 1)³ + (n + 2)³”. We will prove P(n) for all integers n > 1 by induction on n.

2). Base Case (n = 2): 2³ + (2 + 1)³ + (2 + 2)³ = 8 + 27 + 64 = 99 = 9 · 11, so 9 | 2³ + (2 + 1)³ + (2 + 2)³, so P(2) holds.

3). Inductive Hypothesis: Assume that 9 | k³ + (k + 1)³ + (k + 2)³ for an arbitrary integer k > 1. ** Note that this is equivalent to assuming that k³ + (k + 1)³ + (k + 2)³ = 9j for some integer j by the definition of divides.

Prove that 9 | (n³ + (n + 1)³ + (n + 2)³) for all n > 1 by induction.

3). Inductive Hypothesis: Assume that 9 | k³ + (k + 1)³ + (k + 2)³ for an arbitrary integer k > 1. ** Note that this is equivalent to assuming that k³ + (k + 1)³ + (k + 2)³ = 9j for some integer j by the definition of divides.

4). Inductive Step: Goal: Show 9 | (k + 1)³ + (k + 2)³ + (k + 3)³

(k + 1)³ + (k + 2)³ + (k + 3)³ = (k² + 6k + 9)(k + 3) + (k + 1)³ + (k + 2)³ [expanding trinomial]

= (k³ + 6k² + 9k + 3k² + 18k + 27) + (k + 1)³ + (k + 2)³ [expanding binomial]

= 9k² + 27k + 27 + k³ + (k + 1)³ + (k + 2)³ [adding like terms]

= 9k² + 27k + 27 + 9j [by I.H.]

= 9(k² + 3k + 3 + j) [factoring out 9]

Since k and j are integers, k² + 3k + 3 + j is also an integer. Therefore, by the definition of divides,

9 | (k + 1)³ + (k + 2)³ + (k + 3)³, so P(k) → P (k + 1) for an arbitrary integer k > 1.

​

Prove that 9 | (n³ + (n + 1)³ + (n + 2)³) for all n > 1 by induction.

3). Inductive Hypothesis: Assume that 9 | k³ + (k + 1)³ + (k + 2)³ for an arbitrary integer k > 1. ** Note that this is equivalent to assuming that k³ + (k + 1)³ + (k + 2)³ = 9j for some integer j by the definition of divides.

4). Inductive Step: Goal: Show 9 | (k + 1)³ + (k + 2)³ + (k + 3)³

(k + 1)³ + (k + 2)³ + (k + 3)³ = (k² + 6k + 9)(k + 3) + (k + 1)³ + (k + 2)³ [expanding trinomial]

= (k³ + 6k² + 9k + 3k² + 18k + 27) + (k + 1)³ + (k + 2)³ [expanding binomial]

= 9k² + 27k + 27 + k³ + (k + 1)³ + (k + 2)³ [adding like terms]

= 9k² + 27k + 27 + 9j [by I.H.]

= 9(k² + 3k + 3 + j) [factoring out 9]

Since k and j are integers, k² + 3k + 3 + j is also an integer. Therefore, by the definition of divides,

9 | (k + 1)³ + (k + 2)³ + (k + 3)³, so P(k) → P (k + 1) for an arbitrary integer k > 1.

​

Prove that 9 | (n³ + (n + 1)³ + (n + 2)³) for all n > 1 by induction.

3). Inductive Hypothesis: Assume that 9 | k³ + (k + 1)³ + (k + 2)³ for an arbitrary integer k > 1. ** Note that this is equivalent to assuming that k³ + (k + 1)³ + (k + 2)³ = 9j for some integer j by the definition of divides.

4). Inductive Step: Goal: Show 9 | (k + 1)³ + (k + 2)³ + (k + 3)³

(k + 1)³ + (k + 2)³ + (k + 3)³ = (k² + 6k + 9)(k + 3) + (k + 1)³ + (k + 2)³ [expanding trinomial]

= (k³ + 6k² + 9k + 3k² + 18k + 27) + (k + 1)³ + (k + 2)³ [expanding binomial]

= 9k² + 27k + 27 + k³ + (k + 1)³ + (k + 2)³ [adding like terms]

= 9k² + 27k + 27 + 9j [by I.H.]

= 9(k² + 3k + 3 + j) [factoring out 9]

Since k and j are integers, k² + 3k + 3 + j is also an integer. Therefore, by the definition of divides,

9 | (k + 1)³ + (k + 2)³ + (k + 3)³, so P(k) → P(k + 1) for an arbitrary integer k > 1.

5). Conclusion: P(n) holds for all integers n > 1 by induction on n.

​

Q4 Walkthrough

• Fill in the claim.
• Mentioned in the question itself.

2) Base Cases.

• n = 1, 2, 3

eg. n = 1: f(1) = 1 = 1^2

​

3) Inductive Hypothesis.

• Fill in the appropriate assumptions.
• Min and Max Base Case

Another way:

IH: Suppose P(1)⋀P(2)⋀P(3)⋀…⋀P(k) for some arbitrary integer k ≥ 3.

​

1

3

IH: Suppose P(1)⋀P(2)⋀P(3)⋀…⋀P(k) for some arbitrary integer k ≥ 3.

4) Inductive Step.

• Very helpful to fill in the “Goal”.

1. Apply definition of f.

2. Simplify

3. Use the Inductive Hypothesis

4. Expansion.

5. Group like terms.

6. By algebra.

IH: [eg. f(k) = k^2]

1

3

IH: Suppose P(1)⋀P(2)⋀P(3)⋀…⋀P(k) for some arbitrary integer k ≥ 3.

5) Conclusion.

• Restating what we were trying to prove.

1

3

1

Q5 Walkthrough

A store sells candy in packs of 4 and packs of 7. Let P(n) be defined as "You are able to buy n packs of candy". For example, P(3) is not true, because you cannot buy exactly 3 packs of candy from the store. However, it turns out that P(n) is true for any n ≥ 18. Use strong induction on n to prove this.

1). INTRO: define P(N)

​

2). Base case:

.

.

.

A store sells candy in packs of 4 and packs of 7. Let P(n) be defined as "You are able to buy n packs of candy". For example, P(3) is not true, because you cannot buy exactly 3 packs of candy from the store. However, it turns out that P(n) is true for any n ≥ 18. Use strong induction on n to prove this.

1). INTRO: Let P(n) be defined as "You are able to buy n packs of candy". We will prove P(n) is true for all integers n ≥ 18 by strong induction.

2). Base cases: (n = 18,19,20,21):

n = 18: 18 packs of candy can be made up of 2 packs of 7 and 1 pack of 4 (18 = 2 ∗ 7 + 1 ∗ 4).

.

.

.

3). Inductive Hypothesis:

A store sells candy in packs of 4 and packs of 7. Let P(n) be defined as "You are able to buy n packs of candy". For example, P(3) is not true, because you cannot buy exactly 3 packs of candy from the store. However, it turns out that P(n) is true for any n ≥ 18. Use strong induction on n to prove this.

1). INTRO: Let P(n) be defined as "You are able to buy n packs of candy". We will prove P(n) is true for all integers n ≥ 18 by strong induction.

2). Base cases: (n = 18,19,20,21):

n = 18: 18 packs of candy can be made up of 2 packs of 7 and 1 pack of 4 (18 = 2 ∗ 7 + 1 ∗ 4).

n = 19: 19 packs of candy can be made up of 1 pack of 7 and 3 packs of 4 (19 = 1 ∗ 7 + 3 ∗ 4)

.

.

3). Inductive Hypothesis:

A store sells candy in packs of 4 and packs of 7. Let P(n) be defined as "You are able to buy n packs of candy". For example, P(3) is not true, because you cannot buy exactly 3 packs of candy from the store. However, it turns out that P(n) is true for any n ≥ 18. Use strong induction on n to prove this.

1). INTRO: Let P(n) be defined as "You are able to buy n packs of candy". We will prove P(n) is true for all integers n ≥ 18 by strong induction.

2). Base cases: (n = 18,19,20,21):

n = 18: 18 packs of candy can be made up of 2 packs of 7 and 1 pack of 4 (18 = 2 ∗ 7 + 1 ∗ 4).

n = 19: 19 packs of candy can be made up of 1 pack of 7 and 3 packs of 4 (19 = 1 ∗ 7 + 3 ∗ 4)

n = 20: 20 packs of candy can be made up of 5 packs of 4 (20 = 5 ∗ 4).

.

3). Inductive Hypothesis:

A store sells candy in packs of 4 and packs of 7. Let P(n) be defined as "You are able to buy n packs of candy". For example, P(3) is not true, because you cannot buy exactly 3 packs of candy from the store. However, it turns out that P(n) is true for any n ≥ 18. Use strong induction on n to prove this.

1). INTRO: Let P(n) be defined as "You are able to buy n packs of candy". We will prove P(n) is true for all integers n ≥ 18 by strong induction.

2). Base cases: (n = 18,19,20,21):

n = 18: 18 packs of candy can be made up of 2 packs of 7 and 1 pack of 4 (18 = 2 ∗ 7 + 1 ∗ 4).

n = 19: 19 packs of candy can be made up of 1 pack of 7 and 3 packs of 4 (19 = 1 ∗ 7 + 3 ∗ 4)

n = 20: 20 packs of candy can be made up of 5 packs of 4 (20 = 5 ∗ 4).

n = 21: 21 packs of candy can be made up of 3 packs of 7 (21 = 3 ∗ 7).

3). Inductive Hypothesis: Suppose for some arbitrary integer k ≥ 21, P(18) ∧... ∧P(k)

A store sells candy in packs of 4 and packs of 7. it turns out that P(n) is true for any n ≥ 18. Use strong induction on n to prove this.

1). Intro: Let P(n) be defined as "You are able to buy n packs of candy". We will prove P(n) is true for all integers n ≥ 18 by strong induction.

3). Inductive Hypothesis: Suppose for some arbitrary integer k ≥ 21, P(18) ∧... ∧P(k)

4). Inductive step: Goal: Show P(k + 1), i.e. show that we can buy k + 1 packs of candy

…

5). Conclusion: So by strong induction, P(n) is true for all integers n ≥ 18.

A store sells candy in packs of 4 and packs of 7. it turns out that P(n) is true for any n ≥ 18. Use strong induction on n to prove this.

1). Intro: Let P(n) be defined as "You are able to buy n packs of candy". We will prove P(n) is true for all integers n ≥ 18 by strong induction.

3). Inductive Hypothesis: Suppose for some arbitrary integer k ≥ 21, P(18) ∧... ∧P(k)

4). Inductive step: Goal: Show P(k + 1), i.e. show that we can buy k + 1 packs of candy

We want to buy k + 1 packs of candy. By the I.H., we can buy exactly k −3 packs, so we can add another pack of 4 packs in order to buy k + 1 packs of candy, so P(k + 1) is true.

5). Conclusion: So by strong induction, P(n) is true for all integers n ≥ 18.

Q7 Structural Induction

Definitions to Cite & Come back to:

Exit Ticket

Your Full Name +

How do you plan to study for the 311 midterm?