 5.R.1RQ: a) Can you use the principle of mathematical induction to find a fo...
 5.R.2RQ: a) For which positive integers n is 11 n + 17 ? 2n?________________...
 5.R.4RQ: Give two different examples of proofs that use strong induction.
 5.R.5RQ: a) State the wellordering property for the set of positive integer...
 5.R.3RQ: a) Which amounts of postage can be formed using only 5cent and 9c...
 5.R.6RQ: a) Explain why a function f from the set of positive integers to th...
 5.R.8RQ: a) Explain why a sequence an is well defined if it is defined recur...
 5.R.7RQ: a) Give a recursive definition of the Fibonacci numbers.___________...
 5.R.9RQ: Give two examples of how wellformed formulae are defined recursive...
 5.R.10RQ: a) Give a recursive definition of the length of a string.__________...
 5.R.12RQ: Describe a recursive algorithm for computing the greatest common di...
 5.R.11RQ: a) What is a recursive algorithm?________________b) Describe a recu...
 5.R.14RQ: a) Does testing a computer program to see whether it produces the c...
 5.R.13RQ: a) Describe the merge sort algorithm.________________b) Use the mer...
 5.R.15RQ: What techniques can you use to show that a long computer program is...
 5.R.16RQ: What is a loop invariant? How is a loop invariant used?
Solutions for Chapter 5.R: Discrete Mathematics and Its Applications 7th Edition
Full solutions for Discrete Mathematics and Its Applications  7th Edition
ISBN: 9780073383095
Solutions for Chapter 5.R
Get Full SolutionsThis 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. Since 16 problems in chapter 5.R have been answered, more than 198269 students have viewed full stepbystep solutions from this chapter. Chapter 5.R includes 16 full stepbystep solutions. Discrete Mathematics and Its Applications was written by and is associated to the ISBN: 9780073383095.

Big formula for n by n determinants.
Det(A) is a sum of n! terms. For each term: Multiply one entry from each row and column of A: rows in order 1, ... , nand column order given by a permutation P. Each of the n! P 's has a + or  sign.

Change of basis matrix M.
The old basis vectors v j are combinations L mij Wi of the new basis vectors. The coordinates of CI VI + ... + cnvn = dl wI + ... + dn Wn are related by d = M c. (For n = 2 set VI = mll WI +m21 W2, V2 = m12WI +m22w2.)

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

Eigenvalue A and eigenvector x.
Ax = AX with x#O so det(A  AI) = o.

Fourier matrix F.
Entries Fjk = e21Cijk/n give orthogonal columns FT F = nI. Then y = Fe is the (inverse) Discrete Fourier Transform Y j = L cke21Cijk/n.

Full column rank r = n.
Independent columns, N(A) = {O}, no free variables.

Graph G.
Set of n nodes connected pairwise by m edges. A complete graph has all n(n  1)/2 edges between nodes. A tree has only n  1 edges and no closed loops.

Hankel matrix H.
Constant along each antidiagonal; hij depends on i + j.

Kirchhoff's Laws.
Current Law: net current (in minus out) is zero at each node. Voltage Law: Potential differences (voltage drops) add to zero around any closed loop.

Kronecker product (tensor product) A ® B.
Blocks aij B, eigenvalues Ap(A)Aq(B).

Left inverse A+.
If A has full column rank n, then A+ = (AT A)I AT has A+ A = In.

Minimal polynomial of A.
The lowest degree polynomial with meA) = zero matrix. This is peA) = det(A  AI) if no eigenvalues are repeated; always meA) divides peA).

Norm
IIA II. The ".e 2 norm" of A is the maximum ratio II Ax II/l1x II = O"max· Then II Ax II < IIAllllxll and IIABII < IIAIIIIBII and IIA + BII < IIAII + IIBII. Frobenius norm IIAII} = L La~. The.e 1 and.e oo norms are largest column and row sums of laij I.

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.

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 •

Rank r (A)
= number of pivots = dimension of column space = dimension of row space.

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.

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

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.

Spectral Theorem A = QAQT.
Real symmetric A has real A'S and orthonormal q's.