Discrete Mathematics and Its Applications 7th Edition solutions

Discrete Mathematics and Its Applications 7
Problem 1E There are infinitely many stations on a train route. Suppose that the train stops at the first station and suppose that if the train stops at a station, then it stops at the next station. Show that the train stops at all stations.

Discrete Mathematics and Its Applications 7
Problem 2E Suppose that you know that a golfer plays the first hole of a golf course with an infinite number of holes and that if this golfer plays one hole, then the golfer goes on to play the next hole. Prove that this golfer plays every hole on the course.

Discrete Mathematics and Its Applications 7
Problem 3E Let P(n) be the statement that 12 + 22+ = n(n + 1)(2n+1)6 for the positive integer n. a) What is the statement P(1)? ________________ b) Show that P(1) is true, completing the basis step of the proof. ________________ c) What is the inductive hypothesis? ________________ d) What do

Discrete Mathematics and Its Applications 7
Problem 4E Let P(n) be the statement that 13 + 23+ ???+n3(n + 1)/2)2 for the positive integer n. a) What is the statement P(1)? ________________ b) Show that P(1) is true, completing the basis step of the proof. ________________ c) What is the inductive hypothesis? ________________ d) What do

Discrete Mathematics and Its Applications 7
Problem 5E Prove that 12 + 32 + 52 + n3 =(2 n2 + 1)2 = (n + 1) (2 n + 1)(2 n + 3)/3 whenever n is a nonnegative integer.

Discrete Mathematics and Its Applications 7
Problem 6E Prove that 1 ?1! + 2 ? 2! + ??? + n ? n! - (n + 1)! ?1 whenever n is a positive integer.

Discrete Mathematics and Its Applications 7
Problem 7E Prove that 3 + 3 ? 5 + 3 ? 52+ ??? + 3 ? 5n=3(5n+l?1)/4 whenever n is a nonnegative integer.

Discrete Mathematics and Its Applications 7
Problem 8E Prove that 2-2?7 + 2?72+???+ 2(?7)n = (1 ?(?7)n+1)/4 whenever n is a nonnegative integer.

Discrete Mathematics and Its Applications 7
Problem 9E a) Find a formula for the sum of the first n even positive integers. ________________ b) Prove the formula that you conjectured in part (a).

Discrete Mathematics and Its Applications 7
a) Find a formula for \(\frac{1}{1 \cdot 2}+\frac{1}{2 \cdot 3}+\cdots+\frac{1}{n(n+1)}\) by examining the values of this expression for small values of \(n\). b) Prove the formula you conjectured in part (a). ________________ Equation Transcription:

Discrete Mathematics and Its Applications 7
Problem 11E a) Find a formula for by examining the values of this expression for small values of n. ________________ b) Prove the formula you conjectured in part (a).

Discrete Mathematics and Its Applications 7
Prove that \(\sum_{j=0}^{n}\left(-\frac{1}{2}\right)^{j}=\frac{2^{n+1}+(-1)^{n}}{3 \cdot 2^{n}}\) whenever \(n\) is a nonnegative integer. ________________ Equation Transcription: Text Transcription: sum_{j=0}^{n}(-\frac{1}{2})^{j}=\

Discrete Mathematics and Its Applications 7
Problem 13E Prove that 12 ? 22 + 32 + (?1)n-1 n2 = (?1)n -1n(n + l)/2 whenever n is a positive integer.

Discrete Mathematics and Its Applications 7
Problem 14E Prove that for every positive integer n, (n? 1)2n +1 +2.

Discrete Mathematics and Its Applications 7
Problem 15E Prove that for every positive integer n. 1?2 + 2?3 + ??? + n(n + 1) = n(n + l)( n + 2)/3.

Discrete Mathematics and Its Applications 7
Problem 16E Prove that for every positive integer n, 1?2?3 + 2? 3?4+??? + n(n + 1)(n + 2)= n(n+ 1)(n + 2)(n + 3)/4.

Discrete Mathematics and Its Applications 7
Prove that \(\sum_{j=1}^{n} j^{4}=n(n+1)(2 n+1)\left(3 n^{2}+3 n-1\right) / 30\) whenever \(n\) is a positive integer. ________________ Equation Transcription: Text Transcription: sum_{j=1}^{n} j^{4}=n(n+1)(2 n+1)(3 n^{2}+3 n-1) / 30 n

Discrete Mathematics and Its Applications 7
Problem 18E Let P(n) be the statement that n!n. where n is an integer greater than 1. a) What is the statement P(2)? ________________ b) Show that P(2) is true, completing the basis step of the proof. ________________ c) What is the inductive hypothesis? ________________ d) What do you need t

