CSC165H1, Winter 2022 CSC165H1: Worksheet 8—Induction (Partial Solutions)
Learning Objectives
By the end of this worksheet, you will:
• Prove statements using the technique of simple induction.
Copyright By PowCoder代写 加微信 powcoder
• Write proofs using simple induction with different starting base cases. • Write proofs using simple induction within the scope of a larger proof.
1. Induction. Consider the following statement:
∀n ∈ N, n ≤ 2n
(a) Suppose we want to prove this statement using induction. Write down the full statement we’ll prove (it should
be an AND of the base case and induction step). Consult your notes if you aren’t sure about this!
(b) Prove the statement using induction. We strongly recommend reviewing the induction proof template from lecture before working on a proof here.
Hint: 2k+1 =2k +2k.
0 ≤ 20 ∧ ∀k ∈ N, k ≤ 2k ⇒ k + 1 ≤ 2k+1
Proof. We will prove this statement using induction on n. Base case: let n = 0.
Then2n =1,andn=0,son≤2n.
Induction step: let k ∈ N, and assume that k ≤ 2k. We want to prove that k + 1 ≤ 2k+1.
Since 0 ≤ k, we know that 1 ≤ 2k (raising 2 to the power of either side). Then we can add this inequality to our assumption k ≤ 2k to get:
k+1≤2k +2k k + 1 ≤ 2k+1
CSC165H1, Winter 2022 CSC165H1: Worksheet 8—Induction (Partial Solutions)
2. Induction (summations). If marbles are arranged to form an equilateral triangle shape, with n marbles on each n
side, a total of i marbles will be required. (For convenience, we also define T0 = 0.) i=1
T1 = 1 T2 = 3 T3 = 6 T4 = 10 T5 = 15
In the course notes, we prove that i = n(n + 1)/2. For each n ∈ N, let Tn = n(n + 1)/2; these numbers are
usually called the triangular numbers. Use induction to prove that
n n(n + 1)(n + 2)
Let us start by defining the predicate
n(n + 1)(n + 2) 6
We need to prove that ∀n ∈ N, P (n).
Proof. Base case: let n = 0. We want to prove P (0). Then we can calculate:
n0 Tj =Tj j=0 j=0
And also 0(0 + 1)(0 + 2) = 0. 6
Induction step: Let k ∈ N and assume P(k), i.e., that Tj = k(k+1)(k+2)/6. We want to prove P(k+1),
i.e.,thatTj =(k+1)(k+2)(k+3)/6.
CSC165H1, Winter 2022 CSC165H1: Worksheet 8—Induction (Partial Solutions)
We’ll calculate starting from the left side and show that it equals the right side.
Tj + Tk+1
k(k+1)(k+2) +Tk+1
k(k+1)(k+2) + (k+1)(k+2)
62 k(k+1)(k+2)+3(k+1)(k+2)
6 (k+1)(k+2)(k+3)
(pulling out the last term) (by the I.H.)
(by the definition of Tk+1)
CSC165H1, Winter 2022 CSC165H1: Worksheet 8—Induction (Partial Solutions)
3. Induction (inequalities). Consider the statement:
For every positive real number x and every natural number n, (1 + x)n ≥ (1 + nx).
We can express the statement using the notation of predicate logic as: ∀x∈R+, ∀n∈N, (1+x)n ≥1+nx
Notice that in this statement, there are two universally-quantified variables: n and x.1 Prove this statement is True using the following approach:
(a) Use the standard proof structure to introduce x.
(b) When proving the ∀n ∈ N, (1 + x)n ≥ 1 + nx, do induction on n.2
Proof. Letx∈R+. We’llprovethatforalln∈N,(1+x)n ≥1+nxbyinduction. Base case: Let n = 0.
Then(1+x)n =1and1+nx=1. Sothen(1+x)n ≥1+nx.
Induction step: Let k ∈ N, and assume that (1+x)k ≥ 1+kx. We want to prove that (1+x)k+1 ≥ 1+(k+1)x. We’ll start with the quantity on the left, and show that it’s ≥ the quantity on the right.
(1+x)k+1 =(1+x)k(1+x) ≥ (1 + kx)(1 + x)
= 1 + kx + x + kx2 ≥1+kx+x
= 1 + (k + 1)x
(by the I.H.) (sincekx2 ≥0)
1For extra practice, think about the following questions. First, would the statement still be True with the order of the quantifiers reversed: ∀n ∈ N, ∀x ∈ R+, (1 + x)n ≥ 1 + nx? Second, if this variation is correct, how would this change the proof?
2Your predicate P(n) that you want to prove will also contain the variable x—that’s okay, since when we do the induction proof, x has already been defined.
CSC165H1, Winter 2022 CSC165H1: Worksheet 8—Induction (Partial Solutions)
4. Changing the starting number. Recall that you previously proved that ∀n ∈ N, n ≤ 2n using induction.
(a) First, use trial and error to fill in the blank to make the following statement true—try finding the smallest
natural number that works!
∀n ∈ N, n ≥ ⇒ 30n ≤ 2n
(b) Now, prove the completed statement using induction. Be careful about how you choose your base case!
∀n ∈ N, n ≥ 8 ⇒ 30n ≤ 2n.
Proof. Base case: Let n = 8. Then30n=240,and2n =256. So30n≤2n.
Induction step: Let k ∈ N. Assume that k ≥ 8, and that 30k ≤ 2k. We want to prove that 30(k + 1) ≤ 2k+1.
Since 8 ≤ k, we know that 256 ≤ 2k (raising 2 to the power of either side). The induction hypothesis tells us that 30k ≤ 2k. Adding these two inequalities yields:
30k+256≤2k +2k 30k + 256 ≤ 2k+1
30k + 30 ≤ 2k+1 (since 30 ≤ 256) 30(k + 1) ≤ 2k+1
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com