Solved: (For students who have studied calculus) Use

The notation n  k=m ak is read _____.

The expanded form of n  k=m ak is _____.

The value of a1 +a2 +a3 ++an when n =2 is _____.

The notation n  k=m ak is read _____.

If n is a positive integer, then n!=_____.

 k=m ak +c n  k=m bk =_____.

 n  k=m ak  n  k=m bk =_____.

Write the rst four terms of the sequences dened by the formulas. ak = k 10+k , for all integers k 1.

Write the rst four terms of the sequences dened by the formulas. bj = 5 j 5+ j , for all integers j 1.

Write the rst four terms of the sequences dened by the formulas. ci = (1)i 3i , for all integers i 0.

Write the rst four terms of the sequences dened by the formulas. dm =1+1 2 m for all integers m 0.

Write the rst four terms of the sequences dened by the formulas.Let ak =2k+1 andbk = (k1)3 +k+2 for all integers k 0.Showthattherstthreetermsofthesesequencesare identical but that their fourth terms differ.

Find explicit formulas for sequences of the form a1,a2,a3,... with the initial terms given 1,1,1,1,1,1

Find explicit formulas for sequences of the form a1,a2,a3,... with the initial terms given 0,1,2,3,4,5

Find explicit formulas for sequences of the form a1,a2,a3,... with the initial terms given 1 4 , 2 9 , 3 16 , 4 25 , 5 36 , 6 49

Find explicit formulas for sequences of the form a1,a2,a3,... with the initial terms given 1 1 2 , 1 2 1 3 , 1 3 1 4 , 1 4 1 5 , 1 5 1 6 , 1 6 1 7

Find explicit formulas for sequences of the form a1,a2,a3,... with the initial terms given 1 3 , 4 9 , 9 27 , 16 81 , 25 243 , 36 729

Find explicit formulas for sequences of the form a1,a2,a3,... with the initial terms given 0, 1 2 , 2 3 , 3 4 , 4 5 , 5 6 , 6 7

Find explicit formulas for sequences of the form a1,a2,a3,... with the initial terms given 3, 6, 12, 24, 48, 96

Let a0 =2, a1 =3, a2 =2, a3 =1, a4 =0, a5 = 1, and a6 =2. Compute each of the summations and products below. a. 6  i=0 ai b. 0  i=0 ai c. 3  j=1 a2j d. 6  k=0 ak e. 2  k=2 ak

Compute the summations and products  k=1 (k+1)

Compute the summations and products 4  k=2 k2

Compute the summations and products 3  m=0 1 2m

Compute the summations and products 4  j=0 (1)

