Math 55: Discrete Mathematics


 Giles Harrison
 5 years ago
 Views:
Transcription
1 Math 55: Discrete Mathematics UC Berkeley, Spring 2012 Homework # 9, due Wednesday, April How many ways are there to pay a bill of 17 pesos using a currency with coins of values of 1 peso, 2 pesos, 5 pesos, and 10 pesos, and with bills with values of 5 pesos and 10 pesos? Let a n denote the number of ways to pay a bill of n pesos. Then a n = 0 for n < 0, and a 0 = 1, and we have the recurrence relation a n = a n 1 + a n a n a n 10 for n 1. This recurrence relation gives the following sequence: n a n Hence there are 9494 ways to pay a bill of 17 pesos a) Find a recurrence relation for the number of bit strings of length n that contain three consecutive 0s. b) What are initial conditions? c) How many bit strings of length seven contain three consecutive 0s? Let a n denote the number of such strings of length n. a) Consider a string of length n that contains three consecutive 0s. Such a string either ends with 1, or with 10, or with 100, or with 000. In the first case, there are a n 1 possibilities. In the second case, there are a n 2 possibilities. In the third case, there are a n possibilities. And, in the fourth case, there are 2 n possibilities. Hence the recurrence relation is a n = a n 1 + a n 2 + a n + 2 n for n. 1
2 b) The initial conditions are a 0 = a 1 = a 2 = 0. Note that a = 1. c) The recurrence gives the sequence of positive integers 0, 0, 0, 1,, 8, 20, 47, 107, 28, 520, 1121, 291,.... Hence there are a 7 = 47 bit strings of length seven that contain three consecutive 0s a) Find a recurrence relation for the number of ways to climb n stairs if the person climbing the stairs can take one stair or two stairs at a time. b) What are the initial conditions? c) In how many ways can this person climb a flight of eight stairs? Let S n denote the number of ways of climbing the stairs. a) Let n. The last step either was a single step, for which there are S n 1 possibilities, or a double step, for which there are S n 2 possibilities. The recurrence is S n = S n 1 + S n 2 for n. b) We have S 1 = 1 and S 2 = 2. You can take two stairs either directly or by taking stair at a time. c) The recurrence gives the Fibonacci sequence 1, 2,, 5, 8, 1, 21, 4, 55,.... Hence there are S 8 = 4 ways to climb a flight of eight stairs A bus driver pays all tolls, using only nickels and dimes, by throwing one coin at a time into the mechanical toll collector. a) Find the recurrence relation for the number of different ways the bus driver can pay a toll of n cents (where the order in which the coins are used matters). b) In how many ways can the driver pay a toll of 45 cents? Let c n denote the number of ways of paying n cents. a) Consider the coin that was paid last. That coin either is a nickel, for which there are c n 5 possibilities, or it is a dime, for which there are c n 10 possibilities. Hence the recurrence relation is c n = c n 5 + c n 10 for n 11. Also, the initial conditions are c 1 = c 2 = c = c 4 = c 6 = c 7 = c 8 = c 9 = 0, c 5 = 1, and c 10 = 2. 2
3 b) This recurrence generates the interspersed Fibonacci sequence 0, 0, 0, 0, 1, 0, 0, 0, 0, 2, 0, 0, 0, 0,, 0, 0, 0, 0, 5, 0, 0, 0, 0, 8, 0, 0, 0, 0, 1, 0, 0, 0, 0, 21, 0, 0, 0, 0, 4, 0, 0, 0, 0, 55,... Hence there are c 45 = 55 ways for the bus driver to pay toll a) Write out all the ways the product x 0 x 1 x 2 x x 4 can be parenthesized to determine the order of multiplication. b) Use the recurrence relation developed in Example 5 to calculate C n, the number of ways to parenthesize the product of five numbers. Verify that you listed the correct number of ways in part (a). c) Check your result in part (b) by finding C 4, using the closed formula for C n in the solution of Example 5. a) There are 14 ways to parenthesize a product of five factors: (((x 0 x 1 ) x 2 ) x ) x 4, ((x 0 (x 1 x 2 )) x ) x 4, ((x 0 x 1 ) (x 2 x )) x 4, (x 0 ((x 1 x 2 ) x )) x 4, (x 0 (x 1 (x 2 x ))) x 4, (x 0 x 1 x 2 ) (x x 4 ), (x 0 x 1 x 2 ) (x x 4 ), (x 0 x 1 ) ((x 2 x ) x 4 ), (x 0 x 1 ) (x 2 (x x 4 )), x 0 (((x 1 x 2 ) x ) x 4 ), x 0 ((x 1 (x 2 x )) x 4 ), x 0 ((x 1 x 2 ) (x x 4 )), x 0 (x 1 ((x 2 x ) x 4 )), x 0 (x 1 (x 2 (x x 4 ))). b) From the recurrence on page 507 we get C 4 = C 0 C +C 1 C 2 +C 2 C 1 +C C 0 = = 14. c) The closed formula for the Catalan numbers is C n = ( 2n n ) /(n+1). Substituting n = 4, we confirm C 4 ( 8 4) /5 = 70/5 = Determine which of these are linear homogeneous recurrence relations with constant coefficients. Also, find the degree of those that are. a) a n = a n 2 b) a n = c) a n = a 2 n 1 d) a n = a n 1 + a n e) a n = a n 1 /n
4 f) a n = a n 1 + a n 2 + n + g) a n = 4a n 2 + 5a n 4 + 9a n 7 a) This is a linear homogeneous recurrence relation with constant coefficients of degree 2. b) This recurrence is not homogeneous. c) This recurrence is not linear. d) This is a linear homogeneous recurrence relation with constant coefficients of degree. e) This recurrence does not have constant coefficients. f) This recurrence is not homogeneous. g) This is a linear homogeneous recurrence relation with constant coefficients of degree A model for the number of lobsters caught per year is based on the assumption that the number of lobsters caught in a year is the average of the number caught in the previous two years. a) Find a recurrence relation for {L n } where L n is the number of lobsters caught in year n, under the assumption of this model. b) Find L n if 100, 000 lobsters were caught in year 1 and 200, 000 lobsters were caught in year 2. a) Since L n is the average of L n 1 and L n 2, the recurrence is L n = 1 2 L n L n 2. b) The characteristic polynomial x 2 x/2 1/2 = 1 2 (2x + 1)(x 1) has the roots 1 and 1/2. Hence there exist real constants c 1 and c 2 such that L n = γ 1 + γ 2 ( 1/2) n. The initial conditions imply the linear relations γ 1 +γ 2 = and γ 1 γ 2 /2 = The solution is γ 1 = / and γ 2 = /, and we conclude c n = ( 1/2)n. The second term converges to zero. Thus, the steady state scenario is that 166, 667 lobsters will be caught every year. 4
5 The Lucas numbers satisfy the recurrence relation L n = L n 1 + L n 2, and the initial conditions L 0 = 2 and L 1 = 1. a) Show that L n = f n 1 + f n+1 for n = 2,,..., where f n is the nth Fibonacci number. b) Find an explicit formula for the Lucas numbers. a) We define a new sequence {M n } by setting M 0 = 2 and M n = f n 1 + f n+1 for n 1. Then M 1 = f 0 + f 2 = 1 and M 2 = f 1 + f = =. The two sequences {M n } and {L n } satisfy the same recurrence, and they satisfy the same initial conditions. Therefore they must be equal. b) The roots of the characteristic polynomial are given by the golden ratio, and we find L n = ( ) n + 2 ( ) 1 5 n for n = 0, 1, 2,, Solve the recurrence relation a n = 6a n 1 12a n 2 + 8a n with a 0 = 5, a 1 = 4 and a 2 = 88. The characteristic polynomial equals x 6x 2 +12x 8 = (x 2). We know from Theorem 4 on page 519 that a n = γ 1 2 n + γ 2 n2 n + γ n 2 2 n for some constants γ 1, γ 2, γ. By substituting n = 0, 1, 2 into this equation, we obtain the linear system γ 1 = 5, 2γ 1 + 2γ 2 + 2γ = 4 and 4γ 1 + 8γ γ = 88. The solution is γ 1 = 5, c 2 = 1/2, c = 1/2, and therefore a n = 5 2 n + n 2 n n 2 2 n 1 for n = 0, 1, 2,, Suppose that there are two goats on an island initially. The number of goats on the island doubles every year by natural reproduction, and some goats are either added or removed each year. a) Construct a recurrence relation for number of goats on the island at the start of the nth year, assuming that during each year an extra 100 goats are put on the island. 5
6 b) Solve the recurrence relation from part (a) to find the number of goats on the island at the start of the nth year. c) Construct a recurrence relation for number of goats on the island at the start of the nth year, assuming that n goats are removed during the nth year for each n. d) Solve the recurrence relation in part (c) to find the number of goats on the island at the start of the nth year. a) Let G n denote the number of goats on the island at the start of the nth year. The recurrence is G n = 2G n for n = 1, 2,.... b) A particular solution to his inhomogenous linear recurrence is 100 (2 n 1). By Theorem 5 on page 521, the solution must have the form G n = 100(2 n 1) + γ2 n. Since G 0 = 2, we see that γ = 2, and hence the number of goats equals G n = 100(2 n 1) + 2 n+1 for n = 0, 1, 2,,.... c) The recurrence is G n = 2G n 1 n for n = 1, 2,..., d) We observe that the recurrence gives the sequence 2,, 4, 5, 6,.... Using mathematical induction, we easily prove that indeed G n = n + 2 for n = 0, 1, 2,, ** Find a closed form for the generating function for the sequence {a n } where a) a n = 1 for all n = 0, 1, 2,... b) a n = 2 n for n = 1, 2,, 4,... and a 0 = 0 c) a n = n 1 for n = 0, 1, 2,... d) a n = 1/(n + 1)! for 0, 1, 2,... e) a n = ( n 2) for n = 0, 1, 2,..., f) a n = ( 10 n+1) for n = 0, 1, 2,... The following generating functions represent the desired sequences: a) 1/(x 1). b) 2x/(1 2x) 6
7 c) (2x 1)/(1 x) 2 d) (e x 1)/x. e) x 2 /(1 x) f) ((x + 1) 10 1)/x For each of these generating functions, provide a closed formula for the sequence it determines. a) (x 2 + 1) b) (x 1) c) 1/(1 2x 2 ) d) x 2 /(1 x) e) x 1 + (1/(1 x)) f) (1 + x )/(1 + x) g) x/(1 + x + x 2 ) h) e x2 1 a) ( n/2) if n is even, and 0 if n is odd b) ( ) n( ) n c) 2 n/2 if n is even, and 0 if n is odd d) ( ) n e) 0 for n = 0, 4 for n = 1, and n for n 2. f) 1 for n = 0, and ( 1) n n for n 1. g) 0 if n 0 (mod ), 1 if n 1 (mod ), 1 if n 2 (mod ). h) 2 n/2 /(n/2)! if n is even and positive, and 0 otherwise Use generating functions to determine the number of different ways 12 identical action figures can be given to five children so that each child receives at most three action figures. This is the coefficient of x 12 in (1 + x + x 2 + x ) 5. It is found to be 5. So, there are 5 ways of distributing the 12 action figures What is the generating function for the sequence {c k }, where c k represents the number of ways to make change for k pesos using bills worth 10 pesos, 20 pesos, 50 pesos and 100 pesos? 7
8 The generating function for making change with these bills is x k = k=0 1 (1 x 10 )(1 x 20 )(1 x 50 )(1 x 100 ) Give a combinatorial interpretation of the coefficient of x 6 in the expansion (1 + x + x 2 + x + ) n. Use this interpretation to find this number. This is the number of ways of giving n action figures to six children. While the action figures are indistinguishable, the children are very precious and thus we consider them to be distinguishable. More abstractly, that coefficient counts the ncombinations of a set of 6 elements with repetition allowed. The number equals ( ) n Use generating functions to solve the recurrence relation a k = a k 1 + 2a k k with initial conditions a 0 = 4 and a 1 = 12. From the initial conditions and the recurrence relation, we find that the generating function G(x) = k=0 a kx k satisfies the identity G(x) 4 12x = x(g(x) 4) + 2x 2 G(x) + We solve this equation for G(x) to find 1 1 2x 1 2x. G(x) = 4 (1 x 2 ) (1 2x) 2 (1 + x) = x + 24x x + 120x 4 + 8
Discrete Mathematics: Homework 7 solution. Due: 2011.6.03
EE 2060 Discrete Mathematics spring 2011 Discrete Mathematics: Homework 7 solution Due: 2011.6.03 1. Let a n = 2 n + 5 3 n for n = 0, 1, 2,... (a) (2%) Find a 0, a 1, a 2, a 3 and a 4. (b) (2%) Show that
More informationMath 55: Discrete Mathematics
Math 55: Discrete Mathematics UC Berkeley, Fall 2011 Homework # 5, due Wednesday, February 22 5.1.4 Let P (n) be the statement that 1 3 + 2 3 + + n 3 = (n(n + 1)/2) 2 for the positive integer n. a) What
More informationHOMEWORK 5 SOLUTIONS. n!f n (1) lim. ln x n! + xn x. 1 = G n 1 (x). (2) k + 1 n. (n 1)!
Math 7 Fall 205 HOMEWORK 5 SOLUTIONS Problem. 2008 B2 Let F 0 x = ln x. For n 0 and x > 0, let F n+ x = 0 F ntdt. Evaluate n!f n lim n ln n. By directly computing F n x for small n s, we obtain the following
More information3 0 + 4 + 3 1 + 1 + 3 9 + 6 + 3 0 + 1 + 3 0 + 1 + 3 2 mod 10 = 4 + 3 + 1 + 27 + 6 + 1 + 1 + 6 mod 10 = 49 mod 10 = 9.
SOLUTIONS TO HOMEWORK 2  MATH 170, SUMMER SESSION I (2012) (1) (Exercise 11, Page 107) Which of the following is the correct UPC for Progresso minestrone soup? Show why the other numbers are not valid
More informationSample Induction Proofs
Math 3 Worksheet: Induction Proofs III, Sample Proofs A.J. Hildebrand Sample Induction Proofs Below are model solutions to some of the practice problems on the induction worksheets. The solutions given
More informationAssignment 5  Due Friday March 6
Assignment 5  Due Friday March 6 (1) Discovering Fibonacci Relationships By experimenting with numerous examples in search of a pattern, determine a simple formula for (F n+1 ) 2 + (F n ) 2 that is, a
More information4/1/2017. PS. Sequences and Series FROM 9.2 AND 9.3 IN THE BOOK AS WELL AS FROM OTHER SOURCES. TODAY IS NATIONAL MANATEE APPRECIATION DAY
PS. Sequences and Series FROM 9.2 AND 9.3 IN THE BOOK AS WELL AS FROM OTHER SOURCES. TODAY IS NATIONAL MANATEE APPRECIATION DAY 1 Oh the things you should learn How to recognize and write arithmetic sequences
More informationMathematical Induction. Lecture 1011
Mathematical Induction Lecture 1011 Menu Mathematical Induction Strong Induction Recursive Definitions Structural Induction Climbing an Infinite Ladder Suppose we have an infinite ladder: 1. We can reach
More informationZeros of Polynomial Functions
Review: Synthetic Division Find (x 25x  5x 3 + x 4 ) (5 + x). Factor Theorem Solve 2x 35x 2 + x + 2 =0 given that 2 is a zero of f(x) = 2x 35x 2 + x + 2. Zeros of Polynomial Functions Introduction
More informationVieta s Formulas and the Identity Theorem
Vieta s Formulas and the Identity Theorem This worksheet will work through the material from our class on 3/21/2013 with some examples that should help you with the homework The topic of our discussion
More informationJUST THE MATHS UNIT NUMBER 1.8. ALGEBRA 8 (Polynomials) A.J.Hobson
JUST THE MATHS UNIT NUMBER 1.8 ALGEBRA 8 (Polynomials) by A.J.Hobson 1.8.1 The factor theorem 1.8.2 Application to quadratic and cubic expressions 1.8.3 Cubic equations 1.8.4 Long division of polynomials
More informationSolving Rational Equations
Lesson M Lesson : Student Outcomes Students solve rational equations, monitoring for the creation of extraneous solutions. Lesson Notes In the preceding lessons, students learned to add, subtract, multiply,
More informationCHAPTER 5. Number Theory. 1. Integers and Division. Discussion
CHAPTER 5 Number Theory 1. Integers and Division 1.1. Divisibility. Definition 1.1.1. Given two integers a and b we say a divides b if there is an integer c such that b = ac. If a divides b, we write a
More information1.2. Successive Differences
1. An Application of Inductive Reasoning: Number Patterns In the previous section we introduced inductive reasoning, and we showed how it can be applied in predicting what comes next in a list of numbers
More informationPractice Problems for Homework #8. Markov Chains. Read Sections 7.17.3. Solve the practice problems below.
Practice Problems for Homework #8. Markov Chains. Read Sections 7.17.3 Solve the practice problems below. Open Homework Assignment #8 and solve the problems. 1. (10 marks) A computer system can operate
More informationFACTORING POLYNOMIALS IN THE RING OF FORMAL POWER SERIES OVER Z
FACTORING POLYNOMIALS IN THE RING OF FORMAL POWER SERIES OVER Z DANIEL BIRMAJER, JUAN B GIL, AND MICHAEL WEINER Abstract We consider polynomials with integer coefficients and discuss their factorization
More informationZero: If P is a polynomial and if c is a number such that P (c) = 0 then c is a zero of P.
MATH 11011 FINDING REAL ZEROS KSU OF A POLYNOMIAL Definitions: Polynomial: is a function of the form P (x) = a n x n + a n 1 x n 1 + + a x + a 1 x + a 0. The numbers a n, a n 1,..., a 1, a 0 are called
More informationReal Roots of Univariate Polynomials with Real Coefficients
Real Roots of Univariate Polynomials with Real Coefficients mostly written by Christina Hewitt March 22, 2012 1 Introduction Polynomial equations are used throughout mathematics. When solving polynomials
More informationEquations, Inequalities & Partial Fractions
Contents Equations, Inequalities & Partial Fractions.1 Solving Linear Equations 2.2 Solving Quadratic Equations 1. Solving Polynomial Equations 1.4 Solving Simultaneous Linear Equations 42.5 Solving Inequalities
More information3.1. Solving linear equations. Introduction. Prerequisites. Learning Outcomes. Learning Style
Solving linear equations 3.1 Introduction Many problems in engineering reduce to the solution of an equation or a set of equations. An equation is a type of mathematical expression which contains one or
More informationH/wk 13, Solutions to selected problems
H/wk 13, Solutions to selected problems Ch. 4.1, Problem 5 (a) Find the number of roots of x x in Z 4, Z Z, any integral domain, Z 6. (b) Find a commutative ring in which x x has infinitely many roots.
More informationFactoring Cubic Polynomials
Factoring Cubic Polynomials Robert G. Underwood 1. Introduction There are at least two ways in which using the famous Cardano formulas (1545) to factor cubic polynomials present more difficulties than
More informationReading 13 : Finite State Automata and Regular Expressions
CS/Math 24: Introduction to Discrete Mathematics Fall 25 Reading 3 : Finite State Automata and Regular Expressions Instructors: Beck Hasti, Gautam Prakriya In this reading we study a mathematical model
More information3.2. Solving quadratic equations. Introduction. Prerequisites. Learning Outcomes. Learning Style
Solving quadratic equations 3.2 Introduction A quadratic equation is one which can be written in the form ax 2 + bx + c = 0 where a, b and c are numbers and x is the unknown whose value(s) we wish to find.
More informationInteger roots of quadratic and cubic polynomials with integer coefficients
Integer roots of quadratic and cubic polynomials with integer coefficients Konstantine Zelator Mathematics, Computer Science and Statistics 212 Ben Franklin Hall Bloomsburg University 400 East Second Street
More informationSequences. A sequence is a list of numbers, or a pattern, which obeys a rule.
Sequences A sequence is a list of numbers, or a pattern, which obeys a rule. Each number in a sequence is called a term. ie the fourth term of the sequence 2, 4, 6, 8, 10, 12... is 8, because it is the
More informationMATH 4330/5330, Fourier Analysis Section 11, The Discrete Fourier Transform
MATH 433/533, Fourier Analysis Section 11, The Discrete Fourier Transform Now, instead of considering functions defined on a continuous domain, like the interval [, 1) or the whole real line R, we wish
More informationa 1 x + a 0 =0. (3) ax 2 + bx + c =0. (4)
ROOTS OF POLYNOMIAL EQUATIONS In this unit we discuss polynomial equations. A polynomial in x of degree n, where n 0 is an integer, is an expression of the form P n (x) =a n x n + a n 1 x n 1 + + a 1 x
More informationIntroduction. Appendix D Mathematical Induction D1
Appendix D Mathematical Induction D D Mathematical Induction Use mathematical induction to prove a formula. Find a sum of powers of integers. Find a formula for a finite sum. Use finite differences to
More informationContinued Fractions and the Euclidean Algorithm
Continued Fractions and the Euclidean Algorithm Lecture notes prepared for MATH 326, Spring 997 Department of Mathematics and Statistics University at Albany William F Hammond Table of Contents Introduction
More informationSection IV.1: Recursive Algorithms and Recursion Trees
Section IV.1: Recursive Algorithms and Recursion Trees Definition IV.1.1: A recursive algorithm is an algorithm that solves a problem by (1) reducing it to an instance of the same problem with smaller
More informationRecursive Algorithms. Recursion. Motivating Example Factorial Recall the factorial function. { 1 if n = 1 n! = n (n 1)! if n > 1
Recursion Slides by Christopher M Bourke Instructor: Berthe Y Choueiry Fall 007 Computer Science & Engineering 35 Introduction to Discrete Mathematics Sections 717 of Rosen cse35@cseunledu Recursive Algorithms
More information5.1 Radical Notation and Rational Exponents
Section 5.1 Radical Notation and Rational Exponents 1 5.1 Radical Notation and Rational Exponents We now review how exponents can be used to describe not only powers (such as 5 2 and 2 3 ), but also roots
More informationIndiana State Core Curriculum Standards updated 2009 Algebra I
Indiana State Core Curriculum Standards updated 2009 Algebra I Strand Description Boardworks High School Algebra presentations Operations With Real Numbers Linear Equations and A1.1 Students simplify and
More informationMath Workshop October 2010 Fractions and Repeating Decimals
Math Workshop October 2010 Fractions and Repeating Decimals This evening we will investigate the patterns that arise when converting fractions to decimals. As an example of what we will be looking at,
More informationk, then n = p2α 1 1 pα k
Powers of Integers An integer n is a perfect square if n = m for some integer m. Taking into account the prime factorization, if m = p α 1 1 pα k k, then n = pα 1 1 p α k k. That is, n is a perfect square
More informationFibonacci Numbers and Greatest Common Divisors. The Finonacci numbers are the numbers in the sequence 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,...
Fibonacci Numbers and Greatest Common Divisors The Finonacci numbers are the numbers in the sequence 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,.... After starting with two 1s, we get each Fibonacci number
More informationTaylor and Maclaurin Series
Taylor and Maclaurin Series In the preceding section we were able to find power series representations for a certain restricted class of functions. Here we investigate more general problems: Which functions
More informationCONTRIBUTIONS TO ZERO SUM PROBLEMS
CONTRIBUTIONS TO ZERO SUM PROBLEMS S. D. ADHIKARI, Y. G. CHEN, J. B. FRIEDLANDER, S. V. KONYAGIN AND F. PAPPALARDI Abstract. A prototype of zero sum theorems, the well known theorem of Erdős, Ginzburg
More informationPolynomials. Dr. philippe B. laval Kennesaw State University. April 3, 2005
Polynomials Dr. philippe B. laval Kennesaw State University April 3, 2005 Abstract Handout on polynomials. The following topics are covered: Polynomial Functions End behavior Extrema Polynomial Division
More informationCONTINUED FRACTIONS AND PELL S EQUATION. Contents 1. Continued Fractions 1 2. Solution to Pell s Equation 9 References 12
CONTINUED FRACTIONS AND PELL S EQUATION SEUNG HYUN YANG Abstract. In this REU paper, I will use some important characteristics of continued fractions to give the complete set of solutions to Pell s equation.
More information9.2 Summation Notation
9. Summation Notation 66 9. Summation Notation In the previous section, we introduced sequences and now we shall present notation and theorems concerning the sum of terms of a sequence. We begin with a
More information0.8 Rational Expressions and Equations
96 Prerequisites 0.8 Rational Expressions and Equations We now turn our attention to rational expressions  that is, algebraic fractions  and equations which contain them. The reader is encouraged to
More information3.3. Solving Polynomial Equations. Introduction. Prerequisites. Learning Outcomes
Solving Polynomial Equations 3.3 Introduction Linear and quadratic equations, dealt within Sections 3.1 and 3.2, are members of a class of equations, called polynomial equations. These have the general
More informationWe can express this in decimal notation (in contrast to the underline notation we have been using) as follows: 9081 + 900b + 90c = 9001 + 100c + 10b
In this session, we ll learn how to solve problems related to place value. This is one of the fundamental concepts in arithmetic, something every elementary and middle school mathematics teacher should
More informationFactoring Polynomials
Factoring Polynomials Sue Geller June 19, 2006 Factoring polynomials over the rational numbers, real numbers, and complex numbers has long been a standard topic of high school algebra. With the advent
More informationRolle s Theorem. q( x) = 1
Lecture 1 :The Mean Value Theorem We know that constant functions have derivative zero. Is it possible for a more complicated function to have derivative zero? In this section we will answer this question
More informationCONTINUED FRACTIONS AND FACTORING. Niels Lauritzen
CONTINUED FRACTIONS AND FACTORING Niels Lauritzen ii NIELS LAURITZEN DEPARTMENT OF MATHEMATICAL SCIENCES UNIVERSITY OF AARHUS, DENMARK EMAIL: niels@imf.au.dk URL: http://home.imf.au.dk/niels/ Contents
More informationMath Review. for the Quantitative Reasoning Measure of the GRE revised General Test
Math Review for the Quantitative Reasoning Measure of the GRE revised General Test www.ets.org Overview This Math Review will familiarize you with the mathematical skills and concepts that are important
More informationSOLVING POLYNOMIAL EQUATIONS
C SOLVING POLYNOMIAL EQUATIONS We will assume in this appendix that you know how to divide polynomials using long division and synthetic division. If you need to review those techniques, refer to an algebra
More informationAnswer: (a) Since we cannot repeat men on the committee, and the order we select them in does not matter, ( )
1. (Chapter 1 supplementary, problem 7): There are 12 men at a dance. (a) In how many ways can eight of them be selected to form a cleanup crew? (b) How many ways are there to pair off eight women at the
More informationCatalan Numbers. Thomas A. Dowling, Department of Mathematics, Ohio State Uni versity.
7 Catalan Numbers Thomas A. Dowling, Department of Mathematics, Ohio State Uni Author: versity. Prerequisites: The prerequisites for this chapter are recursive definitions, basic counting principles,
More informationContinued Fractions. Darren C. Collins
Continued Fractions Darren C Collins Abstract In this paper, we discuss continued fractions First, we discuss the definition and notation Second, we discuss the development of the subject throughout history
More information3. Mathematical Induction
3. MATHEMATICAL INDUCTION 83 3. Mathematical Induction 3.1. First Principle of Mathematical Induction. Let P (n) be a predicate with domain of discourse (over) the natural numbers N = {0, 1,,...}. If (1)
More information6 EXTENDING ALGEBRA. 6.0 Introduction. 6.1 The cubic equation. Objectives
6 EXTENDING ALGEBRA Chapter 6 Extending Algebra Objectives After studying this chapter you should understand techniques whereby equations of cubic degree and higher can be solved; be able to factorise
More information5 Numerical Differentiation
D. Levy 5 Numerical Differentiation 5. Basic Concepts This chapter deals with numerical approximations of derivatives. The first questions that comes up to mind is: why do we need to approximate derivatives
More informationLecture 1: Course overview, circuits, and formulas
Lecture 1: Course overview, circuits, and formulas Topics in Complexity Theory and Pseudorandomness (Spring 2013) Rutgers University Swastik Kopparty Scribes: John Kim, Ben Lund 1 Course Information Swastik
More informationMath 115 Spring 2011 Written Homework 5 Solutions
. Evaluate each series. a) 4 7 0... 55 Math 5 Spring 0 Written Homework 5 Solutions Solution: We note that the associated sequence, 4, 7, 0,..., 55 appears to be an arithmetic sequence. If the sequence
More informationSecond Order Linear Nonhomogeneous Differential Equations; Method of Undetermined Coefficients. y + p(t) y + q(t) y = g(t), g(t) 0.
Second Order Linear Nonhomogeneous Differential Equations; Method of Undetermined Coefficients We will now turn our attention to nonhomogeneous second order linear equations, equations with the standard
More informationCollatz Sequence. Fibbonacci Sequence. n is even; Recurrence Relation: a n+1 = a n + a n 1.
Fibonacci Roulette In this game you will be constructing a recurrence relation, that is, a sequence of numbers where you find the next number by looking at the previous numbers in the sequence. Your job
More informationFull and Complete Binary Trees
Full and Complete Binary Trees Binary Tree Theorems 1 Here are two important types of binary trees. Note that the definitions, while similar, are logically independent. Definition: a binary tree T is full
More informationHomework until Test #2
MATH31: Number Theory Homework until Test # Philipp BRAUN Section 3.1 page 43, 1. It has been conjectured that there are infinitely many primes of the form n. Exhibit five such primes. Solution. Five such
More informationU.C. Berkeley CS276: Cryptography Handout 0.1 Luca Trevisan January, 2009. Notes on Algebra
U.C. Berkeley CS276: Cryptography Handout 0.1 Luca Trevisan January, 2009 Notes on Algebra These notes contain as little theory as possible, and most results are stated without proof. Any introductory
More informationNotes on Determinant
ENGG2012B Advanced Engineering Mathematics Notes on Determinant Lecturer: Kenneth Shum Lecture 918/02/2013 The determinant of a system of linear equations determines whether the solution is unique, without
More information1 Inner Products and Norms on Real Vector Spaces
Math 373: Principles Techniques of Applied Mathematics Spring 29 The 2 Inner Product 1 Inner Products Norms on Real Vector Spaces Recall that an inner product on a real vector space V is a function from
More informationStanford Math Circle: Sunday, May 9, 2010 SquareTriangular Numbers, Pell s Equation, and Continued Fractions
Stanford Math Circle: Sunday, May 9, 00 SquareTriangular Numbers, Pell s Equation, and Continued Fractions Recall that triangular numbers are numbers of the form T m = numbers that can be arranged in
More informationMATH 289 PROBLEM SET 4: NUMBER THEORY
MATH 289 PROBLEM SET 4: NUMBER THEORY 1. The greatest common divisor If d and n are integers, then we say that d divides n if and only if there exists an integer q such that n = qd. Notice that if d divides
More informationHomework # 3 Solutions
Homework # 3 Solutions February, 200 Solution (2.3.5). Noting that and ( + 3 x) x 8 = + 3 x) by Equation (2.3.) x 8 x 8 = + 3 8 by Equations (2.3.7) and (2.3.0) =3 x 8 6x2 + x 3 ) = 2 + 6x 2 + x 3 x 8
More informationTAKEAWAY GAMES. ALLEN J. SCHWENK California Institute of Technology, Pasadena, California INTRODUCTION
TAKEAWAY GAMES ALLEN J. SCHWENK California Institute of Technology, Pasadena, California L INTRODUCTION Several games of Tf takeaway?f have become popular. The purpose of this paper is to determine the
More informationPUTNAM TRAINING POLYNOMIALS. Exercises 1. Find a polynomial with integral coefficients whose zeros include 2 + 5.
PUTNAM TRAINING POLYNOMIALS (Last updated: November 17, 2015) Remark. This is a list of exercises on polynomials. Miguel A. Lerma Exercises 1. Find a polynomial with integral coefficients whose zeros include
More informationThe Heat Equation. Lectures INF2320 p. 1/88
The Heat Equation Lectures INF232 p. 1/88 Lectures INF232 p. 2/88 The Heat Equation We study the heat equation: u t = u xx for x (,1), t >, (1) u(,t) = u(1,t) = for t >, (2) u(x,) = f(x) for x (,1), (3)
More informationMATH10212 Linear Algebra. Systems of Linear Equations. Definition. An ndimensional vector is a row or a column of n numbers (or letters): a 1.
MATH10212 Linear Algebra Textbook: D. Poole, Linear Algebra: A Modern Introduction. Thompson, 2006. ISBN 0534405967. Systems of Linear Equations Definition. An ndimensional vector is a row or a column
More informationSolutions to Homework 6 Mathematics 503 Foundations of Mathematics Spring 2014
Solutions to Homework 6 Mathematics 503 Foundations of Mathematics Spring 2014 3.4: 1. If m is any integer, then m(m + 1) = m 2 + m is the product of m and its successor. That it to say, m 2 + m is the
More informationLEARNING OBJECTIVES FOR THIS CHAPTER
CHAPTER 2 American mathematician Paul Halmos (1916 2006), who in 1942 published the first modern linear algebra book. The title of Halmos s book was the same as the title of this chapter. FiniteDimensional
More informationLecture 13  Basic Number Theory.
Lecture 13  Basic Number Theory. Boaz Barak March 22, 2010 Divisibility and primes Unless mentioned otherwise throughout this lecture all numbers are nonnegative integers. We say that A divides B, denoted
More informationMath 319 Problem Set #3 Solution 21 February 2002
Math 319 Problem Set #3 Solution 21 February 2002 1. ( 2.1, problem 15) Find integers a 1, a 2, a 3, a 4, a 5 such that every integer x satisfies at least one of the congruences x a 1 (mod 2), x a 2 (mod
More informationBX in ( u, v) basis in two ways. On the one hand, AN = u+
1. Let f(x) = 1 x +1. Find f (6) () (the value of the sixth derivative of the function f(x) at zero). Answer: 7. We expand the given function into a Taylor series at the point x = : f(x) = 1 x + x 4 x
More information= 2 + 1 2 2 = 3 4, Now assume that P (k) is true for some fixed k 2. This means that
Instructions. Answer each of the questions on your own paper, and be sure to show your work so that partial credit can be adequately assessed. Credit will not be given for answers (even correct ones) without
More informationDiscrete Math in Computer Science Homework 7 Solutions (Max Points: 80)
Discrete Math in Computer Science Homework 7 Solutions (Max Points: 80) CS 30, Winter 2016 by Prasad Jayanti 1. (10 points) Here is the famous Monty Hall Puzzle. Suppose you are on a game show, and you
More information2.5 Zeros of a Polynomial Functions
.5 Zeros of a Polynomial Functions Section.5 Notes Page 1 The first rule we will talk about is Descartes Rule of Signs, which can be used to determine the possible times a graph crosses the xaxis and
More informationMATHEMATICAL INDUCTION. Mathematical Induction. This is a powerful method to prove properties of positive integers.
MATHEMATICAL INDUCTION MIGUEL A LERMA (Last updated: February 8, 003) Mathematical Induction This is a powerful method to prove properties of positive integers Principle of Mathematical Induction Let P
More informationProperties of sequences Since a sequence is a special kind of function it has analogous properties to functions:
Sequences and Series A sequence is a special kind of function whose domain is N  the set of natural numbers. The range of a sequence is the collection of terms that make up the sequence. Just as the word
More informationTHE DYING FIBONACCI TREE. 1. Introduction. Consider a tree with two types of nodes, say A and B, and the following properties:
THE DYING FIBONACCI TREE BERNHARD GITTENBERGER 1. Introduction Consider a tree with two types of nodes, say A and B, and the following properties: 1. Let the root be of type A.. Each node of type A produces
More informationGenerating Functions Count
2 Generating Functions Count 2.1 Counting from Polynomials to Power Series Consider the outcomes when a pair of dice are thrown and our interest is the sum of the numbers showing. One way to model the
More informationPOLYNOMIAL FUNCTIONS
POLYNOMIAL FUNCTIONS Polynomial Division.. 314 The Rational Zero Test.....317 Descarte s Rule of Signs... 319 The Remainder Theorem.....31 Finding all Zeros of a Polynomial Function.......33 Writing a
More information6.3 Conditional Probability and Independence
222 CHAPTER 6. PROBABILITY 6.3 Conditional Probability and Independence Conditional Probability Two cubical dice each have a triangle painted on one side, a circle painted on two sides and a square painted
More informationON FIBONACCI NUMBERS WITH FEW PRIME DIVISORS
ON FIBONACCI NUMBERS WITH FEW PRIME DIVISORS YANN BUGEAUD, FLORIAN LUCA, MAURICE MIGNOTTE, SAMIR SIKSEK Abstract If n is a positive integer, write F n for the nth Fibonacci number, and ω(n) for the number
More informationRow Echelon Form and Reduced Row Echelon Form
These notes closely follow the presentation of the material given in David C Lay s textbook Linear Algebra and its Applications (3rd edition) These notes are intended primarily for inclass presentation
More informationminimal polyonomial Example
Minimal Polynomials Definition Let α be an element in GF(p e ). We call the monic polynomial of smallest degree which has coefficients in GF(p) and α as a root, the minimal polyonomial of α. Example: We
More informationZeros of Polynomial Functions
Zeros of Polynomial Functions The Rational Zero Theorem If f (x) = a n x n + a n1 x n1 + + a 1 x + a 0 has integer coefficients and p/q (where p/q is reduced) is a rational zero, then p is a factor of
More information4.5 Chebyshev Polynomials
230 CHAP. 4 INTERPOLATION AND POLYNOMIAL APPROXIMATION 4.5 Chebyshev Polynomials We now turn our attention to polynomial interpolation for f (x) over [ 1, 1] based on the nodes 1 x 0 < x 1 < < x N 1. Both
More informationn k=1 k=0 1/k! = e. Example 6.4. The series 1/k 2 converges in R. Indeed, if s n = n then k=1 1/k, then s 2n s n = 1 n + 1 +...
6 Series We call a normed space (X, ) a Banach space provided that every Cauchy sequence (x n ) in X converges. For example, R with the norm = is an example of Banach space. Now let (x n ) be a sequence
More informationReducibility of Second Order Differential Operators with Rational Coefficients
Reducibility of Second Order Differential Operators with Rational Coefficients Joseph Geisbauer University of ArkansasFort Smith Advisor: Dr. Jill Guerra May 10, 2007 1. INTRODUCTION In this paper we
More informationMath 181 Handout 16. Rich Schwartz. March 9, 2010
Math 8 Handout 6 Rich Schwartz March 9, 200 The purpose of this handout is to describe continued fractions and their connection to hyperbolic geometry. The Gauss Map Given any x (0, ) we define γ(x) =
More informationSECTION 102 Mathematical Induction
73 0 Sequences and Series 6. Approximate e 0. using the first five terms of the series. Compare this approximation with your calculator evaluation of e 0.. 6. Approximate e 0.5 using the first five terms
More informationThis unit will lay the groundwork for later units where the students will extend this knowledge to quadratic and exponential functions.
Algebra I Overview View unit yearlong overview here Many of the concepts presented in Algebra I are progressions of concepts that were introduced in grades 6 through 8. The content presented in this course
More informationAlgebra Unpacked Content For the new Common Core standards that will be effective in all North Carolina schools in the 201213 school year.
This document is designed to help North Carolina educators teach the Common Core (Standard Course of Study). NCDPI staff are continually updating and improving these tools to better serve teachers. Algebra
More informationExamples of Functions
Examples of Functions In this document is provided examples of a variety of functions. The purpose is to convince the beginning student that functions are something quite different than polynomial equations.
More informationThe Characteristic Polynomial
Physics 116A Winter 2011 The Characteristic Polynomial 1 Coefficients of the characteristic polynomial Consider the eigenvalue problem for an n n matrix A, A v = λ v, v 0 (1) The solution to this problem
More informationLecture Notes on Polynomials
Lecture Notes on Polynomials Arne Jensen Department of Mathematical Sciences Aalborg University c 008 Introduction These lecture notes give a very short introduction to polynomials with real and complex
More information