For integers æ, y, notation æ|y means that x is a divisor of y. (For example 5|30, but it is not true that 5|21.) N denotes the set of natural numbers. (Recall that in this class we assume that 0 E N). Consider the following claim: Claim: Vn EN 3|(22n – 1). The inductive proof of this claim is given below, but in the inductive part the steps of the argument are out of order. Give a correct ordering of these steps. (The argument must be correct mathematically and grammatically as well.) Proof: We apply mathematical induction. In the base case, when n = 0, we have 22n – 1 = 20 – 1= 0, and 0 is a multiple of 3 (because 0 = 3 - 0), so the claim holds for n = 0. In the inductive step, let k be some arbitrary positive integer and assume that the claim holds for n = k, that is 3|(22k – 1). We now proceed as follows. (1) This implies that 22(k+1) – 1 is a multiple of 3, completing the inductive step. (2) 22(k+1) – 1 = 22k+2 – 1 = 4 · 22* – 1= 4(3c + 1) – 1 = 12c + 3 = 3(4c + 1). (3) From the inductive assumption, we have that 22k -1= 3c, for some integer c. (4) Next, we compute 22n – 1 for the next value of n, that is for n = k + 1: (5) This gives us that 22k = 3c + 1. - We proved the base case, for n = 0, and that the claim holding for n = k implies that it holds for n = k + 1. By the principle of induction, this proves the claim for all n. QED Choose the correct ordering in the derivation above: O 1-2-3-4-5 O 2-5-4-3-1 O 3-2-1-4-5 O 3-5-4-2-1
For integers æ, y, notation æ|y means that x is a divisor of y. (For example 5|30, but it is not true that 5|21.) N denotes the set of natural numbers. (Recall that in this class we assume that 0 E N). Consider the following claim: Claim: Vn EN 3|(22n – 1). The inductive proof of this claim is given below, but in the inductive part the steps of the argument are out of order. Give a correct ordering of these steps. (The argument must be correct mathematically and grammatically as well.) Proof: We apply mathematical induction. In the base case, when n = 0, we have 22n – 1 = 20 – 1= 0, and 0 is a multiple of 3 (because 0 = 3 - 0), so the claim holds for n = 0. In the inductive step, let k be some arbitrary positive integer and assume that the claim holds for n = k, that is 3|(22k – 1). We now proceed as follows. (1) This implies that 22(k+1) – 1 is a multiple of 3, completing the inductive step. (2) 22(k+1) – 1 = 22k+2 – 1 = 4 · 22* – 1= 4(3c + 1) – 1 = 12c + 3 = 3(4c + 1). (3) From the inductive assumption, we have that 22k -1= 3c, for some integer c. (4) Next, we compute 22n – 1 for the next value of n, that is for n = k + 1: (5) This gives us that 22k = 3c + 1. - We proved the base case, for n = 0, and that the claim holding for n = k implies that it holds for n = k + 1. By the principle of induction, this proves the claim for all n. QED Choose the correct ordering in the derivation above: O 1-2-3-4-5 O 2-5-4-3-1 O 3-2-1-4-5 O 3-5-4-2-1
Advanced Engineering Mathematics
10th Edition
ISBN:9780470458365
Author:Erwin Kreyszig
Publisher:Erwin Kreyszig
Chapter2: Second-order Linear Odes
Section: Chapter Questions
Problem 1RQ
Related questions
Question
Transcribed Image Text:For integers æ, y, notation æ|y means that x is a divisor of y. (For example 5|30, but it is not
true that 5|21.) N denotes the set of natural numbers. (Recall that in this class we assume that
0 E N). Consider the following claim:
Claim: Vn EN 3|(22n – 1).
The inductive proof of this claim is given below, but in the inductive part the steps of the
argument are out of order. Give a correct ordering of these steps. (The argument must be
correct mathematically and grammatically as well.)
Proof: We apply mathematical induction. In the base case, when n = 0, we have 22n – 1 =
20 – 1= 0, and 0 is a multiple of 3 (because 0 = 3 - 0), so the claim holds for n = 0.
In the inductive step, let k be some arbitrary positive integer and assume that the claim holds
for n = k, that is 3|(22k – 1). We now proceed as follows.
(1) This implies that 22(k+1) – 1 is a multiple of 3, completing the inductive step.
(2) 22(k+1) – 1 = 22k+2 – 1 = 4 · 22* – 1= 4(3c + 1) – 1 = 12c + 3 = 3(4c + 1).
(3) From the inductive assumption, we have that 22k -1= 3c, for some integer c.
(4) Next, we compute 22n – 1 for the next value of n, that is for n = k + 1:
(5) This gives us that 22k = 3c + 1.
-
We proved the base case, for n = 0, and that the claim holding for n = k implies that it holds
for n = k + 1. By the principle of induction, this proves the claim for all n. QED
Choose the correct ordering in the derivation above:
O 1-2-3-4-5
O 2-5-4-3-1
O 3-2-1-4-5
O 3-5-4-2-1
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 2 steps
Recommended textbooks for you
Advanced Engineering Mathematics
Advanced Math
ISBN:
9780470458365
Author:
Erwin Kreyszig
Publisher:
Wiley, John & Sons, Incorporated
Numerical Methods for Engineers
Advanced Math
ISBN:
9780073397924
Author:
Steven C. Chapra Dr., Raymond P. Canale
Publisher:
McGraw-Hill Education
Introductory Mathematics for Engineering Applicat…
Advanced Math
ISBN:
9781118141809
Author:
Nathan Klingbeil
Publisher:
WILEY
Advanced Engineering Mathematics
Advanced Math
ISBN:
9780470458365
Author:
Erwin Kreyszig
Publisher:
Wiley, John & Sons, Incorporated
Numerical Methods for Engineers
Advanced Math
ISBN:
9780073397924
Author:
Steven C. Chapra Dr., Raymond P. Canale
Publisher:
McGraw-Hill Education
Introductory Mathematics for Engineering Applicat…
Advanced Math
ISBN:
9781118141809
Author:
Nathan Klingbeil
Publisher:
WILEY
Mathematics For Machine Technology
Advanced Math
ISBN:
9781337798310
Author:
Peterson, John.
Publisher:
Cengage Learning,