Discrete Mathematics and Its Applications 7
Let \(P(n)\) be the statement that \(1+\frac{1}{4}+\frac{1}{9}+\cdots+\frac{1}{n^{2}}<2-\frac{1}{n}\) where \(n\) is an integer greater than 1. a) What is the statement \(P (2)\)? b) Show that \(P (2)\) is true, completing the basis step of the proof. c) What is the inductive hypothesis? d) Wha

Discrete Mathematics and Its Applications 7
Problem 20E Prove that 3n<n! if n is an integer greater than 6.

Discrete Mathematics and Its Applications 7
Problem 21E Prove that 2 n > n2 if n is an integer greater than 4.

Discrete Mathematics and Its Applications 7
Problem 22E For which nonnegative integers n is n2 ? n!? Prove your answer.

Discrete Mathematics and Its Applications 7
Problem 23E For which nonnegative integers n is 2n + 3 ? 2 n? Prove your answer.

Discrete Mathematics and Its Applications 7
Problem 25E Prove that if h > ?l, then 1 + nh ? (1 + h)n for all non- negative integers n. This is called Bernoulli's inequality.

Discrete Mathematics and Its Applications 7
Problem 26E Suppose that a and b are real numbers with 0<b<a. Prove that if n is a positive integer, then an ? bn ? nan(a?b).

Discrete Mathematics and Its Applications 7
Prove that for every positive integer \(n\), \(1+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+\cdots+\frac{1}{\sqrt{n}}>2(\sqrt{n+1}-1) \text {. }\) ________________ Equation Transcription: Text Transcription: n 1+\frac{1}{\sqrt{2}}+\frac

Discrete Mathematics and Its Applications 7
Problem 28E Prove that n2 ?7 n + 12 is nonnegative whenever n is an integer with n ? 3. In Exercises 29 and 30, Hn denotes the nth harmonic number.

Discrete Mathematics and Its Applications 7
Problem 29E Prove that H2n ? 1 + n whenever n is a nonnegative integer.

Discrete Mathematics and Its Applications 7
Problem 30E Prove that H1 + H2 + ???+ Hn = (n + 1)Hn ? n. Use mathematical induction in Exercises 31-37 to prove divisibility facts.

Discrete Mathematics and Its Applications 7
Problem 31E Prove that 2 divides n2 + n whenever n is a positive integer.

Discrete Mathematics and Its Applications 7
Problem 32E Prove that 3 divides n3+ 2n whenever n is a positive integer.

Discrete Mathematics and Its Applications 7
Problem 33E Prove that 5 divides n5 -n whenever n is a nonnegative integer.

Discrete Mathematics and Its Applications 7
Problem 34E Prove that 6 divides n3 ? n whenever n is a nonnegative integer.

Discrete Mathematics and Its Applications 7
Problem 35E Prove that n2?1 is divisible by 8 whenever n is an odd positive integer.

Discrete Mathematics and Its Applications 7
Problem 36E Prove that 21 divides 4n+1+ 52n-1 whenever n is a positive integer.

Discrete Mathematics and Its Applications 7
Problem 37E Prove that if n is a positive integer, then 133 divides 11n+1 + 122 n -1.

Discrete Mathematics and Its Applications 7
Prove that if \(A_{1}, A_{2}, \ldots, A_{n}\) and \(B_{1}, B_{2}, \ldots, B_{n}\) are sets such that \(A_{j} \subseteq B_{j}\) for \(j=1,2, \ldots, n\), then \(\bigcup_{j=1}^{n} A_{j} \subseteq \bigcup_{j=1}^{n} B_{j}\) ________________ Equation Transcription:

Discrete Mathematics and Its Applications 7
Problem 39E Prove that if A1, A 2,, An and B1, B2.,Bn are sets such that Aj ? Bj for j = 1, 2,. n, then

Discrete Mathematics and Its Applications 7
Problem 40E Prove that if A1, A2, , An and B are sets, then

Discrete Mathematics and Its Applications 7
Problem 41E Prove that if A1, A2,, An and B are sets, then

Discrete Mathematics and Its Applications 7
Prove that if \(A_{1}, A_{2}, \ldots, A_{n}\) and \(B\) are sets, then \(\begin{aligned}\left(A_{1}-B\right) & \cap\left(A_{2}-B\right) \cap \cdots \cap\left(A_{n}-B\right) \\ =&\left(A_{1} \cap A_{2} \cap \cdots \cap A_{n}\right)-B .\end{aligned}\) ________________ Equation