Compute the summations and products 1  i=1 i(i +1

Compute the summations and products 0  j=0 (j +1)2j

Compute the summations and products 2  k=2 1 1 k 

Compute the summations and products 1  k=1 (k2 +3)

Compute the summations and products 10  n=1 1 n 1 n+1 

Compute the summations and products  i=2 i(i +2) (i 1)(i +1)

Write the summations in expanded form. n  i=1 (2)i

Write the summations in expanded form. n  j=1 j(j +1)

Write the summations in expanded form.n+1  k=0 1 k!

Write the summations in expanded form.k+1  i=1 i(i!)

Evaluate the summations and products for the indicated values of the variable. 1 12 + 1 22 + 1 32 +...+ 1 n2; n =1

Evaluate the summations and products for the indicated values of the variable.1(1!)+2(2!)+3(3!)+...+m(m!); m =

Evaluate the summations and products for the indicated values of the variable.  1 1+1  2 2+1  3 3+1 ... k k+1 ; k =3

Evaluate the summations and products for the indicated values of the variable. 12 34 45 67 67 89 ... m(m+1) (m+2)(m+3) ;m =1

Rewrite by separating off the nal term.k+1  i=1 i(i!)

Rewrite by separating off the nal term.m+1  k=1 k2

Rewrite by separating off the nal term.n+1  m=1 m(m+1)

Write as a single summation.k  i=1 i3 +(k+1)3

Write as a single summation.m  k=1 k k+1 + m+1 m+2

Write as a single summation.n  m=0 (m+1)2m +(n+2)2n+1

Write using summation or product notation. 12 22 +32 42 +52 62 +72

Write using summation or product notation. (13 1)(23 1)+(33 1)(43 1)+(53 1)

Write using summation or product notation. (22 1)(32 1)(42 1)

Write using summation or product notation. 2 34 3 45 + 4 56 5 67 + 6 78

Write using summation or product notation. 1r +r2 r3 +r4 r5

Write using summation or product notation. (1t)(1t2)(1t3)(1t4)

Write using summation or product notation. 13 +23 +33 ++n3

Write using summation or product notation. 1 2!+ 2 3!+ 3 4!++ n (n+1)!

Write using summation or product notation. n+(n1)+(n2)++1

Write using summation or product notation. n+ n1 2! + n2 3! + n3 4! ++ 1 n!

Transform by making the change of variable i =k+1. 5  k=0 k(k1)

Transform by making the change of variable i =k+1. n  k=1 k k2 +4

Transform by making the change of variable j =i 1. n+1  i=1 (i 1)2 in

Transform by making the change of variable j =i 1. n  i=3 i i +n1

Transform by making the change of variable j =i 1. n1  i=1 i (ni)2

Transform by making the change of variable j =i 1. 2n  i=n ni +1 n+i

Write as a single summation or product. 3 n  k=1 (2k3)+ n  k=1 (45k)

Write as a single summation or product. 2 n  k=1 (3k2 +4)+5 n  k=1 (2k2 1)

Write as a single summation or product. n  k=1 k k+1  n  k=1 k+1 k+2

Compute . Assume the values of the variables are restricted so that the expressions are dened.4! 3!

Compute . Assume the values of the variables are restricted so that the expressions are dened.6! 8!

Compute . Assume the values of the variables are restricted so that the expressions are dened.4! 0!

Compute . Assume the values of the variables are restricted so that the expressions are dened.n! (n1)!

Compute . Assume the values of the variables are restricted so that the expressions are dened. (n1)! (n+1)!

Compute . Assume the values of the variables are restricted so that the expressions are dened.n! (n2)!

Compute . Assume the values of the variables are restricted so that the expressions are dened.((n+1)!)2 (n!)2

Compute . Assume the values of the variables are restricted so that the expressions are dened.n! (nk)!

Compute . Assume the values of the variables are restricted so that the expressions are dened. n! (nk+1)!

Compute . Assume the values of the variables are restricted so that the expressions are dened. a. Prove that n!+2 is divisible by 2, for all integers n 2. b. Prove that n!+k is divisible by k, for all integers n 2 and k =2,3,...,n. c.H Givenanyintegerm 2,isitpossibletondasequence of m1 consecutive positive integers none of which is prime? Explain your answer.

Compute . Assume the values of the variables are restricted so that the expressions are dened. 5 3

Compute . Assume the values of the variables are restricted so that the expressions are dened. 68. 7 4

Compute . Assume the values of the variables are restricted so that the expressions are dened. 3 0

Compute . Assume the values of the variables are restricted so that the expressions are dened. 5 5

Compute . Assume the values of the variables are restricted so that the expressions are dened.  n n1 

Compute . Assume the values of the variables are restricted so that the expressions are dened. n+1 n1 

Prove that for all nonnegative integers n and r with r +1n, n r +1 = nr r +1 n r.

Prove that if p is a prime number and r is an integer with 0 < r < p, thenp ris divisible by p.

Mathematical induction is a method for proving that a property dened for integers n is true for all values of n that are _____.

Let P(n) be a property dened for integers n and consider constructingaproofbymathematicalinductionforthestatement P(n) is true for all n a.(a) In the basis step one must show that _____. (b) In the inductive step one supposes that _____ for some particular but arbitrarily chosen value of an integer k a. This supposition is called the _____. One then has to show that _____.

Use mathematical induction (and the proof of Proposition 5.2.1 as a model) to show that any amount of money of at least 14c / can be made up using 3c / and 8c / coins.

Use mathematical induction to show that any postage of at least 12c / can be obtained using 3c / and 7c / stamps.

For each positive integer n, letP(n) be the formula 12 +22 ++n2 = n(n+1)(2n+1) 6 . a. Write P(1). IsP(1) true? b. Write P(k). c. Write P(k+1). d. In a proof by mathematical induction that the formula holds for all integers n 1, what must be shown in the inductive step?

For each integer n with n 2, let P(n) be the formula n1  i=1 i(i +1) = n(n1)(n+1) 3 . a. Write P(2). IsP(2) true? b. Write P(k). c. Write P(k+1). d. In a proof by mathematical induction that the formula holds for all integers n 2, what must be shown in the inductive step?

Fill in the missing pieces in the following proof that 1+3+5++(2n1) =n2 for all integers n 1. Proof: Let the property P(n) be the equation 1+3+5++(2n1) =n2. P(n) Show that P(1) is true: To establish P(1), we must show that when 1 is substituted in place of n, the left-hand side equals the right-hand side. But when n =1, the left-hand side is the sum of all the odd integers from 1 to 211, which is the sum of the odd integers from 1 to 1, which is just 1. The right-hand side is (a) , which also equals 1. So P(1) is true. Show that for all integers k 1, if P (k) is true then P(k+1) is true: Let k be any integer with k 1. [Suppose P(k) is true. That is:] Suppose 1+3+5++(2k1) = (b) . P(k) [This is the inductive hypothesis.] [We must show that P(k+1) is true. That is:] We must show that (c) = (d) . P(k+1) But the left-hand side of P(k+1) is 1+3+5++(2(k+1)1) =1+3+5++(2k+1) by algebra =[ 1+3+5++(2k1)]+(2k+1) the next-to-last term is 2k1 because (e) =k2 +(2k+1) by (f) = (k+1)2 by algebra which is the right-hand side of P(k+1) [as was to be shown.] [Since we have proved the basis step and the inductive step, we conclude that the given statement is true.] The previous proof was annotated to help make its logical ow more obvious. In standard mathematical writing, such annotation is omitted.

Prove using mathematical induction. Do not derive them from Theorem 5.2.2 or Theorem 5.2.3. For all integers n 1, 2+4+6++2n =n2 +n.

Prove using mathematical induction. Do not derive them from Theorem 5.2.2 or Theorem 5.2.3. For all integers n 1, 1+6+11+16++(5n4) = n(5n3) 2 .

Prove using mathematical induction. Do not derive them from Theorem 5.2.2 or Theorem 5.2.3. For all integers n 0, 1+2+22 ++2n =2n+1 1.

Prove using mathematical induction. Do not derive them from Theorem 5.2.2 or Theorem 5.2.3. For all integers n 3, 43 +44 +45 ++4n = 4(4n 16) 3 .

Prove by mathematical induction. 12 +22 ++n2 = n(n+1)(2n+1) 6 , for all integers n 1.

Prove by mathematical induction. 13 +23 ++n3 = n(n+1) 2 2, for all integers n 1.

Prove by mathematical induction. 12 + 1 23 ++ 1 n(n+1) = n n+1 , for all integers n 1.

Prove by mathematical induction. n1  i=1 i(i +1) = n(n1)(n+1) 3 , for all integers n 2.

Prove by mathematical induction. n+1  i=1 i2i =n2n+2 +2, for all integers n 0.

Prove by mathematical induction. n  i=1 i(i!) = (n+1)!1, for all integers n 1.

Prove by mathematical induction. 1 1 22 1 1 32 1 1 n2 = n+1 2n , for all inte gers n 2.

Prove by mathematical induction. n  i=0  1 2i +1 1 2i +2 = 1 (2n+2)! , for all integers n 0.

If x is a real number not divisible by , then for all integers n 1, sinx +sin3x +sin5x ++sin (2n1)x = 1cos2nx 2sinx .

(For students who have studied calculus) Use mathematical induction, the product rule from calculus, and the facts that d(x) dx =1 and thatxk+1 = xxk to prove that for all integers n 1, d(xn) dx =nxn1.

Usetheformulaforthesumoftherstn integersand/ortheformula for the sum of a geometric sequence to evaluate the sums or to write them in closed form. 4+8+12+16++200

Usetheformulaforthesumoftherstn integersand/ortheformula for the sum of a geometric sequence to evaluate the sums or to write them in closed form. 5+10+15+20++300

Usetheformulaforthesumoftherstn integersand/ortheformula for the sum of a geometric sequence to evaluate the sums or to write them in closed form. 3+4+5+6++1000

Usetheformulaforthesumoftherstn integersand/ortheformula for the sum of a geometric sequence to evaluate the sums or to write them in closed form. 7+8+9+10++600

Usetheformulaforthesumoftherstn integersand/ortheformula for the sum of a geometric sequence to evaluate the sums or to write them in closed form. 1+2+3++(k1),wherek isanintegerandk 2.

Usetheformulaforthesumoftherstn integersand/ortheformula for the sum of a geometric sequence to evaluate the sums or to write them in closed form. a. 1+2+22 ++225 b. 2+22 +23 ++226

Usetheformulaforthesumoftherstn integersand/ortheformula for the sum of a geometric sequence to evaluate the sums or to write them in closed form. 3+32 +33 ++3n, wheren is an integer with n 1

Usetheformulaforthesumoftherstn integersand/ortheformula for the sum of a geometric sequence to evaluate the sums or to write them in closed form. 53 +54 +55 ++5k,wherek isany integer with k 3.

Usetheformulaforthesumoftherstn integersand/ortheformula for the sum of a geometric sequence to evaluate the sums or to write them in closed form. 1+ 1 2 + 1 22 ++ 1 2n , wheren is a positive integer

Usetheformulaforthesumoftherstn integersand/ortheformula for the sum of a geometric sequence to evaluate the sums or to write them in closed form. 12+22 23 ++(1)n2n, wheren is a positive integer

Find a formula in n,a,m, andd for the sum (a+md)+ (a+(m+1)d)+(a+(m+2)d)++(a+(m+n)d), where m and n are integers, n 0, and a and d are real numbers. Justify your answer.

Find a formula in a,r,m, andn for the sum arm +arm+1 +arm+2 ++arm+n where m and n are integers, n 0, and a and r are real numbers. Justify your answer.

You have two parents, four grandparents, eight greatgrandparents, and so forth. a. If all your ancestors were distinct, what would be the total number of your ancestors for the past 40 generations (counting your parents generation as number one)? (Hint: Use the formula for the sum of a geometric sequence.) b. Assuming that each generation represents 25 years, how long is 40 generations? c. The total number of people who have ever lived is approximately 10 billion, which equals 1010 people. Compare this fact with the answer to part (a). What do you deduce

Find the mistakes in the proof fragments . Theorem: For any integer n 1, 12 +22 ++n2 = n(n+1)(2n+1) 6 . Proof (by mathematical induction): Certainly the theorem is true for n =1 because 12 =1 and 1(1+1)(21+1) 6 =1. So the basis step is true. Fortheinductivestep,supposethatforsomeintegerk 1, k2 = k(k+1)(2k+1) 6 . We must show that (k+1)2 = (k+1)((k+1)+1)(2(k+1)+1) 6 .

Find the mistakes in the proof fragments . Theorem: For any integer n 0, 1+2+22 ++2n =2n+1 1. Proof (by mathematical induction): Let the property P(n) be 1+2+22 ++2n =2n+1 1. Show that P(0) is true: The left-hand side of P(0) is 1+2+22 ++20 =1 and the right-hand side is 20+1 1=21=1 also. So P(0) is true.

Find the mistakes in the proof fragments . Theorem: For any integer n 1, n  i=1 i(i!) = (n+1)!1. Proof (by mathematical induction): Let the property P(n) be n  i=1 i(i!) = (n+1)!1. Show that P(1) is true: When n =1 1  i=1 i(i!) = (1+1)!1 So 1(1!) =2!1 and 1=1 Thus P(1) is true.

Use Theorem 5.2.2 to prove that if m and n are any positive integers and m is odd, thenm1 k=0 (n+k) is divisible by m.Does the conclusion hold if m is even? Justify your answer.

Use Theorem 5.2.2 and the result of exercise 10 to prove that if p is any prime number with p 5, then the sum of squares of any p consecutive integers is divisible by p.

Mathematical induction differs from the kind of induction used in the natural sciences because it is actually a form of ____ reasoning.

Mathematical induction can be used to _____ conjectures that have been made using inductive reasoning.

Based on the discussion of the product 1 1 21 1 3 1 1 41 1 n at the beginning of this section, con-jecture a formula for general n. Prove your conjecture by mathematical induction.

Experiment with computing values of the product 1+ 1 11+ 1 21+ 1 31+ 1 n for small values of n toconjectureaformulaforthisproductforgeneraln.Prove your conjecture by mathematical induction.

Observe that 1 13 = 1 3 1 13 + 1 35 = 2 5 1 13 + 1 35 + 1 57 = 3 7 1 13 + 1 35 + 1 57 + 1 79 = 4 9 Guess a general formula and prove it by mathematical induction.

Observe that 1=1, 14= (1+2), 14+9=1+2+3, 14+916= (1+2+3+4), 14+916+25=1+2+3+4+5. Guess a general formula and prove it by mathematical induction.

Evaluate the sum n  k=1 k (k+1)! for n =1,2,3,4, and 5. Make a conjecture about a formula for this sum for general n, and prove your conjecture by mathematical induction.

For each positive integer n, letP(n) be the property 5n 1 is divisible by 4. a. Write P(0). IsP(0) true? b. Write P(k). c. Write P(k+1). d. In a proof by mathematical induction that this divisibility property holds for all integers n 0, what must be shown in the inductive step?

For each positive integer n, letP(n) be the property 2n <( n+1)!. a. Write P(2). IsP(2) true? b. Write P(k). c. Write P(k+1). d. In a proof by mathematical induction that this inequality holds for all integers n 2, what must be shown in the inductive step?

Prove each statement by mathematical induction. 5n 1 is divisible by 4, for each integer n 0.

Prove each statement by mathematical induction. 7n 1 is divisible by 6, for each integer n 0.

Prove each statement by mathematical induction. n3 7n+3 is divisible by 3, for each integer n 0.

Prove each statement by mathematical induction. n3 7n+3 is divisible by 3, for each integer n 0.

Prove each statement by mathematical induction. For any integer n 0,7n 2n is divisible by 5.

Prove each statement by mathematical induction. For any integer n 0,xn yn is divisible by x y, where x and y are any integers with x = y.

Prove each statement by mathematical induction. n3 n is divisible by 6, for each integer n 0.

Prove each statement by mathematical induction. n(n2 +5) is divisible by 6, for each integer n 0.

Prove each statement by mathematical induction. 2n <( n+1)!, for all integers n 2.

Prove each statement by mathematical induction. 1+3n 4n, for every integer n 0.

Prove each statement by mathematical induction. 5n +9 < 6n, for all integers n 2.

Prove each statement by mathematical induction. n2 < 2n, for all integers n 5.

Prove each statement by mathematical induction. 2n <( n+2)!, for all integers n 0.

Prove each statement by mathematical induction. n < 1 1 + 1 2 ++ 1 n, for all integers n 2.

Prove each statement by mathematical induction. 1+nx (1+x)n, for all real numbers x > 1 and integers n 2.

Prove each statement by mathematical induction. a. n3 > 2n+1, for all integers n 2. b. n! > n2, for all integers n 4.

A sequence a1,a2,a3,...is dened by letting a1 =3 and ak =7ak1 for all integers k 2. Show that an =37n1 for all integers n 1.

A sequence b0,b1,b2,...is dened by letting b0 =5 and bk =4+bk1 forall integers k 1. Show that bn > 4n for all integers n 0.

A sequence c0,c1,c2,...is dened by letting c0 =3 and ck = (ck1)2 for all integers k 1. Show that cn =32n for all integers n 0.

A sequence d1,d2,d3,...is dened by letting d1 =2 and dk = dk1 k for all integers k 2. Show that for all integers n 1, dn = 2 n! .

Prove that for all integers n 1, 1 3 = 1+3 5+7 = 1+3+5 7+9+11 = = 1+3++(2n1) (2n+1)++(4n1) .

As each of a group of businesspeople arrives at a meeting, each shakes hands with all the other people present. Use mathematical induction to show that if n people come to the meeting then[n(n1)]/2 handshakes occur

In order for a proof by mathematical induction to be valid, the basis statement must be true for n =a and the argument of the inductive step must be correct for every integer k a. nd the mistakes in the proofs by mathematical induction. Theorem: For any integer n 1, all the numbers in a set of n numbers are equal to each other. Proof (by mathematical induction): It is obviously true that all the numbers in a set consisting of just one number are equal to each other, so the basis step is true. For the inductive step, let A ={ a1,a2,...,ak,ak+1} be any set ofk +1 numbers. Form two subsets each of size k: B ={ a1,a2,a3,...,ak} and C ={ a1,a3,a4,...,ak+1}. (B consists of all the numbers in A except ak+1, andC consists of all the numbers in A except a2.) By inductive hypothesis, all the numbers in B equal a1 and all the numbers in C equal a1 (since both sets have only k numbers). But every number in A is in B or C, so all the numbers in A equal a1; hence all are equal to each other.

In order for a proof by mathematical induction to be valid, the basis statement must be true for n =a and the argument of the inductive step must be correct for every integer k a. nd the mistakes in the proofs by mathematical induction. Theorem: For all integers n 1,3n 2 is even. Proof (by mathematical induction): Suppose the theorem is true for an integer k, wherek 1. That is, suppose that 3k 2 is even. We must show that 3k+1 2 is even. But 3k+1 2=3k32=3k(1+2)2 = (3k 2)+3k2. Now 3k 2 is even by inductive hypothesis and 3k2 is even by inspection. Hence the sum of the two quantities is even (by Theorem 4.1.1). It follows that 3k+1 2 is even, which is what we needed to show.

Some55checkerboardswithonesquareremovedcanbe completely covered by L-shaped trominoes, whereas other 55 checkerboards cannot. Find examples of both kinds of checkerboards. Justify your answers.

Consider a 46 checkerboard. Draw a covering of the board by L-shaped trominoes.

a. Use mathematical induction to prove that any checkerboard with dimensions 23n can be completely covered with L-shaped trominoes for any integer n 1. b. Let n be any integer greater than or equal to 1. Use the result of part (a) to prove by mathematical induction that for all integers m, any checkerboard with dimensions2m3n canbecompletelycoveredwithL-shaped trominoes.

Let m and n be any integers that are greater than or equal to 1. a. Prove that a necessary condition for an mn checkerboardtobecompletelycoverablebyL-shapedtrominoes is that mn be divisible by 3. H b. Prove that having mn be divisible by 3 is not a sufcient condition for an mn checkerboard to be completely coverable by L-shaped trominoes.

In a round-robin tournament each team plays every other team exactly once. If the teams are labeled T1,T2,...,Tn, then the outcome of such a tournament can be represented by a drawing, called a directed graph, in which the teams are represented as dots and an arrow is drawn from one dot to another if, and only if, the team represented by the rst dot beats the team represented by the second dot. For example, the directed graph below shows one outcome of a round-robin tournament involving ve teams, A, B, C, D, and E.Use mathematical induction to show that in any roundrobin tournament involving n teams, where n 2, it is possible to label the teams T1,T2,...,Tn so that Ti beats Ti+1 for all i =1,2,...,n1. (For instance, one such labeling in the example above is T1 = A,T2 = B,T3 = C,T4 = E,T5 = D.)(Hint:Givenk+1teams,pickone say T and apply the inductive hypothesis to the remaining teams to obtain an ordering T1,T2,...,Tk. Consider threecases: T beats T1,T losestotherstm teams(where 1m k1) and beats the (m+1)st team, and T loses to all the other teams.)

On the outside rim of a circular disk the integers from 1 through 30 are painted in random order. Show that no matter what this order is, there must be three successive integers whose sum is at least 45.

Suppose that nas and nbs are distributed around the outside of a circle. Use mathematical induction to prove that for all integers n 1, given any such arrangement, it is possible to nd a starting point so that if one travels around the circle in a clockwise direction, the number of as one has passed is never less than the number of bs one has passed. For example, in the diagram shown below, one could start at the a with an asterisk.

For a polygon to be convex means that given any two points on or inside the polygon, the line joining the points lies entirely inside the polygon. Use mathematical induction to prove that for all integers n 3, the anglesofanyn-sidedconvexpolygonaddupto180(n2) degrees.

a. Prove that in an 88 checkerboard with alternating black and white squares, if the squares in the top right andbottomleftcornersareremovedtheremainingboard cannot be covered with dominoes. (Hint: Mathematical induction is not needed for this proof.) b.H c. Use mathematical induction to prove that for all integers n, if a 2 n2n checkerboard with alternating black and white squares has one white square and one black square removed anywhere on the board, the remaining squares can be covered with dominoes.

In a proof by strong mathematical induction the basis step mayrequirecheckingaproperty P(n) formore_____value of n.

Suppose that in the basis step for a proof by strong mathematical induction the property P(n) was checked for all integers n from a through b. Then in the inductive step one assumesthatforanyintegerk b,theproperty P(n) istrue for all values of i from _____ through _____ and one shows that _____ is true.

Accordingtothewell-orderingprinciplefortheintegers,ifa set S of integers contains at least _____ and if there is some integer that is less than or equal to every _____, then _____.

Suppose a1,a2,a3,...is a sequence dened as follows: a1 =1, a2 =3, ak =ak2 +2ak1 for all integers k 3. Prove that an is odd for all integers n 1.

Suppose b1,b2,b3,...is a sequence dened as follows: b1 =4, b2 =12 bk =bk2 +bk1 for all integers k 3. Prove that bn is divisible by 4 for all integers n 1.

Supposethatc0,c1,c2,...isasequencedenedasfollows: c0 =2, c1 =2, c2 =6, ck =3ck3 for all integers k 3. Prove that cn is even for all integers n 0.

Supposethatd1,d2,d3,...isasequencedenedasfollows: d1 = 9 10 , d2 = 10 11 , dk =dk1dk2 for all integers k 3. Prove that 0 < dn 1 for all integers n 1.

Supposethate0,e1,e2,...isasequencedenedasfollows: e0 =12, e1 =29 ek =5ek1 6ek2 for all integers k 2. Prove that en =53n +72n for all integers n 0.

Suppose that f0, f1, f2,... is a sequence dened as follows: f0 =5, f1 =16 fk =7fk1 10fk2 for all integers k 2. Prove that fn =32n +25n for all integers n 0.

Suppose that g1,g2,g3,... is a sequence dened as follows: g1 =3, g2 =5 gk =3gk1 2gk2 for all integers k 3. Prove that gn =2n +1 for all integers n 1.

Suppose that h0,h1,h2,... is a sequence dened as follows: h0 =1, h1 =2, h2 =3, hk =hk1 +hk2 +hk3 for all integers k 3. a. Prove that hn 3n for all integers n 0. b. Suppose that s is any real number such that s3 s2 +s+1. (This implies that s > 1.83.) Prove that hn sn for all n 2.

Deneasequencea1,a2,a3,...asfollows:a1 =1,a2 =3, andak =ak1 +ak2 forallintegersk 3.(Thissequence is known as the Lucas sequence.) Use strong mathematical induction to prove that an 7 4n for all integers n 1.

The problem that was used to introduce ordinary mathematical induction in Section 5.2 can also be solved using strong mathematical induction. Let P(n) be any nc / can be obtained using a combination of 3c / and 5c / coins. Use strong mathematical induction to prove that P(n) is true for all integers n 8.

You begin solving a jigsaw puzzle by nding two pieces that match and tting them together. Each subsequent step of the solution consists of tting together two blocks made up of one or more pieces that have previously been assembled. Use strong mathematical induction to prove that the number of steps required to put together all n pieces of a jigsaw puzzle is n1.

The sides of a circular track contain a sequence of cans of gasoline.Thetotalamountinthecansissufcienttoenable a certain car to make one complete circuit of the track, and itcouldalltintothecarsgastankatonetime.Usemathematicalinductiontoprovethatitispossibletondaninitial location for placing the car so that it will be able to traverse the entire track by using the various amounts of gasoline in the cans that it encounters along the way.

Use strong mathematical induction to prove the existence partoftheuniquefactorizationofintegers(Theorem4.3.5): Every integer greater than 1 is either a prime number or a product of prime numbers.

Any product of two or more integers is a result of successive multiplications of two integers at a time. For instance, hereareafewofthewaysinwhicha1a2a3a4 mightbecomputed: (a1a2)(a3a4) or ((a1a2)a3)a4) or a1((a2a3)a4).Use strong mathematical induction to prove that any product of two or more odd integers is odd.

