Mathematics > QUESTIONS & ANSWERS > CS 70 Discrete Mathematics and Probability Theory HW 5 | University of California, Berkeley (All)
CS 70 Discrete Mathematics and Probability Theory HW 5 | University of California, Berkeley
Document Content and Description Below
CS 70 Discrete Mathematics and Probability Theory Fall 2019 Alistair Sinclair and Yun S. Song HW 5 Note: This homework consists of two parts. The first part (questions 1-4) will be graded and will ... determine your score for this homework. The second part (questions 5-6) will be graded if you submit them, but will not affect your homework score in any way. You are strongly advised to attempt all the questions in the first part. You should attempt the problems in the second part only if you are interested and have time to spare. For each problem, justify all your answers unless otherwise specified. Part 1: Required Problems 1 Recursively Defined Polynomials Let’s define two polynomials f1(x) = x − 2, f2(x) = x2 + 3, and for each natural number n ≥ 2, recursively define fn(x) = x fn−1(x)− fn−2(x). (a) Compute f3(x) and f4(x). (b) What is the largest number of roots that fn(x) can have over R? What is the smallest number of roots it can have? Both answers should depend only on the degree of fn(x), and one will depend on whether n is even or odd. (c) Prove that fn(2) = 0 mod 7 for every n. Solution: (a) Directly from the definition of fn(x) in the problem, f3(x) = x f2(x)− f1(x) = x(x2 +3)−(x−2) = x3 +2x +2 and f4(x) = x f3(x)− f2(x) = x(x3 +2x +2)−(x2 +3) = x4 +x2 +2x−3: CS 70, Fall 2019, HW 5 1(b) Recall that the degree of a polynomial is the highest exponent that appears in it, and that a polynomial of degree d has at most d roots over any field. Over R, a polynomial of even degree need not have any roots (consider x2d +a2), but a polynomial of odd degree must have at least one: if f(x) = x2d+1 + f2dx2d +···+ f0x0 then f(x) goes to positive infinity as x gets very large and positive, to negative infinity as x gets very large and negative, and we can use the intermediate value theorem to prove that there is a root somewhere in between. So all we need to do is compute the degree of fn(x). In our case, the degree of f1(x) is one, so it has exactly one root (a degree one polynomial over any field has exactly one root). The degree of f2(x) is two, so it could in principle have up to two roots, but because f2(x) = x2 +3 and 3 > 0, it has none. For n > 1, let’s prove by (strong) induction that fn(x) has degree n, and that the coefficient of the xn term is 1. We’ve already done the base case, so assume that fk(x) and fk−1(x) have degree k and k − 1 respectively. Then by definition fk+1(x) = x fk(x)− fk−1(x) = xxk +ak−1xk−1 +···+a1x+a0 − xk−1 +bk−2xk−2 +···+b1x+b0 Ind. Assump. = xk+1 +ak−1xk + (ak−2 −1)xk−1 + (ak−3 − bk−2)xk−2 +···+ (a0 − b1)x − b0; and the last line clearly has degree k +1. Since we’ve proved that fn(x) is a degree-n polynomial, we know it can have at most n roots, and has at least zero if n is even, and at least one if n is odd. (c) Let’s prove this by strong induction as well. We’ll need two base cases, since each fk(x) is defined in terms of the two previous polynomials in the sequence: these base cases are f0(2) = 2−2 = 0 [Show More]
Last updated: 9 months ago
Preview 3 out of 10 pages
Loading document previews ...
Buy this document to get the full access instantly
Instant Download Access after purchase
Buy NowInstant download
We Accept:
Reviews( 0 )
$5.00
Can't find what you want? Try our AI powered Search
Document information
Connected school, study & course
About the document
Uploaded On
Feb 25, 2021
Number of pages
10
Written in
Additional information
This document has been written for:
Uploaded
Feb 25, 2021
Downloads
0
Views
87
.png)
.png)
