Solved: Use mathematical induction to show that (cos x + i

a) Can you use the principle of mathematical induction to find a formula for the sum of the first n terms of a sequence? b) Can you use the principle of mathematical induction to determine whether a given formula for the sum of the first n terms of a sequence is correct? c) Find a formula for the sum of the first n even positive integers, and prove it using mathematical induction.

a) For which positive integers n is l ln + 17 ::: 2n ? b) Prove the conjecture you made in part (a) using mathematical induction.

a) Which amounts of postage can be formed using only 5-cent and 9-cent stamps? b) Prove the conjecture you made using mathematical induction. c) Prove the conjecture you made using strong induction. d) Find a proof of your conjecture different from the ones you gave in (b) and (c).

Give two different examples. of proofs that use strong induction

a) State the well-ordering property for the set of positive integers. b) Use this property to show that every positive integer can be written as the product of primes.

a) Explain why a function is well-defined ifit is defined recursively by specifYing f(l) and a rule for finding f(n) from f(n - 1). b) Provide a recursive definition of the function f(n) = (n + I)!.

a) Give a recursive definition of the Fibonacci numbers. b) Show that fn > a n-2 whenever n ::: 3, where fn is the nth term of the Fibonacci sequence and a = (l + ./5)/2.

a) Explain why a sequence an is well defined if it is defined recursively by specifYing a I and a2 and a rule for finding an from aI , a2, ... , an-I for n = 3, 4, 5, .... b) Find the value of an if al = 1, a2 = 2, and an = an-I + an-2 + ... + al , for n = 3, 4, 5, ....

Give two examples of how well-formed formulae are defined recursively for different sets of elements and operators.

a) Give a recursive definition ofthe length of a string. b) Use the recursive definition from part (a) and structural induction to prove that l(xy) = l(x) + l(y).

a) What is a recursive algorithm? b) Describe a recursive algorithm for computing the sum of n numbers in a sequence.

Describe a recursive algorithm for computing the greatest common divisor of two positive integers.

a) Describe the merge sort algorithm. b) Use the merge sort algorithm to put the list 4, 10, 1, 5, 3, 8, 7, 2, 6, 9 in increasing order. c) Give a big-O estimate for the number of comparisons used by the merge sort.

a) Does testing a computer program to see whether it produces the correct output for certain input values verifY that the program always produces the correct output? b) Does showing that a computer program is partially correct with respect to an initial assertion and a final assertion verifY that the program always produces the correct output? If not, what else is needed?

What techniques can you use to show that a long computer program is partially correct with respect to an initial assertion and a final assertion?

What is a loop invariant? How is a loop invariant used?

Use mathematical induction to show that + + 3 9 1.. + ... + 1.. - 1 - 1.. whenever n is a positive 27 3" - 3" integer.

Use mathematical induction to show that 1 3 + 33 + 53 + ... + (2n + 1)3 = (n + 1)2 (2n2 + 4n + 1) whenever n is a positive integer.

Use mathematical induction to show that 1 . 2 0 + 2 . 2 1 + 3 . 2 2 + ... + n 2n-1 = (n - 1) 2n + 1 whenever n isa positive integer.

Use mathematical induction to show that -1 l i n 1 . 3 3 + -. 5 + ... + (2n - 1 )(2n + 1) =--2n + 1 whenever n is a positive integer.

Show that -1 l i n 1 4 + -47 + ... + (3n - 2)(3n + l) =--3n +l whenever n is a positive integer.

Use mathematical induction to show that 2 n > n 2 + n whenever n is an integer greater than 4

Use mathematical induction to show that 2 n > n 3 whenever n is an integer greater than 9.

Find an integer N such that 2 n > n 4 whenever n is greater than N. Prove that your result is correct using mathematical induction.

Use mathematical induction to prove that a - b is a factor of a n - bn whenever n is a positive integer.

Use mathematical induction to prove that 9 divides n 3 + (n + 1)3 + (n + 2)3 whenever n is a nonnegative integer.