Dene the sum of one integer to be that integer, and use strong mathematical induction to prove that for all integers n 1, any sum of n even integers is even.

Use strong mathematical induction to prove that for any integer n 2, if n is even, then any sum of n odd integers is even, and if n is odd, then any sum of n odd integers is odd.

Compute 41,42,43,44,45,46,47, and 4 8. Make a conjecture about the units digit of 4n where n is a positive integer. Use strong mathematical induction to prove your conjecture.

Compute90,91,92,93,94,and9 5.Makeaconjectureabout theunitsdigitof9n wheren isapositiveinteger.Usestrong mathematical induction to prove your conjecture.

Find the mistake in the following proof that purports to show that every nonnegative integer power of every nonzero real number is 1. Proof: Letr beanynonzerorealnumberandlettheproperty P(n) be the equation rn =1. Show that P(0) is true:P(0) is true becauser0 =1 by definition of zeroth power. Show that for all integers k0, if P(i) is true for all integers i from 0 through k, then P(k+1) is also true:Let k be any integer with k 0 and suppose that ri =1 for all integers i from 0 through k. This is the inductive hypothesis. We must show that rk+1 =1. Now rk+1 =rk+k(k1) becausek+k(k1) =k+kk+1=k+1 = rkrk rk1 by the laws of exponents = 11 1 by inductive hypothesis =1. Thus rk+1 =1 [as was to be shown]. [Since we have proved the basis step and the inductive step of the strong mathematical induction, we conclude that the given statement is true.]

