 21.21.1: What is the smallest positive real number?
 21.21.2: Prove by the techniques of this section that 1 C 2 C 3 C C n D 1 2 ...
 21.21.3: Prove by the techniques of this section that n < 2n for all n 2 N.
 21.21.4: Prove by the techniques of this section that n n n for all positive...
 21.21.5: Prove by the techniques of this section that 2n n 4 n for all natur...
 21.21.6: Recall Proposition 13.2 that for all positive integers n we have 1 ...
 21.21.7: The inequality Fn > 1:6n is true once n is big enough. Do some calc...
 21.21.8: Calculate the sum of the first n Fibonacci numbers for n D 0; 1; 2;...
 21.21.9: . Criticize the following statement and proof: Statement. All natur...
 21.21.10: In Section 17 we discussed that Pascals triangle and the triangle o...
 21.21.11: Prove the generalized Addition Principle by use of the WellOrderin...
Solutions for Chapter 21: Smallest Counterexample
Full solutions for Mathematics: A Discrete Introduction  3rd Edition
ISBN: 9780840049421
Solutions for Chapter 21: Smallest Counterexample
Get Full SolutionsThis expansive textbook survival guide covers the following chapters and their solutions. Since 11 problems in chapter 21: Smallest Counterexample have been answered, more than 9894 students have viewed full stepbystep solutions from this chapter. Mathematics: A Discrete Introduction was written by and is associated to the ISBN: 9780840049421. Chapter 21: Smallest Counterexample includes 11 full stepbystep solutions. This textbook survival guide was created for the textbook: Mathematics: A Discrete Introduction, edition: 3.

Back substitution.
Upper triangular systems are solved in reverse order Xn to Xl.

Characteristic equation det(A  AI) = O.
The n roots are the eigenvalues of A.

Companion matrix.
Put CI, ... ,Cn in row n and put n  1 ones just above the main diagonal. Then det(A  AI) = ±(CI + c2A + C3A 2 + .•. + cnA nl  An).

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

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.

Full row rank r = m.
Independent rows, at least one solution to Ax = b, column space is all of Rm. Full rank means full column rank or full row rank.

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

Iterative method.
A sequence of steps intended to approach the desired solution.

Jordan form 1 = M 1 AM.
If A has s independent eigenvectors, its "generalized" eigenvector matrix M gives 1 = diag(lt, ... , 1s). The block his Akh +Nk where Nk has 1 's on diagonall. Each block has one eigenvalue Ak and one eigenvector.

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

Matrix multiplication AB.
The i, j entry of AB is (row i of A)·(column j of B) = L aikbkj. By columns: Column j of AB = A times column j of B. By rows: row i of A multiplies B. Columns times rows: AB = sum of (column k)(row k). All these equivalent definitions come from the rule that A B times x equals A times B x .

Similar matrices A and B.
Every B = MI AM has the same eigenvalues as A.

Simplex method for linear programming.
The minimum cost vector x * is found by moving from comer to lower cost comer along the edges of the feasible set (where the constraints Ax = b and x > 0 are satisfied). Minimum cost at a comer!

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

Special solutions to As = O.
One free variable is Si = 1, other free variables = o.

Spectrum of A = the set of eigenvalues {A I, ... , An}.
Spectral radius = max of IAi I.

Toeplitz matrix.
Constant down each diagonal = timeinvariant (shiftinvariant) filter.

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

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.

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.