Use mathematical induction to prove this formula for the sum of the terms of an arithmetic progression. a + (a + d) + ... + (a + nd) = (n + 1)(2a + nd)/2

Suppose that aj == bj (mod m) for j = 1 , 2, ... , n. Use mathematical induction to prove that n n a) L aj == L bj (mod m). j = 1 j =1 n n b) n aj == n bj (mod m).

Show that if n is a positive integer, then n k + 4 n(3n + 7) Lk= I k(k + 1)(k + 2) = 2(n + 1)(n + 2)

For which positive integers n is n + 6 < (n2 - 8n)/16? Prove your answer using mathematical induction

(Requires calculus) Suppose that I(x) = and g(x) = xeX Use mathematical induction together with the product rule and the fact that I'(x) = to prove that g(n )(x) = (x + n)eX whenever n is a positive integer.

(Requires calculus) Suppose that I(x) = and g(x) = eCx, where c is a constant. Use mathematical induction together with the chain rule and the fact that I' (x) = to prove that g(n ) = c n ecx whenever n is a positive integer.

Determine which Fibonacci numbers are even, and use a form of mathematical induction to prove your conjecture

Determine which Fibonacci numbers are divisible by 3. Use a form of mathematical induction to prove your conjecture.

Provethat lkln + lk+l /n+1 = In+k+1 for all nonnegative integers n, where k is a nonnegative integer and J; denotes the ith Fibonacci number.

Show that In + In+2 = In+1 whenever n is a positive integer, where J; and Ii are the ith Fibonacci number and ith Lucas number, respectively.

Show that 15 + It + ... + I = Inln+1 + 2 whenever n is a nonnegative integer and Ii is the ith Lucas number.

Use mathematical induction to show that the product of any n consecutive positive integers is divisible by n! . [Hint: Use the identity m(m + 1) (m +n - 1)/n! = (m - l)m(m + 1) (m + n - 2)/n! + m(m+ 1) (m + n - 2)/(n - I)! .]

Use mathematical induction to show that (cos x + i sin x)n =-cos nx + i sin nx whenever n is a positive integer. (Here i is the square root of - 1 .) [Hint: Use the identities cos( a + b) = cos a cos b - sin a sin b and sin(a + b) = sin a cos b + cos a sin b.]

Use mathematical induction to show that LJ = I cos j X = cos[(n + l )x /2] sin(nx /2)/ sin(x /2) whenever n is a positive integer and sin(x /2) :/= O.

Use mathematical induction to prove that LJ=I j 2 2 j = n 2 2 n+1 - n2n+2 + 3 2 n+1 - 6 for every positive integer n.

(Requires calculus) Suppose that the sequence XI , X2, , Xn, . is recursively defined by XI = 0 and Xn+l = "';xn + 6. a) Use mathematical induction to show that XI < X2 < ... < Xn < ... , that is, the sequence {xn} is monotonically increasing. b) Use mathematical induction to prove that Xn < 3 for n = 1 , 2, .... c) Show that limn-HXl Xn = 3.

Show if n is a positive integer with n :::: 2, then t 1 _ = (n - 1)(3n + 2) j=2 j 2 - 1 4n(n + 1).

Use mathematical induction to prove Theorem 1 in Section 3.6, that is, show if b is a positive integer, b > 1, and n is a positive integer, then n can be expressed uniquely in the form n = akb k + ak_Ibk-1 + ... + alb + ao.

A lattice point in the plane is a point (x , y) where both x and y are integers. Use mathematical induction to show that at least n + 1 straight lines are needed to ensure that every lattice point (x, y) with x :::: 0, y :::: 0, and x + y :'S n lies on one of these lines.

(Requires calculus) Use mathematical induction and the product rule to show that if n is a positive integer and f, (x), fz(x), ... , fn(x), are all differentiable functions, then (f,(x)fz(x) fn(x))' f, (x)fz(x) fn(x) = f{ (x) + f (x) + ... + f (x) f, (x) fz(x) fn(x)