Use the well-ordering principle for the integers to prove Theorem 4.3.4: Every integer greater than 1 is divisible by a prime number.

Use the well-ordering principle for the integers to prove the existence part of the unique factorization of integers theorem: Every integer greater than 1 is either prime or a product of prime numbers.

a. The Archimedean property for the rational numbers states that for all rational numbers r, there is an integer n such that n > r. Prove this property. b. Prove that given any rational number r, the numberr is also rational. c. Use the results of parts (a) and (b) to prove that given any rational number r, there is an integer m such that m < r.

Use the results of exercise 22 and the well-ordering principle for the integers to show that given any rational number r, there is an integer m such that m r < m+1.

Usethewell-orderingprincipletoprovethatgivenanyinteger n 1, there exists an odd integer m and a nonnegative integer k such that n =2km.

Imagine a situation in which eight people, numbered consecutively 18, are arranged in a circle. Starting from person #1, every second person in the circle is eliminated. The elimination process continues until only one person remains. In the rst round the people numbered 2, 4, 6, and 8 are eliminated, in the second round the people numbered 3 and 7 are eliminated, and in the third round person #5 is eliminated.Soafterthethirdroundonlyperson#1remains, as shown below.a. Given a set of sixteen people arranged in a circle and numbered, consecutively 116, list the numbers of the people who are eliminated in each round if every second person is eliminated and the elimination process continuesuntilonlyonepersonremains.Assumethatthestarting point is person #1. b. Use mathematical induction to prove that for all integers n 1,givenanysetof2n peoplearrangedinacircleand numbered consecutively 1 through 2n, if one starts from person #1 and goes repeatedly around the circle successively eliminating every second person, eventually only person #1 will remain. c. . Use the result of part (b) to prove that for any nonnegative integers n and m with 2n 2n +m < 2n+1, if r =2n +m, then given any set of r people arranged in a circle and numbered consecutively 1 through r, if one starts from person #1 and goes repeatedly around the circle successively eliminating every second person, eventually only person #(2m+1) will remain.

