 5.1.1E: There are infinitely many stations on a train route. Suppose that t...
 5.1.2E: Suppose that you know that a golfer plays the first hole of a golf ...
 5.1.3E: Let P(n) be the statement that 12 + 22+ = n(n + 1)(2n+1)6 for the p...
 5.1.4E: Let P(n) be the statement that 13 + 23+ ???+n3(n + 1)/2)2 for the p...
 5.1.5E: Prove that 12 + 32 + 52 + …n3 =(2 n2 + 1)2 = (n + 1) (2 n + 1)(2 n ...
 5.1.6E: Prove that 1 ?1! + 2 ? 2! + ??? + n ? n!  (n + 1)! ?1 whenever n i...
 5.1.7E: Prove that 3 + 3 ? 5 + 3 ? 52+ ??? + 3 ? 5n=3(5n+l?1)/4 whenever n ...
 5.1.8E: Prove that 22?7 + 2?72+???+ 2(?7)n = (1 ?(?7)n+1)/4 whenever n is ...
 5.1.9E: a) Find a formula for the sum of the first n even positive integers...
 5.1.10E: a) Find a formula for by examining the values of this expression fo...
 5.1.11E: a) Find a formula for by examining the values of this expression fo...
 5.1.12E: Prove that whenever n is a nonnegative integer.
 5.1.13E: Prove that 12 ? 22 + 32 + (?1)n1 n2 = (?1)n 1n(n + l)/2 whenever ...
 5.1.14E: Prove that for every positive integer n, (n? 1)2n +1 +2.
 5.1.15E: Prove that for every positive integer n.1?2 + 2?3 + ??? + n(n + 1) ...
 5.1.16E: Prove that for every positive integer n,1?2?3 + 2? 3?4+??? + n(n + ...
 5.1.17E: Prove that j4 = n(n + 1)(2 n + 1)(3 n2 + 3 n ?1)/30 whenever n is a...
 5.1.18E: Let P(n) be the statement that n!n. where n is an integer greater t...
 5.1.19E: Let P(n)be the statement that where n is an integer greater than 1....
 5.1.20E: Prove that 3n<n! if n is an integer greater than 6.
 5.1.21E: Prove that 2 n > n2 if n is an integer greater than 4.
 5.1.22E: For which nonnegative integers n is n2 ? n!? Prove your answer.
 5.1.23E: For which nonnegative integers n is 2n + 3 ? 2 n? Prove your answer.
 5.1.25E: Prove that if h > ?l, then 1 + nh ? (1 + h)n for all non negative ...
 5.1.26E: Suppose that a and b are real numbers with 0<b<a. Prove that if n i...
 5.1.27E: Prove that for every positive integer n,
 5.1.28E: Prove that n2 ?7 n + 12 is nonnegative whenever n is an integer wit...
 5.1.29E: Prove that H2n ? 1 + n whenever n is a nonnegative integer.
 5.1.30E: Prove thatH1 + H2 + ???+ Hn = (n + 1)Hn ? n.Use mathematical induct...
 5.1.31E: Prove that 2 divides n2 + n whenever n is a positive integer.
 5.1.32E: Prove that 3 divides n3+ 2n whenever n is a positive integer.
 5.1.33E: Prove that 5 divides n5 n whenever n is a nonnegative integer.
 5.1.34E: Prove that 6 divides n3 ? n whenever n is a nonnegative integer.
 5.1.35E: Prove that n2?1 is divisible by 8 whenever n is an odd positive int...
 5.1.36E: Prove that 21 divides 4n+1+ 52n1 whenever n is a positive integer.
 5.1.37E: Prove that if n is a positive integer, then 133 divides 11n+1 + 122...
 5.1.38E: Prove that if A1. A2, Anand B1, B2 Bn„ are sets such that Aj ? Bj f...
 5.1.39E: Prove that if A1, A 2,…, An and B1, B2….,Bn are sets such that Aj ?...
 5.1.40E: Prove that if A1, A2, …, An and B are sets, then
 5.1.41E: Prove that if A1, A2,…, An and B are sets, then
 5.1.42E: Prove that if A1, A2,…, An and B are sets, then
 5.1.43E: Prove that if A1, A2,…, An are subsets of a universal
 5.1.44E: Prove that if A1, A2,…, An and B are sets, then
 5.1.45E: Prove that a set with n elements has n(n ? l)/2 subsets containing ...
 5.1.46E: Prove that a set with n elements has n(n ?1)(n ? 2)/6 subsets conta...
 5.1.47E: Devise a greedy algorithm that uses the minimum number of towers po...
 5.1.48E: Use mathematical induction to prove that the algorithm you devised ...
 5.1.49E: What is wrong with this "proof" that all horses are the same color?...
 5.1.50E: What is wrong with this "proof?"Theorem" For every positive integer...
 5.1.51E: What is wrong with this "proof"?"Theorem" For every positive intege...
 5.1.52E: Suppose that m and n are positive integers with m > n and f is a fu...
 5.1.53E: Use mathematical induction to show that 11 people can divide a cake...
 5.1.55E: A knight on a chessboard can move one space horizontally (in either...
 5.1.56E: Suppose that where a and b are real numbers. Show that for every po...
 5.1.57E: (Requires calculus) Use mathematical induction to prove that the de...
 5.1.58E: Suppose that A and B are square matrices with the property AB = BA....
 5.1.59E: Suppose that m is a positive integer. Use mathematical induction to...
 5.1.60E: Use mathematical induction to show that ¬ (p1 ? p2? …. ? pn ) is eq...
 5.1.61E: Show that is a tautology whenever p1 , p2, …. pn are propositions, ...
 5.1.62E: Show that n lines separate the plane into (n2 + n + 2)/2 regions if...
 5.1.63E: Let a1 , a2, …. an be positive real numbers. The arithmetic mean of...
 5.1.64E: Use mathematical induction to prove Lemma 3 of Section 4.3, which s...
 5.1.65E: Show that if n is a positive integer, then (Here the sum is over al...
 5.1.67E: Show that if A1, A2,…, An are sets where n ? 2, and for all pairs o...
 5.1.68E: A guest at a party is a celebrity if this person is known by every ...
 5.1.69E: Find G(l), G(2), G(3), and G(4).
 5.1.71E: Prove that G(n) = 2n ? 4 for n ?4.
 5.1.72E: Show that it is possible to arrange the numbers 1,2 ,…,n in a row s...
 5.1.73E: Show that if I1, I2….. In is a collection of open intervals on the ...
 5.1.74E: Suppose that we want to prove that for all positive integers n.a) S...
 5.1.75E: Let n be an even positive integer. Show that when n people stand in...
 5.1.76E: Construct a tiling using right triominoes of the 4 × 4 checkerboard...
 5.1.77E: Construct a tiling using right triominoes of the 8×8 checkerboard w...
 5.1.78E: Prove or disprove that all checkerboards of these shapes can be com...
 5.1.79E: Show that a threedimensional 2 n × 2n × 2 n checkerboard with one ...
 5.1.80E: Show that an n × n checkerboard with one square removed can be comp...
 5.1.81E: Show that a 5 x 5 checkerboard with a corner square removed can be ...
 5.1.82E: Find a 5 × 5 checkerboard with a square removed that cannot be tile...
 5.1.83E: Use the principle of mathematical induction to show that P(n) is tr...
Solutions for Chapter 5.1: Discrete Mathematics and Its Applications 7th Edition
Full solutions for Discrete Mathematics and Its Applications  7th Edition
ISBN: 9780073383095
Solutions for Chapter 5.1
Get Full SolutionsThis textbook survival guide was created for the textbook: Discrete Mathematics and Its Applications, edition: 7. Discrete Mathematics and Its Applications was written by and is associated to the ISBN: 9780073383095. Since 79 problems in chapter 5.1 have been answered, more than 133767 students have viewed full stepbystep solutions from this chapter. This expansive textbook survival guide covers the following chapters and their solutions. Chapter 5.1 includes 79 full stepbystep solutions.

Associative Law (AB)C = A(BC).
Parentheses can be removed to leave ABC.

Covariance matrix:E.
When random variables Xi have mean = average value = 0, their covariances "'£ ij are the averages of XiX j. With means Xi, the matrix :E = mean of (x  x) (x  x) T is positive (semi)definite; :E is diagonal if the Xi are independent.

Cramer's Rule for Ax = b.
B j has b replacing column j of A; x j = det B j I det A

Determinant IAI = det(A).
Defined by det I = 1, sign reversal for row exchange, and linearity in each row. Then IAI = 0 when A is singular. Also IABI = IAIIBI and

Free columns of A.
Columns without pivots; these are combinations of earlier columns.

Free variable Xi.
Column i has no pivot in elimination. We can give the n  r free variables any values, then Ax = b determines the r pivot variables (if solvable!).

Fundamental Theorem.
The nullspace N (A) and row space C (AT) are orthogonal complements in Rn(perpendicular from Ax = 0 with dimensions rand n  r). Applied to AT, the column space C(A) is the orthogonal complement of N(AT) in Rm.

Hessenberg matrix H.
Triangular matrix with one extra nonzero adjacent diagonal.

Indefinite matrix.
A symmetric matrix with eigenvalues of both signs (+ and  ).

Linear combination cv + d w or L C jV j.
Vector addition and scalar multiplication.

Multiplicities AM and G M.
The algebraic multiplicity A M of A is the number of times A appears as a root of det(A  AI) = O. The geometric multiplicity GM is the number of independent eigenvectors for A (= dimension of the eigenspace).

Nilpotent matrix N.
Some power of N is the zero matrix, N k = o. The only eigenvalue is A = 0 (repeated n times). Examples: triangular matrices with zero diagonal.

Nullspace N (A)
= All solutions to Ax = O. Dimension n  r = (# columns)  rank.

Orthonormal vectors q 1 , ... , q n·
Dot products are q T q j = 0 if i =1= j and q T q i = 1. The matrix Q with these orthonormal columns has Q T Q = I. If m = n then Q T = Q 1 and q 1 ' ... , q n is an orthonormal basis for Rn : every v = L (v T q j )q j •

Pascal matrix
Ps = pascal(n) = the symmetric matrix with binomial entries (i1~;2). Ps = PL Pu all contain Pascal's triangle with det = 1 (see Pascal in the index).

Rank one matrix A = uvT f=. O.
Column and row spaces = lines cu and cv.

Reduced row echelon form R = rref(A).
Pivots = 1; zeros above and below pivots; the r nonzero rows of R give a basis for the row space of A.

Right inverse A+.
If A has full row rank m, then A+ = AT(AAT)l has AA+ = 1m.

Rotation matrix
R = [~ CS ] rotates the plane by () and R 1 = RT rotates back by (). Eigenvalues are eiO and eiO , eigenvectors are (1, ±i). c, s = cos (), sin ().

Transpose matrix AT.
Entries AL = Ajj. AT is n by In, AT A is square, symmetric, positive semidefinite. The transposes of AB and AI are BT AT and (AT)I.