Statement. Let {F} be the sequence defined by the recursive definition Fn Fo= 0 and F₁ = 1. Then for all n E Zzo, Fn is even. Proof. Let P(n) be the statement that Fn is even. Base Case: Since Fo= 0, and 0 is even, P(0) is true. = Fn-1 + Fn-2 Induction Step: Suppose that P(0), P(1),..., P(k) is true for some k ≥ 0; that is, Fo, F₁,...,. each even. We will show that P(k + 1) is true; that is, Fk+1 is even. FkFk-1. Since P(k) and P(k − 1) are both true, F = 2l and F-1 = 2r for some integers and r. By the recurrence relation, Fk+1 F-1 are both even. So by definition, F = 2l + 2r = = 2(l+r). Since l and r are integers, l + r is an integer, and by definition, F Fk+1 also even. Thus, by the Principle of Induction, the statement is true. (a) Do you believe the statement is true? If so why? If not, give an examlpe to show why not. (b) There is something wrong with the proof. EXPLAIN what it is. (c) What kind of induction is being used? Strong or weak? How do you know?
Statement. Let {F} be the sequence defined by the recursive definition Fn Fo= 0 and F₁ = 1. Then for all n E Zzo, Fn is even. Proof. Let P(n) be the statement that Fn is even. Base Case: Since Fo= 0, and 0 is even, P(0) is true. = Fn-1 + Fn-2 Induction Step: Suppose that P(0), P(1),..., P(k) is true for some k ≥ 0; that is, Fo, F₁,...,. each even. We will show that P(k + 1) is true; that is, Fk+1 is even. FkFk-1. Since P(k) and P(k − 1) are both true, F = 2l and F-1 = 2r for some integers and r. By the recurrence relation, Fk+1 F-1 are both even. So by definition, F = 2l + 2r = = 2(l+r). Since l and r are integers, l + r is an integer, and by definition, F Fk+1 also even. Thus, by the Principle of Induction, the statement is true. (a) Do you believe the statement is true? If so why? If not, give an examlpe to show why not. (b) There is something wrong with the proof. EXPLAIN what it is. (c) What kind of induction is being used? Strong or weak? How do you know?
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:Statement. Let {F} be the sequence defined by the recursive definition Fn
Fo= 0 and F₁ = 1. Then for all n E Zzo, Fn is even.
Proof. Let P(n) be the statement that Fn is even.
Base Case: Since Fo= 0, and 0 is even, P(0) is true.
=
Fn-1 + Fn-2, with
Induction Step: Suppose that P(0), P(1),…, P(k) is true for some k ≥ 0; that is, Fo, F₁,..., Fk are
each even. We will show that P(k + 1) is true; that is, Fk+1 is even.
=
=
By the recurrence relation, Fk+1 FkFk-1. Since P(k) and P(k − 1) are both true, F and
F-1 are both even. So by definition, F 2l and Fk-1 = 2r for some integers and r. Thus,
Fk+1 2l + 2r = 2(l+r). Since l and r are integers, l +r is an integer, and by definition, Fk+1 is
also even.
Thus, by the Principle of Induction, the statement is true.
(a) Do you believe the statement is true? If so why? If not, give an examlpe to show why not.
(b) There is something wrong with the proof. EXPLAIN what it is.
(c) What kind of induction is being used? Strong or weak? How do you know?
Expert Solution
Step 1
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 2 images
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,