Suppose P(n) is a property such that 1. P(0), P(1), P(2) are all true, 2. for all integers k 0, if P(k) is true, then P(3k) is true. Must it follow that P(n) is true for all integers n 0? If yes, explain why; if no, give a counterexample.

Prove that if a statement can be proved by strong mathematical induction, then it can be proved by ordinary mathematical induction. To do this, let P(n) be a property that is dened for integers n, and suppose the following two statements are true: 1. P(a), P(a+1), P(a+2),...,P(b). 2. For any integer k b, ifP(i) is true for all integers i from a through k, thenP(k+1) is true. The principle of strong mathematical induction would allow us to conclude immediately that P(n) is true for all integersn a.Canwereachthesameconclusionusingthe principle of ordinary mathematical induction? Yes! To see this, let Q(n) be the property P(j) is true for all integers j with a j n. Then use ordinary mathematical induction to show that Q(n) is true for all integers n b. That is, prove 1. Q(b) is true. 2. For any integer k b, ifQ(k) is true then Q(k+1) is true.

Give examples to illustrate the proof of Theorem 5.4.1.

Write the following numbers in decimal notation: a.11102 b.101112 c. 1101102 d. 11001012 e. 10001112 f. 10110112

It is a fact that every integer n 1 can be written in the form cr3r +cr13r1 ++c232 +c13+c0, where cr =1 or 2 andci =0,1, or 2 for all integers i = 0,1,2,...,r 1. Sketch a proof of this fact.

Use mathematical induction to prove the existence part of the quotient-remainder theorem for integers n 0.

Prove that if a statement can be proved by ordinary mathematical induction, then it can be proved by the wellordering principle.

Use the principle of ordinary mathematical induction to prove the well-ordering principle for the integers.

A recursive denition for a sequence consists of a _____ and _____.

A recurrence relation is an equation that denes each later term of a sequence by reference to _____ in the sequence.

Initialconditionsforarecursivedenitionofasequenceconsist of one or more of the _____ of the sequence.

To solve a problem recursively means to divide the problem into smaller subproblems of the same type as the initial problem, to suppose _____, and to gure out how to use the supposition to _____.

A crucial step for solving a problem recursively is to dene a _____ in terms of which the recurrence relation and initial conditions can be specied.

Find the rst four terms of each of the recursively dened sequences. ak =2ak1 +k, for all integers k 2 a1 =1

Find the rst four terms of each of the recursively dened sequences. bk =bk1 +3k, for all integers k 2 b1 =1

Find the rst four terms of each of the recursively dened sequences.ck =k(ck1)2, for all integers k 1 c0 =1

Find the rst four terms of each of the recursively dened sequences.dk =k(dk1)2, for all integers k 1 d0 =3

Find the rst four terms of each of the recursively dened sequences. sk =sk1 +2sk2, for all integers k 2 s0 =1, s1 =1

Find the rst four terms of each of the recursively dened sequences.tk =tk1 +2tk2, for all integers k 2 t0 =

Find the rst four terms of each of the recursively dened sequences.uk =kuk1 uk2, for all integers k 3 u1 =1, u2 =1

Find the rst four terms of each of the recursively dened sequences.vk = vk1 +vk2 +1, for all integers k 3 v1 =1,v

Find the rst four terms of each of the recursively dened sequences.Let a0,a1,a2,...be dened by the formula an =3n+1, for all integers n 0. Show that this sequence satises the recurrence relation ak =ak1 +3, for all integers k 1.

Letb0,b1,b2,...bedenedbytheformulabn =4n,forall integers n 0. Show that this sequence satises the recurrence relation bk =4bk1, for all integers k 1.

