 4.5.4.5.1: Prove that the program segment y := 1 z :=x + y is correct with res...
 4.5.4.5.2: Verify that the program segment if x < 0 then x := 0 is correct wit...
 4.5.4.5.3: Verify that the program segment x := 2 z := x + y if y > 0 then z :...
 4.5.4.5.4: Verify that the program segment if x < y then min := x else min := ...
 4.5.4.5.5: Devise a rule of inference for verificatiQn of partial correctness ...
 4.5.4.5.6: Use the rule of inference developed in Exercise 5 to verify that th...
 4.5.4.5.7: Use a loop invariant to prove that the following program segment fo...
 4.5.4.5.8: Prove that the iterative program for finding In given in Section 4....
 4.5.4.5.9: Provide all the details in the proof of correctness given in Exampl...
 4.5.4.5.10: Suppose that both the conditional statement Po + PI and the progr...
 4.5.4.5.11: Suppose that both the program assertion p{S}qo and the conditional ...
 4.5.4.5.12: This program computes quotients and remainders. r := a q := 0 while...
 4.5.4.5.13: Use a loop invariant to verify that the Euclidean algorithm (Algori...
Solutions for Chapter 4.5: Induction and Recursion
Full solutions for Discrete Mathematics and Its Applications  6th Edition
ISBN: 9780073229720
Solutions for Chapter 4.5: Induction and Recursion
Get Full SolutionsSince 13 problems in chapter 4.5: Induction and Recursion have been answered, more than 38961 students have viewed full stepbystep solutions from this chapter. Discrete Mathematics and Its Applications was written by and is associated to the ISBN: 9780073229720. This expansive textbook survival guide covers the following chapters and their solutions. Chapter 4.5: Induction and Recursion includes 13 full stepbystep solutions. This textbook survival guide was created for the textbook: Discrete Mathematics and Its Applications, edition: 6.

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

Cholesky factorization
A = CTC = (L.J]))(L.J]))T for positive definite A.

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

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.

Four Fundamental Subspaces C (A), N (A), C (AT), N (AT).
Use AT for complex A.

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.

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.

Independent vectors VI, .. " vk.
No combination cl VI + ... + qVk = zero vector unless all ci = O. If the v's are the columns of A, the only solution to Ax = 0 is x = o.

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.

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.

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

Multiplication Ax
= Xl (column 1) + ... + xn(column n) = combination of columns.

Partial pivoting.
In each column, choose the largest available pivot to control roundoff; all multipliers have leij I < 1. See condition number.

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

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

Row picture of Ax = b.
Each equation gives a plane in Rn; the planes intersect at x.

Subspace S of V.
Any vector space inside V, including V and Z = {zero vector only}.

Symmetric factorizations A = LDLT and A = QAQT.
Signs in A = signs in D.

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