 5.2.1E: Use strong induction to show that if you can run one mile or two mi...
 5.2.3E: Let P(n) be the statement that a postage of ncentscanbe formed usin...
 5.2.4E: Let P (n) be the statement that a postage of n cents can be formed ...
 5.2.5E: a) Determine which amounts of postage can be formed using just 4ce...
 5.2.6E: a) Determine which amounts of postage can be formed using just 3ce...
 5.2.7E: Which amounts of money can be formed using just two dollar bills a...
 5.2.9E: Use strong induction to prove that is irrational. [Hint: Let P (n) ...
 5.2.11E: Consider this variation of the game of Nim. The game begins with n ...
 5.2.13E: A jigsaw puzzle is put together by successively joining pieces that...
 5.2.15E: Prove that the first player has a winning strategy for the game of ...
 5.2.16E: Prove that the first player has a winning strategy for the game of ...
 5.2.17E: Use strong induction to show that if a simple polygon with at least...
 5.2.18E: Use strong induction to show that when a simple polygon P with cons...
 5.2.19E: Pick's theorem says that the area of a simple polygon P in the plan...
 5.2.20E: Suppose that P is a simple polygon with vertices v1, v2,…. vn liste...
 5.2.21E: In the proof of Lemma 1 we mentioned that many incorrect methods fo...
 5.2.22E: Let P(n) be the statement that when nonintersecting diagonals are d...
 5.2.23E: Let E(n) be the statement that in a triangulation of a simple polyg...
 5.2.24E: A stable assignment, defined in the preamble to Exercise 60 in Sect...
 5.2.25E: Suppose that P(n) is a propositional function. Determine for which ...
 5.2.26E: Suppose that P(n) is a propositional function. Determine for which ...
 5.2.27E: Show that if the statement P(n) is true for infinitely many positiv...
 5.2.28E: Let b be a fixed integer and j a fixed positive integer. Show that ...
 5.2.29E: What is wrong with this "proof" by strong induction? "Theorem" For ...
 5.2.31E: Show that strong induction is a valid method of proof by showing th...
 5.2.33E: Show that we can prove that P(n, k) is true for all pairs of positi...
 5.2.35E: Show that if a 1, a 2…. an are n distinct real numbers, exactly n ?...
 5.2.37E: Let a be an integer and d be a positive integer. Show that the inte...
 5.2.38E: Use mathematical induction to show that a rectangular checkerboard ...
 5.2.39E: Can you use the wellordering property to prove the statement: "Eve...
 5.2.40E: Use the wellordering principle to show that if x and y are real nu...
 5.2.41E: Show that the wellordering property can be proved when the princip...
 5.2.42E: Show that the principle of mathematical induction and strong induct...
 5.2.43E: Show that we can prove the wellordering property when we take stro...
Solutions for Chapter 5.2: Discrete Mathematics and Its Applications 7th Edition
Full solutions for Discrete Mathematics and Its Applications  7th Edition
ISBN: 9780073383095
Solutions for Chapter 5.2
Get Full SolutionsChapter 5.2 includes 34 full stepbystep solutions. Since 34 problems in chapter 5.2 have been answered, more than 203595 students have viewed full stepbystep solutions from this chapter. Discrete Mathematics and Its Applications was written by and is associated to the ISBN: 9780073383095. This expansive textbook survival guide covers the following chapters and their solutions. This textbook survival guide was created for the textbook: Discrete Mathematics and Its Applications, edition: 7.

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

Column space C (A) =
space of all combinations of the columns of A.

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

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

GramSchmidt orthogonalization A = QR.
Independent columns in A, orthonormal columns in Q. Each column q j of Q is a combination of the first j columns of A (and conversely, so R is upper triangular). Convention: diag(R) > o.

Hermitian matrix A H = AT = A.
Complex analog a j i = aU of a symmetric matrix.

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

Hypercube matrix pl.
Row n + 1 counts corners, edges, faces, ... of a cube in Rn.

Length II x II.
Square root of x T x (Pythagoras in n dimensions).

Linearly dependent VI, ... , Vn.
A combination other than all Ci = 0 gives L Ci Vi = O.

Lucas numbers
Ln = 2,J, 3, 4, ... satisfy Ln = L n l +Ln 2 = A1 +A~, with AI, A2 = (1 ± /5)/2 from the Fibonacci matrix U~]' Compare Lo = 2 with Fo = O.

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

Network.
A directed graph that has constants Cl, ... , Cm associated with the edges.

Particular solution x p.
Any solution to Ax = b; often x p has free variables = o.

Projection matrix P onto subspace S.
Projection p = P b is the closest point to b in S, error e = b  Pb is perpendicularto S. p 2 = P = pT, eigenvalues are 1 or 0, eigenvectors are in S or S...L. If columns of A = basis for S then P = A (AT A) 1 AT.

Pseudoinverse A+ (MoorePenrose inverse).
The n by m matrix that "inverts" A from column space back to row space, with N(A+) = N(AT). A+ A and AA+ are the projection matrices onto the row space and column space. Rank(A +) = rank(A).

Row space C (AT) = all combinations of rows of A.
Column vectors by convention.

Saddle point of I(x}, ... ,xn ).
A point where the first derivatives of I are zero and the second derivative matrix (a2 II aXi ax j = Hessian matrix) is indefinite.

Singular Value Decomposition
(SVD) A = U:E VT = (orthogonal) ( diag)( orthogonal) First r columns of U and V are orthonormal bases of C (A) and C (AT), AVi = O'iUi with singular value O'i > O. Last columns are orthonormal bases of nullspaces.

Skewsymmetric matrix K.
The transpose is K, since Kij = Kji. Eigenvalues are pure imaginary, eigenvectors are orthogonal, eKt is an orthogonal matrix.