Let c0,c1,c2,... be dened by the formula cn =2n 1 for all integers n 0. Show that this sequence satises the recurrence relation ck =2ck1 +1.

Let s0,s1,s2,... be dened by the formula sn = (1)n n!for all integers n 0. Show that this sequence satises therecurrence relation sk = sk1 k .

Let t0,t1,t2,...be dened by the formula tn =2+n for all integers n 0. Show that this sequence satises the recurrence relation tk =2tk1 tk2.

Let d0,d1,d2,...be dened by the formula dn =3n 2n for all integers n 0. Show that this sequence satises the recurrence relation dk =5dk1 6dk2.

For the sequence of Catalan numbers dened in Example 5.5.4, prove that for all integers n 1, Cn = 1 4n+2  2n+2 n+1 .

Use the recurrence relation and values for the Tower of Hanoi sequence m1,m2,m3,... discussed in Example 5.5.5 to compute m7 and m8.

TowerofHanoiwithAdjacencyRequirement:Supposethat inadditiontotherequirementthattheynevermovealarger diskontopofasmallerone,thepriestswhomovethedisks of the Tower of Hanoi are also allowed only to move disks one by one from one pole to an adjacent pole. Assume poles A and C are at the two ends of the row and pole B is in the middle. Let an = the minimum number of moves needed to transfer a tower of n disks from pole A to pole C . a. Find a1,a2, anda3. b. Find a4. c. Find a recurrence relation for a1,a2,a3,... .

Tower of Hanoi with Adjacency Requirement: Suppose the same situation as in exercise 17. Let bn = the minimum number of moves needed to transfer a tower of n disks from pole A to pole B . a. Find b1,b2, andb3. b. Find b4. c. Show that bk =ak1 +1+bk1 for all integers k 2, where a1,a2,a3,... is the sequence dened in exercise 17. d. Show that bk 3bk1 +1 for all integers k 2. e.H Show that bk =3bk1 +1 for all integers k 2.

Four-Pole Tower of Hanoi: Suppose that the Tower of Hanoi problem has four poles in a row instead of three. Disks can be transferred one by one from one pole to any other pole, but at no time may a larger disk be placed on top of a smaller disk. Let sn be the minimum number of moves needed to transfer the entire tower of n disks from the left-most to the right-most pole. a. Find s1,s2, ands3. b. Find s4. c. Show that sk 2sk2 +3 for all integers k 3.

Tower of Hanoi Poles in a Circle: Suppose that instead of being lined up in a row, the three poles for the original Tower of Hanoi are placed in a circle. The monks move thedisksonebyonefromonepoletoanother,buttheymay onlymovedisksoneoverinaclockwisedirectionandthey may never move a larger disk on top of a smaller one. Let cn be the minimum number of moves needed to transfer a pile of n disks from one pole to the next adjacent pole in the clockwise direction. a. Justify the inequality ck 4ck1 +1 for all integers k 2.b. The expression 4ck1 +1 is not the minimum number of moves needed to transfer a pile of k disks from one pole to another. Explain, for example, why c3 =4c2 +1.

Double Tower of Hanoi: In this variation of the Tower of Hanoi there are three poles in a row and 2n disks, two of each of n different sizes, where n is any positive integer. Initially one of the poles contains all the disks placed on top of each other in pairs of decreasing size. Disks are transferred one by one from one pole to another, but at no time may a larger disk be placed on top of a smaller disk. However, a disk may be placed on top of one of the same size. Let tn be the minimum number of moves needed to transfer a tower of 2n disks from one pole to another. a. Find t1 and t2. b. Find t3. c. Find a recurrence relation for t1,t2,t3,....

Fibonacci Variation: A single pair of rabbits (male and female) is born at the beginning of a year. Assume the following conditions (which are more realistic than Fibonaccis): (1) Rabbit pairs are not fertile during their rst month of life but thereafter give birth to four new male/female pairs at the end of every month. (2) No rabbits die. a. Let rn =the number of pairs of rabbits alive at the end of month n, for each integer n 1, and let r0 =1. Find a recurrence relation for r0,r1,r2,.... b. Compute r0,r1,r2,r3,r4,r5, andr6. c. How many rabbits will there be at the end of the year?

Fibonacci Variation: A single pair of rabbits (male and female) is born at the beginning of a year. Assume the following conditions: (1) Rabbit pairs are not fertile during their rst two months of life, but thereafter give birth to three new male/female pairs at the end of every month. (2) No rabbits die. a. Let sn =the number of pairs of rabbits alive at the end of month n, for each integer n 1, and let s0 =1. Find a recurrence relation for s0,s1,s2,.... b. Compute s0,s1,s2,s3,s4, ands5. c. How many rabbits will there be at the end of the year?

F0, F1, F2,...is the Fibonacci sequence. Use the recurrence relation and values for F0, F1, F2,... given in Example 5.5.6 to compute F13 and F14.

F0, F1, F2,...is the Fibonacci sequence. The Fibonacci sequence satises the recurrence relation Fk = Fk1 +Fk2, for all integers k 2. a. Explain why the following is true: Fk+1 = Fk +Fk1 for all integers k 1. b. Write an equation expressing Fk+2 in terms of Fk+1 and Fk. c. Write an equation expressing Fk+3 in terms of Fk+2 and Fk+1

F0, F1, F2,...is the Fibonacci sequence.Prove that Fk =3Fk3 +2Fk4 for all integers k 4.

F0, F1, F2,...is the Fibonacci sequence.Prove that F2 k F2 k1 = FkFk 1 Fk 1Fk 1, for allintegers k 1.

F0, F1, F2,...is the Fibonacci sequence.Prove that F2 k+1 F2 k F2 k1 =2FkFk1, for all integersk 1.

F0, F1, F2,...is the Fibonacci sequence.Prove that F2 k+1 F2 k = Fk1Fk+2, for all integersk 1.

F0, F1, F2,...is the Fibonacci sequence.Use mathematical induction to prove that for all integers n 0, Fn+2Fn F2 n+1 = (1)n.

F0, F1, F2,...is the Fibonacci sequence.Use strong mathematical induction to prove that Fn < 2n for all integers n 1.

F0, F1, F2,...is the Fibonacci sequence.It turns out that the Fibonacci sequence satises the following explicit formula: For all integers Fn 0, Fn = 1 5 1+5 2 n+1 15 2 n+1 Verify that the sequence dened by this formula satises the recurrence relation Fk = Fk1 +Fk2 for all integers k 2.

F0, F1, F2,...is the Fibonacci sequence. (For students who have studied calculus) Find lim n Fn+1 Fn , assuming that the limit exists.

F0, F1, F2,...is the Fibonacci sequence. (For students who have studied calculus) Prove that lim n Fn+1 Fn exists.

(For students who have studied calculus) Dene x0,x1,x2,...as follows: xk =2+xk1 for all integers k 1 x0 =0 Find limn xn. (Assume that the limit exists.)

Compound Interest: Suppose a certain amount of money is deposited in an account paying 4% annual interest compounded quarterly. For each positive integer n, let Rn =the amount on deposit at the end of the nth quarter, assuming no additional deposits or withdrawals, and let R0 be the initial amount deposited. a. Find a recurrence relation for R0, R1, R2,.... b. If R0 =$5000, nd the amount of money on deposit at the end of one year. c. Find the APR for the account.