Discrete Mathematics and Its Applications 7
Prove that if \(A_{1}, A_{2}, \ldots, A_{n}\) are subsets of a universal set \(U\), then \(\overline{\bigcup_{k=1}^{n} A_{k}}=\bigcap_{k=1}^{n} \overline{A_{k}}\).. ________________ Equation Transcription: Text Transcription: A_{1}, A_{2}

Discrete Mathematics and Its Applications 7
Problem 44E Prove that if A1, A2,, An and B are sets, then

Discrete Mathematics and Its Applications 7
Problem 45E Prove that a set with n elements has n(n ? l)/2 subsets containing exactly two elements whenever n is an integer greater than or equal to 2.

Discrete Mathematics and Its Applications 7
Problem 46E Prove that a set with n elements has n(n ?1)(n ? 2)/6 subsets containing exactly three elements whenever n is an integer greater than or equal to 3.

Discrete Mathematics and Its Applications 7
Problem 47E Devise a greedy algorithm that uses the minimum number of towers possible to provide cell service to d buildings located at positions x1, x2.xd, from the start of the road. [Hint: At each step, go as far as possible along the road before adding a tower so as not to leave any buildings w

Discrete Mathematics and Its Applications 7
Problem 48E Use mathematical induction to prove that the algorithm you devised in Exercise 47 produces an optimal solution, that is, that it uses the fewest towers possible to provide cellular service to all buildings.

Discrete Mathematics and Its Applications 7
Problem 49E What is wrong with this "proof" that all horses are the same color? Let P(n) be the proposition that all the horses in a set of n horses are the same color. Basis Step: Clearly, P(l) is true. Inductive Step: Assume that P(k) is true, so that all the horses in any set of k horses are the

Discrete Mathematics and Its Applications 7
Problem 50E What is wrong with this "proof? "Theorem" For every positive integer n, Basis Step: The formula is true for n = 1. Inductive Step: Suppose that . Then= By the inductive hypothesis, completing the inductive step.

Discrete Mathematics and Its Applications 7
Problem 51E What is wrong with this "proof"? "Theorem" For every positive integer n, if x and y are positive integers with max(x, y) = n, then x = y. Basis Step: Suppose that n = 1. If max(x, y) = 1 and x and y are positive integers, we have x = 1 and y = 1. Inductive Step: Let k be a positive inte

Discrete Mathematics and Its Applications 7
Problem 52E Suppose that m and n are positive integers with m > n and f is a function from {1,2 .m} to {1,2 .n}.Use mathematical induction on the variable 11 to show- that f is not one-to-one.

Discrete Mathematics and Its Applications 7
Use mathematical induction to show that \(n\) people can divide a cake (where each person gets one or more separate pieces of the cake) so that the cake is divided fairly, that is, in the sense that each person thinks he or she got at least \((1 / n)\) th of the cake. [Hint: For the inductive step, t

Discrete Mathematics and Its Applications 7
Problem 55E A knight on a chessboard can move one space horizontally (in either direction) and two spaces vertically (in either direction) or two spaces horizontally (in either direction) and one space vertically (in either direction). Suppose that we have an infinite chessboard, made up of all squ

Discrete Mathematics and Its Applications 7
Problem 56E Suppose that where a and b are real numbers. Show that for every positive integer n.

Discrete Mathematics and Its Applications 7
Problem 57E (Requires calculus) Use mathematical induction to prove that the derivative of f (x) = xn equals nxn?1 whenever n is a positive integer. (For the inductive step, use the product rule for derivatives.)

Discrete Mathematics and Its Applications 7
Problem 58E Suppose that A and B are square matrices with the property AB = BA. Show that ABn = BnA for every positive integer n.

Discrete Mathematics and Its Applications 7
Problem 59E Suppose that m is a positive integer. Use mathematical induction to prove that if a and b are integers with a ? b (mod m), then ak = bk (mod m) whenever k is a nonnegative integer.

Discrete Mathematics and Its Applications 7
Problem 60E Use mathematical induction to show that (p1 ? p2? . ? pn ) is equivalent to that p1? p2 ? ???? pn whenever p1 , p2, . pn are propositions.

Discrete Mathematics and Its Applications 7
Problem 61E Show that is a tautology whenever p1 , p2, . pn are propositions, where n ? 2.

Discrete Mathematics and Its Applications 7
Problem 62E Show that n lines separate the plane into (n2 + n + 2)/2 regions if no two of these lines are parallel and no three pass through a common point.

Discrete Mathematics and Its Applications 7
Problem 63E Let a1 , a2, . an be positive real numbers. The arithmetic mean of these numbers is defined by A = (a1+ , a2,+ . +an )/n. and the geometric mean of these numbers is defined by G = (a1 a2, . an)1/n. Use mathematical induction to prove that A ? G.

Discrete Mathematics and Its Applications 7
Problem 64E Use mathematical induction to prove Lemma 3 of Section 4.3, which states that if p is a prime and p| a1 , a2, . an where ai,- is an integer for i = 1. 2, 3 n, then p|ai, for some integer i.

Discrete Mathematics and Its Applications 7
Show that if \(n\) is a positive integer, then \(\sum_{\left\{a_{1}, \ldots, a_{k}\right\} \subseteq\{1,2, \ldots, n\}} \frac{1}{a_{1} a_{2} \cdots a_{k}}=n\) . (Here the sum is over all nonempty subsets of the set of the \(n\) smallest positive integers.) ________________

Discrete Mathematics and Its Applications 7
Problem 67E Show that if A1, A2,, An are sets where n ? 2, and for all pairs of integers i and j with 1 ? i<j ?n either Aj is a subset of Aj or Aj is a subset of Ai then there is an integer j, 1 ? i ? n such that Ai is a subset of Aj for all integers j with 1 ? j ? n.

Discrete Mathematics and Its Applications 7
Problem 68E A guest at a party is a celebrity if this person is known by every other guest, but knows none of them. There is at most one celebrity at a party, for if there were two, they would know each other. A particular party may have no celebrity. Your assignment is to find the celebrity, if on

Discrete Mathematics and Its Applications 7
Problem 69E Find G(l), G(2), G(3), and G(4).

Discrete Mathematics and Its Applications 7
Problem 71E Prove that G(n) = 2n ? 4 for n ?4.

Discrete Mathematics and Its Applications 7
Problem 72E Show that it is possible to arrange the numbers 1,2 ,,n in a row so that the average of any two of these numbers never appears between them. [Hint: Show that it suffices to prove this fact when n is a power of 2. Then use mathematical induction to prove the result when n is a power of 2

Discrete Mathematics and Its Applications 7
Problem 73E Show that if I1, I2.. In is a collection of open intervals on the real number line, n ? 2, and every pair of these intervals has a nonempty intersection, that is, whenever 1 ? i ?n and 1 ? j ? n, then the intersection of all these sets is nonempty, that is, (Recall that an open in

Discrete Mathematics and Its Applications 7
Problem 74E Suppose that we want to prove that for all positive integers n. a) Show that if we try to prove this inequality using mathematical induction, the basis step works, but the inductive step fails. ________________ b) Show that mathematical induction can be used to prove the stronger

Discrete Mathematics and Its Applications 7
Problem 75E Let n be an even positive integer. Show that when n people stand in a yard at mutually distinct distances and each person throws a pie at their nearest neighbor, it is possible that everyone is hit by a pie.

Discrete Mathematics and Its Applications 7
Problem 76E Construct a tiling using right triominoes of the 4 4 checkerboard with the square in the upper left corner removed.

Discrete Mathematics and Its Applications 7
Problem 77E Construct a tiling using right triominoes of the 88 checkerboard with the square in the upper left corner removed.

Discrete Mathematics and Its Applications 7
Problem 78E Prove or disprove that all checkerboards of these shapes can be completely covered using right triominoes whenever n is a positive integer. a) 3 2 n ________________ b) 6 2 n ________________ c) 3 n 3 n ________________ d) 6 n 6 n

Discrete Mathematics and Its Applications 7
Problem 79E Show that a three-dimensional 2 n 2n 2 n checkerboard with one 1 1 1 cube missing can be completely covered by 2 2 2 cubes with one lll cube removed.

Discrete Mathematics and Its Applications 7
Problem 80E Show that an n n checkerboard with one square removed can be completely covered using right triominoes if n > 5, n is odd. and 3 ? n

Discrete Mathematics and Its Applications 7
Problem 81E Show that a 5 x 5 checkerboard with a corner square removed can be tiled using right triominoes.

Discrete Mathematics and Its Applications 7
Problem 82E Find a 5 5 checkerboard with a square removed that cannot be tiled using right triominoes. Prove that such a tiling does not exist for this board.

Discrete Mathematics and Its Applications 7
Problem 83E Use the principle of mathematical induction to show that P(n) is true for n = b, b + 1, b + 2,, where b is an integer, if P(b) is true and the conditional statement P(k) ? P(k + 1) is true for all integers k with k ? b.