 5.9.1: Consider the set of Boolean expressions defined in Example 5.9.1. G...
 5.9.2: Let S be defined as in Example 5.9.2. Give derivations showing that...
 5.9.3: Consider the MIUsystem discussed in Example 5.9.3. Give derivation...
 5.9.4: The set of arithmetic expressions over the real numbers can be defi...
 5.9.5: Another way to show that a given element is in a recursively define...
 5.9.6: To prove that every element in a recursively defined set S satisfie...
 5.9.7: A function is said to be defined recursively if, and only if, _____.
 5.9.8: Define a set S recursively as follows: I. BASE: 1 S, 2 S, 3 S, 4 S,...
 5.9.9: Define a set S recursively as follows: I. BASE: 1 S, 3 S, 5 S, 7 S,...
 5.9.10: Define a set S recursively as follows: I. BASE: 0 S, 5 S II. RECURS...
 5.9.11: Define a set S recursively as follows: I. BASE: 0 S II. RECURSION: ...
 5.9.12: Is the string M U in the MIUsystem? Use structural induction to pr...
 5.9.13: Consider the set P of parenthesis structures defined in Example 5.9...
 5.9.14: Determine whether either of the following parenthesis structures is...
 5.9.15: Give a recursive definition for the set of all strings of 0s and 1s...
 5.9.16: Give a recursive definition for the set of all strings of 0s and 1s...
 5.9.17: Give a recursive definition for the set of all strings of as and bs...
 5.9.18: Give a recursive definition for the set of all strings of as and bs...
 5.9.19: Use the definition of McCarthys 91 function in Example 5.9.6 to sho...
 5.9.20: Prove that McCarthys 91 function equals 91 for all positive integer...
 5.9.21: Use the definition of the Ackermann function in Example 5.9.7 to co...
 5.9.22: Use the definition of the Ackermann function in Example 5.9.7 to co...
 5.9.23: Compute T (2), T (3), T (4), T (5), T (6), and T (7) for the functi...
 5.9.24: Student A tries to define a function F : Z+ Z by the rule F(n) = 1 ...
 5.9.25: Student C tries to define a function G : Z+ Z by the rule G(n) = 1 ...
Solutions for Chapter 5.9: General Recursive Definitions and Structural Induction
Full solutions for Discrete Mathematics with Applications  4th Edition
ISBN: 9780495391326
Solutions for Chapter 5.9: General Recursive Definitions and Structural Induction
Get Full SolutionsChapter 5.9: General Recursive Definitions and Structural Induction includes 25 full stepbystep solutions. This textbook survival guide was created for the textbook: Discrete Mathematics with Applications , edition: 4. Since 25 problems in chapter 5.9: General Recursive Definitions and Structural Induction have been answered, more than 51789 students have viewed full stepbystep solutions from this chapter. This expansive textbook survival guide covers the following chapters and their solutions. Discrete Mathematics with Applications was written by and is associated to the ISBN: 9780495391326.

Cofactor Cij.
Remove row i and column j; multiply the determinant by (I)i + j •

Condition number
cond(A) = c(A) = IIAIlIIAIII = amaxlamin. In Ax = b, the relative change Ilox III Ilx II is less than cond(A) times the relative change Ilob III lib II· Condition numbers measure the sensitivity of the output to change in the input.

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.

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

Free variable Xi.
Column i has no pivot in elimination. We can give the n  r free variables any values, then Ax = b determines the r pivot variables (if solvable!).

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.

lAII = l/lAI and IATI = IAI.
The big formula for det(A) has a sum of n! terms, the cofactor formula uses determinants of size n  1, volume of box = I det( A) I.

Left nullspace N (AT).
Nullspace of AT = "left nullspace" of A because y T A = OT.

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

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

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

Positive definite matrix A.
Symmetric matrix with positive eigenvalues and positive pivots. Definition: x T Ax > 0 unless x = O. Then A = LDLT with diag(D» O.

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

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

Schwarz inequality
Iv·wl < IIvll IIwll.Then IvTAwl2 < (vT Av)(wT Aw) for pos def A.

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

Singular matrix A.
A square matrix that has no inverse: det(A) = o.

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

Sum V + W of subs paces.
Space of all (v in V) + (w in W). Direct sum: V n W = to}.

Wavelets Wjk(t).
Stretch and shift the time axis to create Wjk(t) = woo(2j t  k).