On the outside rim of a circular disk the integers from 1

Problem 1E Based on the discussion of the product at the beginning of this section, conjecture a formula for general n. Prove your conjecture by mathematical induction.

Problem 40E a. Prove that in an 8 ×8 checkerboard with alternating black and white squares, if the squares in the top right and bottom left corners are removed the remaining board cannot be covered with dominoes. (Hint: Mathematical induction is not needed for this proof.) b.Use mathematical induction to prove that for all integers n, if a 2n x 2n 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.

Problem 3E Observe that Guess a general formula and prove it by mathematical induction.

Problem 2E Experiment with computing values of the product for small values of n to conjecture a formula for this product for general n. Prove your conjecture by mathematical induction.

Problem 6E For each positive integer n, let P(n) be the property 5n –1 is divisible by 4. a. Write P (0). Is P (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?

Problem 8E Prove the statement by mathematical induction. Exercise 5n –1 is divisible by 4, for each integer n ? 0.

Problem 4E Observe that Guess a general formula and prove it by mathematical induction.

Problem 5E Evaluate the sum 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.

Problem 9E Prove the statement by mathematical induction. Exercise 7n –1 is divisible by 6, for each integer n ? 0.

Problem 10E Prove the statement by mathematical induction. Exercise n3 –7n + 3 is divisible by 3, for each integer n ? 0.

Problem 13E Prove the statement by mathematical induction. Exercise For any integer n ? 0, xn – yn is divisible by x – y, where x and y are any integers with x ? y.

Problem 14E Prove the statement by mathematical induction. Exercise n3 – n is divisible by 6, for each integer n ? 0.

Problem 12E Prove the statement by mathematical induction. Exercise For any integer n ? 0, 7n – 2n is divisible by 5.

Problem 15E Prove the statement by mathematical induction. Exercise n(n2 + 5) is divisible by 6, for each integer n ?0.

Problem 16E Prove the statement by mathematical induction. Exercise 2n<(n + 1)!, for all integers n ? 2.

Problem 11E Prove the statement by mathematical induction. Exercise 32n – 1 is divisible by 8, for each integer n ?0.

Problem 17E Prove the statement by mathematical induction. Exercise 1 + 3n ? 4n, for every integer n ? 0.

Problem 18E Prove the statement by mathematical induction. Exercise 5n + 9 ? 6n, for all integers n ?2.

Problem 19E Prove the statement by mathematical induction. Exercise n2<2n, for all integers n? 5.

Problem 20E Prove the statement by mathematical induction. Exercise 2n ? (n + 2)!, for all integers n ?0.

Problem 21E Prove the statement by mathematical induction. Exercise for all integers n ? 2.

Problem 23E Prove the statement by mathematical induction. Exercise a. n3 > 2n + 1, for all integers n ? 2. ________________ b. n! > n2, for all integers n ?4.

Problem 24E A sequence a1, a2, a3, ... is defined by letting a1 = 3 and ak = 7ak—1 for all integers k ?2. Show that an = 3•7n–1 for all integers n ? 1.

Problem 22E Prove the statement by mathematical induction. Exercise 1+ nx ? (1 + x )n, for all real numbers x ? –1 and integers n ?2.

Problem 25E A sequence b0, b1, b2, ... is defined by letting b0 = 5 and bk = 4 + bk–1 for all integers k > 1. Show that bn ?4n for all integers n ? 0.

Problem 26E A sequence c0, c1, c2, ... is defined by letting c0 = 3 and ck = (ck–1)2 for all integers k ? 1. Show that cn = 32n for all integers n ? 0.

Problem 27E A sequence d2, d3, ... is defined by letting d1 = 2 and for all integers k ? 2. Show that for all integers n ? 1

Problem 28E Prove that for all integers n ? 1,

Problem 30E 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. In Find the mistakes in the “proofs” by mathematical induction. Exercise “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 of k + 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, and C 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.”

Problem 29E 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(n – 1)]/2 handshakes occur.

Problem 32E Some 5 × 5 checkerboards with one square removed can be completely covered by L-shaped trominoes, whereas other 5×5 checkerboards cannot. Find examples of both kinds of checkerboards. Justify your answers.

Problem 33E Consider a 4 × 6 checkerboard. Draw a covering of the board by L-shaped trominoes.

Problem 31E 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. In Find the mistakes in the “proofs” by mathematical induction. Exercise “Theorem:” For all integers n > 1,3n – 2 is even. “Proof (by mathematical induction): Suppose the theorem is true for an integer k, where k ? 1. That is, suppose that 3k – 2 is even. We must show that 3k+1 –2 is even. But Now 3k – 2 is even by inductive hypothesis and 3k • 2 is even by inspection. Hence the sum of the two quantities is even (by Theorem). It follows that 3k+1 – 2 is even, which is what we needed to show.” Theorem The sum of any two even integers is even. Proof: Suppose m and n are [particular but arbitrarily chosen] even integers. [We must show that m + n is even.] By definition of even, m = 2r and n = 2s for some integers r and s. Then Let t = r + s. Note that t is an integer because it is a sum of integers. Hence m + n = 2t where t is an integer. It follows by definition of even that m + n is even. [This is what we needed to show.]

Problem 34E a. Use mathematical induction to prove that any checkerboard with dimensions 2 × 3n 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 dimensions 2m × 3n can be completely covered with L-shaped trominoes.

Problem 35E Let m and n be any integers that are greater than or equal to 1. a. Prove that a necessary condition for an m × n checkerboard to be completely coverable by L-shaped trominoes is that mn be divisible by 3. ________________ b. Prove that having mn be divisible by 3 is not a sufficient condition for an m × n checkerboard to be completely coverable by L-shaped trominoes.

Problem 37E 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.

Problem 36E 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 first dot beats the team represented by the second dot. For example, the directed graph below shows one outcome of a round-robin tournament involving five teams, A, B, C, D, and E. Use mathematical induction to show that in any round-robin tournament involving n teams, where n > 2, it is possible to label the teams T1, T2, ..., Tn so that Ti beats 7i+1 for all i = 1, 2, ..., n – 1. (For instance, one such labeling in the example above is T1 = A , T2 = B, T3 = C, T4 = E, T5 = D.) (Hint: Given k + 1 teams, pick one— say T'— and apply the inductive hypothesis to the remaining teams to obtain an ordering T1, T2, ..., Tk. Consider three cases: T' beats T1, T' loses to the first m teams (where 1 ? m ? k – 1) and beats the (m + 1)st team, and T' loses to all the other teams.)

Problem 39E 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 angles of any n-sided convex polygon add up to 180(n –2) degrees.

Problem 38E Suppose that n a’s and n b’s 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 find a starting point so that if one travels around the circle in a clockwise direction, the number of a’s one has passed is never less than the number of b’s one has passed. For example, in the diagram shown below, one could start at the a with an asterisk.

Problem 7E For each positive integer n, let P(n) be the property 2n < (n + 1)!. a. Write P(2). Is P(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?