 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 170589 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.

Affine transformation
Tv = Av + Vo = linear transformation plus shift.

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

Commuting matrices AB = BA.
If diagonalizable, they share n eigenvectors.

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.

Diagonalization
A = S1 AS. A = eigenvalue matrix and S = eigenvector matrix of A. A must have n independent eigenvectors to make S invertible. All Ak = SA k SI.

Dot product = Inner product x T y = XI Y 1 + ... + Xn Yn.
Complex dot product is x T Y . Perpendicular vectors have x T y = O. (AB)ij = (row i of A)T(column j of B).

Echelon matrix U.
The first nonzero entry (the pivot) in each row comes in a later column than the pivot in the previous row. All zero rows come last.

Elimination matrix = Elementary matrix Eij.
The identity matrix with an extra eij in the i, j entry (i # j). Then Eij A subtracts eij times row j of A from row i.

Elimination.
A sequence of row operations that reduces A to an upper triangular U or to the reduced form R = rref(A). Then A = LU with multipliers eO in L, or P A = L U with row exchanges in P, or E A = R with an invertible E.

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

Identity matrix I (or In).
Diagonal entries = 1, offdiagonal entries = 0.

Krylov subspace Kj(A, b).
The subspace spanned by b, Ab, ... , AjIb. Numerical methods approximate A I b by x j with residual b  Ax j in this subspace. A good basis for K j requires only multiplication by A at each step.

Normal equation AT Ax = ATb.
Gives the least squares solution to Ax = b if A has full rank n (independent columns). The equation says that (columns of A)·(b  Ax) = o.

Rayleigh quotient q (x) = X T Ax I x T x for symmetric A: Amin < q (x) < Amax.
Those extremes are reached at the eigenvectors x for Amin(A) and Amax(A).

Semidefinite matrix A.
(Positive) semidefinite: all x T Ax > 0, all A > 0; A = any RT R.

Solvable system Ax = b.
The right side b is in the column space of A.

Stiffness matrix
If x gives the movements of the nodes, K x gives the internal forces. K = ATe A where C has spring constants from Hooke's Law and Ax = stretching.

Trace of A
= sum of diagonal entries = sum of eigenvalues of A. Tr AB = Tr BA.

Vector addition.
v + w = (VI + WI, ... , Vn + Wn ) = diagonal of parallelogram.

Vector space V.
Set of vectors such that all combinations cv + d w remain within V. Eight required rules are given in Section 3.1 for scalars c, d and vectors v, w.