(Requires material in Section 3.7) Suppose that B = MAM-' , where A and B are n x n matrices and M is invertible. Show that B k = MAkM-' for all positive integers k.

Use mathematical induction to show that if you draw lines in the plane you only need two colors to color the regions formed so that no two regions that have an edge in common have a common color

Show that n! can be represented as the sum of n of its distinct positive divisors whenever n 3. [Hint: Use inductive loading. First try to prove this result using mathematical induction. By examining where your proof fails, find a stronger statement that you can easily prove using mathematical induction.]

Use mathematical induction to prove that ifx" X2 , , Xn are positive real numbers with n 2, then

Use mathematical induction to prove that ifn people stand in a line, where n is a positive integer, and ifthe first person in the line is a woman and the last person in line is a man, then somewhere in the line there is a woman directly in front of a man.

Suppose that for every pair of cities in a country there is a direct one-way road connecting them in one direction or the other. Use mathematical induction to show that there is a city that can be reached from every other city either directly or via exactly one other city.

Use mathematical induction to show that when n circles divide the plane into regions, these regions can be colored with two different colors such that no regions with a common boundary are colored the same.

Suppose that among a group of cars on a circular track there is enough fuel for one car to complete a lap. Use mathematical induction to show that there is a car in the group that can complete a lap by obtaining gas from other cars as it travels around the track.

Show that if n is a positive integer, then 'tt(2j - 1) (j;; 1/ k) = n(n + 1)/2.

A unit or Egyptian fraction is a fraction of the form l/n, where n is a positive integer. In this exercise, we will use strong induction to show that a greedy algorithm can be used to express every rational number p / q with o < p / q < I as the sum of distinct unit fractions. At each step of the algorithm, we find the smallest positive integer n such that 1/ n can be added to the sum without exceeding p / q. For example, to express 517 we first start the sum with 1 /2. Because 5/7 - 1 /2 = 3/14 we add 1/5 to the sum because 5 is the smallest positive integer k such that 1/ k < 3/14. Because 3/14 - 1 /5 = 1/70, the a1gorithmterminates, showing that5j7 = 1/2 + 1/5 + 1170. Let T (p) be the statement that this algorithm terminates for all rational numbers p / q with 0 < p / q < 1. We will prove that the algorithm always terminates by showing that T(p) holds for all positive integers p. a) Show that the basis step T(l) holds. b) Suppose that T(k) holds for positive integers k with k < p. That is, assume that the algorithm terminates for all rational numbers k / r, where 1 k < p. Show that if we start with p / q and the fraction 1/ n is selected in the first step of the algorithm, then p / q = p' /q' + l/n, where p' = np - q and q' = nq. After considering the case where p/q = l/n, use the inductive hypothesis to show that the greedy algorithm terminates when it begins with p' / q' and complete the inductive step.

By successively using the defining rule for M(n), find a) M(102). b) M(101). c) M(99). d) M(97). e) M(87). t) M(76)

Show that the function M(n) is a well-defined function from the set of positive integers to the set of positive integers. [Hint: Prove that M(n) = 91 for all positive integers n with n 101.]

Is this proofthat -1 1 1 3 + - + ... + - - - 1 2 23 (n - l )n - 2 - n whenever n is a positive integer, correct? Justify your answer. Basis step: The result is true when n = 1 because 1 3 1 1 2 2 Inductive step: Assume that the result is true for n. Then -1 1 1 1 + - + ... + +--- 1 2 23 (n - 1)n n(n+1) = _ .!. + (.!. _ _ 1 ) 2 n n n+1 3 1 = - 2 ---n + 1 Hence, the result is true for n + 1 if it is true for n. This completes the proof.

Suppose that AI. A2, ... , An are a collection of sets. Suppose that R2 = Al EB A2 and Rk = RkI EB Ak for k = 3, 4, ... , n. Use mathematical induction to prove that x E Rn if and only if x belongs to an odd number of the sets A I, A2, ... , An. (Recall that S EB T is the symmetric difference of the sets S and T defined in Section 2.2.)