Compound Interest: Suppose a certain amount of money is deposited in an account paying 3% annual interest compounded monthly. For each positive integer n, letSn =the amount on deposit at the end of the nth month, and let S0 be the initial amount deposited. a. Find a recurrence relation for S0, S1, S2,..., assuming no additional deposits or withdrawals during the year. b. If S0 =$10,000, nd the amount of money on deposit at the end of one year. c. Find the APR for the account.

Witheachstepyoutakewhenclimbingastaircase,youcan move up either one stair or two stairs. As a result, you can climb the entire staircase taking one stair at a time, taking twoatatime,ortakingacombinationofone-andtwo-stair increments.Foreachintegern 1,ifthestaircaseconsists of n stairs, let cn be the number of different ways to climb the staircase. Find a recurrence relation for c1,c2,c3,....

A set of blocks contains blocks of heights 1, 2, and 4 centimeters. Imagine constructing towers by piling blocks of differentheightsdirectlyontopofoneanother.(Atowerof height 6cm could be obtained using six 1-cm blocks, three 2-cm blocks one 2-cm block with one 4-cm block on top, one 4-cm block with one 2-cm block on top, and so forth.) Let tn be the number of ways to construct a tower of height n cmusingblocksfromtheset.(Assumeanunlimitedsupply of blocks of each size.) Find a recurrence relation for t1,t2,t3,...

Use the recursive denition of summation, together with mathematical induction, to prove the generalized distributivelawthatforallpositiveintegersn,ifa1,a2,...,an and c are real numbers, then n  i=1 cai =c n  i=1 ai .

Usetherecursivedenitionofproduct,togetherwithmathematical induction, to prove that for all positive integers n, if a1,a2,...,an and b1,b2,...,bn are real numbers, then n  i=1 (aibi) = n  i=1 ai  n  i=1 bi .

Usetherecursivedenitionofproduct,togetherwithmathematical induction, to prove that for all positive integers n, if a1,a2,...,an and c are real numbers, then n  i=1 (cai) =cn n  i=1 ai .

The triangle inequality for absolute value states that for all real numbers a and b,|a+b|| a|+|b|. Use the recursive denition of summation, the triangle inequality, the denitionofabsolutevalue, andmathematical induction to prove that for all positive integers n, ifa1,a2,...,an are real numbers, then      n  i=1 ai     n  i=1 |ai|.

To use iteration to nd an explicit formula for a recursively dened sequence, start with the _____ and use successive substitution into the _____ to look for a numerical pattern.

At every step of the iteration process, it is important to eliminate _____.

If a single number, say a, is added to itself k times in one of the steps of the iteration, replace the sum by the expression _____.

If a single number, say a, is multiplied by itself k times in one of the steps of the iteration, replace the product by the expression _____.

A general arithmetic sequence a0, a1, a2,... with initial value a0 and xed constant d satises the recurrence relation _____ and has the explicit formula _____.

A general geometric sequence a0, a1, a2,... with initial value a0 and xed constant r satises the recurrence relation _____ and has the explicit formula _____.

Whenanexplicitformulaforarecursivelydenedsequence has been obtained by iteration, its correctness can be checked by _____.

The formula 1+2+3++n = n(n+1) 2 is true for all integers n 1. Use this fact to solve each of the following problems: a. If k is an integer and k 2, nd a formula for the expression 1+2+3++(k1). b. If n is an integer and n 1, nd a formula for the expression 3+2+4+6+8++2n.c. If n is an integer and n 1, nd a formula for the expression 3+32+33++3n+n.

The formula 1+r +r2 ++rn = rn+1 1 r 1 is true for all real numbers r except r =1 and for all integers n 0. Use this fact to solve each of the following problems: a. If i is an integer and i 1, nd a formula for the expression 1+2+22 ++2i1.b. If n is an integer and n 1, nd a formula for the expression 3n1 +3n2 ++32 +3+1.c. If n is an integer and n 2, nd a formula for the expression 2n +2n23+2n33++223+23+3d. If n is an integer and n 1, nd a formula for the expression 2n 2n1 +2n2 2n3 ++(1)n12+(1)n.

In a sequence is dened recursively. Use iteration to guess an explicit formula for the sequence. Use the formulas from Section 5.2 to simplify your answers whenever possible. ak =kak1, for all integers k 1 a0 =1

In a sequence is dened recursively. Use iteration to guess an explicit formula for the sequence. Use the formulas from Section 5.2 to simplify your answers whenever possible. bk = bk1 1 + bk1 , for all integers k 1 b0 =1

In a sequence is dened recursively. Use iteration to guess an explicit formula for the sequence. Use the formulas from Section 5.2 to simplify your answers whenever possible. ck =3ck1 +1, for all integers k 2 c1 =1

In a sequence is dened recursively. Use iteration to guess an explicit formula for the sequence. Use the formulas from Section 5.2 to simplify your answers whenever possible. dk =2dk1 +3, for all integers k 2 d1 =2

In a sequence is dened recursively. Use iteration to guess an explicit formula for the sequence. Use the formulas from Section 5.2 to simplify your answers whenever possible. ek =4ek1 +5, for all integers k 1 e0 =2

In a sequence is dened recursively. Use iteration to guess an explicit formula for the sequence. Use the formulas from Section 5.2 to simplify your answers whenever possible. fk = fk1 +2k, for all integers k 2 f1 =1

In a sequence is dened recursively. Use iteration to guess an explicit formula for the sequence. Use the formulas from Section 5.2 to simplify your answers whenever possible. gk = gk1 gk1 +2 , for all integers k 2 g1 =

In a sequence is dened recursively. Use iteration to guess an explicit formula for the sequence. Use the formulas from Section 5.2 to simplify your answers whenever possible. hk =2k hk1, for all integers k 1 h0 =1

In a sequence is dened recursively. Use iteration to guess an explicit formula for the sequence. Use the formulas from Section 5.2 to simplify your answers whenever possible. pk = pk1 +23k p1 =2

In a sequence is dened recursively. Use iteration to guess an explicit formula for the sequence. Use the formulas from Section 5.2 to simplify your answers whenever possible. sk =sk1 +2k, for all integers k 1 s0 =3

In a sequence is dened recursively. Use iteration to guess an explicit formula for the sequence. Use the formulas from Section 5.2 to simplify your answers whenever possible. tk =tk1 +3k+1, for all integers k 1 t0 =0

In a sequence is dened recursively. Use iteration to guess an explicit formula for the sequence. Use the formulas from Section 5.2 to simplify your answers whenever possible. xk =3xk1 +k, for all integers k 2 x1 =1

In a sequence is dened recursively. Use iteration to guess an explicit formula for the sequence. Use the formulas from Section 5.2 to simplify your answers whenever possible. yk = yk1 +k2, for all integers k 2 y1 =1

Solve the recurrence relation obtained as the answer to exercise 17(c) of Section 5.5.

Solve the recurrence relation obtained as the answer to exercise 21(c) of Section 5.5.

Supposed isaxedconstantanda0,a1,a2,...isasequence that satises the recurrence relation ak =ak1 +d, for all integers k 1. Use mathematical induction to prove that an =a0 +nd, for all integers n 0.