Show that n circles divide the plane into n 2 - n + 2 regions if every two circles intersect in exactly two points and no three circles contain a common point.

Show that n planes divide three-dimensional space into (n3 + 5n + 6)/6 regions ifany three of these planes have a point in common and no four contain a common point.

Use the well-ordering property to show that .../i is irrational. [Hint: Assume that .../i is rational. Show that the set of positive integers of the form b.../i has a least element a. Then show that a.../i - a is a smaller positive integer of this form.]

A set is well ordered if every nonempty subset of this set has a least element. Determine whether each of the following sets is well ordered. a) the set of integers b) the set of integers greater than - 100 c) the set of positive rationals d) the set of positive rationals with denominator less than 100

a) Show that if aI , a2, ... , an are positive integers, then gcd(al ' a2, ... , an- I, an) = gcd(al' a2, ... , an-2, gcd(an_I ' an. b) Use part (a), together with the Euclidean algorithm, to develop a recursive algorithm for computing the greatest common divisor of a set of n positive integers.

Describe a recursive algorithm for writing the greatest common divisor of n positive integers as a linear combination of these integers.

Find an explicit formula for f(n) iff(l) = 1 and f(n) = fn - 1) + 2n - 1 for n ::: 2. Prove your result using mathematical induction.

Give a recursive definition of the set of bit strings that contain twice as many Os as 1 s

Let S be the set of bit strings defined recursively by A E S and Ox E S, x I E S if XES, where A is the empty string. a) Find all strings in S oflength not exceeding five. b) Give an explicit description of the elements of S.

Let S be the set of strings defined recursively by abc E S, bac E S, and acb E S, where a, b, and c are fixed letters; and for all XES, abcx E S; abxc E S, axbc E S, and xabc E S, where x is a variable representing a string of letters. a) Find all elements of S oflength eight or less. b) Show that every element of S has a length divisible by three.

Show that (00) is a balanced string of parentheses and (0 is not a balanced string of parentheses.

Find all balanced strings of parentheses with exactly six symbols.

Find all balanced strings of parentheses with four or fewer symbols.

Use induction to show that if x is a balanced string of parentheses, then the number of left parentheses equals the number of right parentheses in x. Define the function N on the set of strings of parentheses by N(A) = 0, N (O = 1, N O) = -I, N(uv) = N(u) + N(v), where A is the empty string, and u and v are strings. It can be shown that N is well defined.

Find a) N . c) N ( ) . b) N 0 0)(0. d) N ) ( ) ).

Show that a string w of parentheses is balanced if and only if N(w) = 0 and N(u) ::: 0 whenever u is a prefix of w, that is, w = uv.

Give a recursive algorithm for finding all balanced strings of parentheses containing n or fewer symbols.

Give a recursive algorithm for finding gcd(a, b), where a and b are nonnegative integers, based on these facts: gcd(a , b) = gcd(b, a) if a > b, gcd(O, b) = b, gcd(a, b) = 2 gcd(aI2, b12) if a and b are even, gcd(a, b) = gcd(aI2, b) if a is even and b is odd, and gcd(a, b) = gcd(a, b - a).

Verify the program segment if x > y then x := y with respect to the initial assertion T and the final assertion x :::s y.

Develop a rule of inference for verifying recursive programs and use it to verify the recursive program for computing factorials given in Section 4.4.

Devise a recursive algorithm that counts the number of times the integer 0 occurs in a list of integers.

Find the first 10 terms of the sequence {a(n)} defined in the preamble to this exercise.

Prove that this sequence is well defined. That is, show that a(n) is uniquely defined for all nonnegative integers n.

Prove that a(n) = L(n + 1)t-tJ where t-t = (- 1 + ./5)/2. [Hint: First show for all n > 0 that (t-tn - Lt-tnJ) + (t-t2 n - Lt-t2 nJ) = 1. Then show for all real numbers a with 0 :::s a < 1 and a =11 - t-t that L(1 + t-t)(I - a)J + La + t-t J = 1, considering the cases 0 :::s a < 1 - t-t and 1 - t-t < a < 1 separately.]

Use the formula from Exercise 68 to show that a(n) = a(n - 1) if t-tn - Lt-tnJ < 1 - t-t and a(n) = a(n - 1) + 1 otherwise.

Find the first 10 terms of each of the following selfgenerating sequences: a) a(n) = n - a(a(a(n - 1 ) for n ::: 1 with a(O) = 0 b) a(n) = n - a(a(a(a(n - 1 for n ::: 1 with a(O) = o . c) a(n) = a(n - a(n - 1 + a(n - a(n - 2 for n ::: 3 with a(l) = 1 and a(2) = 1

Find the first 10 terms of both the sequences m(n) and fen) defined by the following pair of interwoven recurrence relations: men) = n - f(m(n - 1, fen) = n - m(f(n - 1 for n ::: 1 with f(O) = 1 and m(O) = o.

Find the first 20 terms of Golomb's self-generating sequence.

Show that if f(n) is the largest integer m such that am = n, where am is the mth term of Golomb's self-generating sequence, then fen) = L = I ak and f(f(n = L= I kak.

Given a 2n x 2 n checkerboard with one square missing, construct a tiling of this checkerboard using right triominoes.

Generate all well-formed formulae for expressions involving the variables x, y, and z and the operators {+, *, I, -} with n or fewer symbols.

Generate all well-formed formulae for propositions with n or fewer symbols where each symbol is T, F, one of the propositional variables p and q, or an operator from {--', v, 1\, -+, }.

Given a string, find its reversal.

Given a real number a and a nonnegative integer n, find a n using recursion.

Given a real number a and a nonnegative integer n, find a 2n using recursion.

Given a real number a and a nonnegative integer n, find a n using the binary expansion of n and a recursive algorithm for computing a 2 k

Given two integers not both zero, find their greatest common divisor using recursion.

Given a list of integers and an element x, locate x in this list using a recursive implementation of a linear search.

Given a list of integers and an element x, locate x in this list using a recursive implementation of a binary search.

Given a nonnegative integer n, find the nth Fibonacci number using iteration.

Given a nonnegative integer n, find the nth Fibonacci number using recursion

Given a positive integer, find the number of partitions of this integer. (See Exercise 47 of Section 4.3.)

Given positive integers m and n, find A(m, n), the value of Ackermann's function at the pair (m, n). (See the preamble to Exercise 48 of Section 4.3.)

Given a list of n integers, sort these integers using the merge sort.

What are the largest values of n for which n! has fewer than 100 decimal digits and fewer than 1000 decimal digits?

Determine which Fibonacci numbers are divisible by 5, which are divisible by 7, and which are divisible by II. Prove that your conjectures are correct.

Construct tilings using right triominoes of various 16 x 16, 32 x 32, and 64 x 64 checkerboards with one square missing.

Explore which m x n checkerboards can be completely covered by right triominoes. Can you make a conjecture that answers this question?

Implement an algorithm for determining whether a point is in the interior or exterior of the simple polygon.

Implement an algorithm for triangulating a simple polygon.

Which values of Ackermann's function are small enough that you are able to compute them?

Compare either the number of operations or the time needed to compute Fibonacci numbers recursively versus that needed to compute them iteratively.

Describe the origins of mathematical induction. Who were the first people to use it and to which problems did they apply it?

Explain how to prove the Jordan curve theorem for simple polygons and describe an algorithm for determining whether a point is in the interior or exterior of a simple polygon.

Describe how the triangulation of simple polygons is used in some key algorithms in computational geometry.

Describe a variety of different applications of the Fibonacci numbers to the biological and the physical sciences.

Discuss the uses of Ackermann's function both in the theory of recursive definitions and in the analysis ofthe complexity of algorithms for set unions.

Discuss some of the various methodologies used to establish the correctness of programs and compare them to Hoare's methods described in Section 4.5.

Explain how the ideas and concepts of program correctness can be extended to prove that operating systems are secure.