A worker is promised a bonus if he can increase his productivity by 2 units a day every day for a period of 30 days. If on day 0 he produces 170 units, how many units must he produce on day 30 to qualify for the bonus?

A runner targets herself to improve her time on a certain course by 3 seconds a day. If on day 0 she runs the course in 3 minutes, how fast must she run it on day 14 to stay on target?

Suppose r is a xed constant and a0,a1,a2 ...is a sequence that satises the recurrence relation ak =rak1, for all integers k 1 anda0 =a. Use mathematical induction to prove that an =arn, for all integers n 0.

As shown in Example 5.5.8, if a bank pays interest at a rate of i compounded m times a year, then the amount of money Pk at the end of k time periods (where one time period =1/mth of a year) satises the recurrence relation Pk =[ 1+(i/m)]Pk1 with initial condition P0 =the initial amount deposited. Find an explicit formula for Pn.

Supposethepopulationofacountryincreasesatasteadyrate of 3% per year. If the population is 50 million at a certain time, what will it be 25 years later?

A chain letter works as follows: One person sends a copy of the letter to ve friends, each of whom sends a copy to ve friends, each of whom sends a copy to ve friends, and so forth. How many people will have received copies of the letter after the twentieth repetition of this process, assuming no person receives more than one copy?

A certain computer algorithm executes twice as many operations when it is run with an input of size k as when it is run with an input of size k1 (wherek is an integer that is greater than 1). When the algorithm is run with an input of size 1, it executes seven operations. How many operations does it execute when it is run with an input of size 25?

A person saving for retirement makes an initial deposit of $1,000 to a bank account earning interest at a rate of 3% per year compounded monthly, and each month she adds an additional $200 to the account. a. For each nonnegative integer n, letAn be the amount in theaccountattheendofn months.Findarecurrencerelation relating Ak to Ak1. b.H Use iteration to nd an explicit formula for An. c. Use mathematical induction to prove the correctness of the formula you obtained in part (b). d. How much will the account be worth at the end of 20 years? At the end of 40 years? e.H In how many years will the account be worth $10,000?

A person borrows $3,000 on a bank credit card at a nominal rate of 18% per year, which is actually charged at a rate of 1.5% per month. a.H What is the annual percentage rate (APR) for the card? (See Example 5.5.8 for a denition of APR.) b. Assume that the person does not place any additional charges on the card and pays the bank $150 each month to pay off the loan. Let Bn be the balance owed on the card after n months. Find an explicit formula for Bn. c.H How long will be required to pay off the debt? d. What is the total amount of money the person will have paid for the loan?

Use mathematical induction to verify the correctness of the formula you obtained in the referenced exercise. Exercise 3

Use mathematical induction to verify the correctness of the formula you obtained in the referenced exercise. Exercise 4

Use mathematical induction to verify the correctness of the formula you obtained in the referenced exercise. Exercise 5

Use mathematical induction to verify the correctness of the formula you obtained in the referenced exercise. Exercise 6

Use mathematical induction to verify the correctness of the formula you obtained in the referenced exercise. Exercise 7

Use mathematical induction to verify the correctness of the formula you obtained in the referenced exercise. Exercise 8

Use mathematical induction to verify the correctness of the formula you obtained in the referenced exercise. Exercise 9

Use mathematical induction to verify the correctness of the formula you obtained in the referenced exercise. Exercise 10

Use mathematical induction to verify the correctness of the formula you obtained in the referenced exercise. Exercise 11

Use mathematical induction to verify the correctness of the formula you obtained in the referenced exercise. Exercise 12

Use mathematical induction to verify the correctness of the formula you obtained in the referenced exercise. Exercise 13

Use mathematical induction to verify the correctness of the formula you obtained in the referenced exercise. Exercise 14

Use mathematical induction to verify the correctness of the formula you obtained in the referenced exercise. Exercise 15

Use mathematical induction to verify the correctness of the formula you obtained in the referenced exercise. Exercise 16

Use mathematical induction to verify the correctness of the formula you obtained in the referenced exercise. Exercise 17

Inasequenceisdenedrecursively.(a)Useiterationtoguessanexplicitformulaforthesequence.(b)Usestrong mathematical induction to verify that the formula of part (a) is correct. ak = ak1 2ak1 1 , for all integers k 1

Inasequenceisdenedrecursively.(a)Useiterationtoguessanexplicitformulaforthesequence.(b)Usestrong mathematical induction to verify that the formula of part (a) is correct. bk = 2 bk1 , for all integers k 2

Inasequenceisdenedrecursively.(a)Useiterationtoguessanexplicitformulaforthesequence.(b)Usestrong mathematical induction to verify that the formula of part (a) is correct. vk = vk/2+v(k+1)/2+2, for all integers k 2, v1 =1.

Inasequenceisdenedrecursively.(a)Useiterationtoguessanexplicitformulaforthesequence.(b)Usestrong mathematical induction to verify that the formula of part (a) is correct. sk =2sk2, for all integers k 2, s0 =1,s1 =2.

Inasequenceisdenedrecursively.(a)Useiterationtoguessanexplicitformulaforthesequence.(b)Usestrong mathematical induction to verify that the formula of part (a) is correct. tk =ktk1, for all integers k 1, t0 =0.

Inasequenceisdenedrecursively.(a)Useiterationtoguessanexplicitformulaforthesequence.(b)Usestrong mathematical induction to verify that the formula of part (a) is correct. wk = wk2 +k, for all integers k 3, w1 =1,w 2 =2.

Inasequenceisdenedrecursively.(a)Useiterationtoguessanexplicitformulaforthesequence.(b)Usestrong mathematical induction to verify that the formula of part (a) is correct. uk =uk2uk1, for all integers k 2, u0 =u1 =2.

Determine whether the given recursively dened sequence satises the explicit formula an = (n1)2, for all integers n 1. ak =2ak1 +k1, for all integers k 2 a1 =0

Determine whether the given recursively dened sequence satises the explicit formula an = (n1)2, for all integers n 1.ak = (ak1 +1)2, for all integers k 2 a1 =0

A single line divides a plane into two regions. Two lines (by crossing) can divide a plane into four regions; three lines can divide it into seven regions (see the gure). Let Pn be the maximum number of regions into which n lines divide a plane, where n is a positive integer. a. Derive a recurrence relation for Pk in terms of Pk1, for all integers k 2. b. Use iteration to guess an explicit formula for Pn.

Compute 11 10 n for small values of n (up to about 5 or 6). Conjecture explicit formulas for the entries in this matrix, and prove your conjecture using mathematical induction.

Ineconomicsthebehaviorofaneconomyfromoneperiodto another is often modeled by recurrence relations. Let Yk be the income in period k and Ck be the consumption in period k. In one economic model, income in any period is assumed to be the sum of consumption in that period plus investment and government expenditures (which are assumed to be constant from period to period), and consumption in each period is assumed to be a linear function of the income of the preceding period. That is, Yk =Ck +E where E is the sum of investment plus government expenditures Ck =c+mYk1 where c and m are constants. Substituting the second equation into the rst gives Yk = E +c+mYk1. a. Use iteration on the above recurrence relation to obtain Yn = (E +c)mn 1 m1 +mnY0 for all integers n1. b. (For students who have studied calculus) Show that if 0 < m < 1, then lim n Yn = E +c 1m .