 5.3.1E: Find f(1), f (2), f (3), and f (4) if f (n) is defined recursively ...
 5.3.2E: Find f (l), f (2), f (3), f (4), and f (5) if f (n) is defined recu...
 5.3.3E: Find f (2), f (3), f (4), and f (5) if f is defined recursively by ...
 5.3.4E: Find f (2), f (3), f (4), and f (5) if f is defined recursively by ...
 5.3.5E: Determine whether each of these proposed definitions is a valid rec...
 5.3.7E: Give a recursive definition of the sequence {an}, n=1, 2, 3…. ifa) ...
 5.3.8E: Give a recursive definition of the sequence {an}, n = 1,2, 3.…ifa) ...
 5.3.9E: Let F be the function such that F(n) is the sum of the first /i pos...
 5.3.10E: Give a recursive definition of Sm (n), the sum of the integer m and...
 5.3.11E: Give a recursive definition of Pm(n), the product of the integer m ...
 5.3.12E: Prove that when n is a positive integer.
 5.3.13E: Prove that when n is a positive integer.
 5.3.14E: Show that when n is a positive integer.
 5.3.15E: Show that when n is a positive integer.
 5.3.16E: Show that when n is a positive integer.
 5.3.17E: Determine the number of divisions used by the Euclidean algorithm t...
 5.3.18E: Let Show that when n is a positive integer.
 5.3.19E: By taking determinants of both sides of the equation in Exercise 18...
 5.3.20E: Give a recursive definition of the functions max and min so that ma...
 5.3.21E: Let a1, a2,…. an and b1,b2.... bn be real numbers. Use the recursiv...
 5.3.22E: Show that the set S defined by 1 ? S and s + 1 ? S whenever s ? S a...
 5.3.23E: Give a recursive definition of the set of positive integers that ar...
 5.3.24E: Give a recursive definition ofa) the set of odd positive integers._...
 5.3.25E: Give a recursive definition ofa) the set of even integers._________...
 5.3.26E: Let S be the subset of the set of ordered pairs of integers defined...
 5.3.27E: Let S be the subset of the set of ordered pairs of integers defined...
 5.3.28E: Give a recursive definition of each of these sets of ordered pairs ...
 5.3.29E: Give a recursive definition of each of these sets of ordered pairs ...
 5.3.31E: Define wellformed formulae of sets, variables representing sets, a...
 5.3.32E: a) Give a recursive definition of the function ones(s),which counts...
 5.3.33E: a) Give a recursive definition of the function m(s),which equals th...
 5.3.34E: Find the reversal of the following bit strings.a) 0101_____________...
 5.3.35E: Give a recursive definition of the reversal of a string. [Hint: Fir...
 5.3.36E: Use structural induction to prove that (w1w2)R = w2Rw 1R
 5.3.37E: Give a recursive definition of wi, where w is a string and i is a n...
 5.3.38E: Give a recursive definition of the set of bit strings that are pali...
 5.3.39E: When does a string belong to the set 4 of bit strings defined recur...
 5.3.40E: Recursively define the set of bit strings that have more zeros than...
 5.3.41E: Use Exercise 37 and mathematical induction to show that l(wi) = i l...
 5.3.42E: Show that (wR)i = (wi)R whenever w is a string and i is a nonnegati...
 5.3.43E: Use structural induction to show that n(T) ? 2h(T) + 1, where T is ...
 5.3.44E: The set of leaves and the set of internal vertices of a full binary...
 5.3.45E: Use generalized induction as was done in Example 13 to show that if...
 5.3.46E: Use generalized induction as was done in Example 13 to show that if...
 5.3.47E: A partition of a positive integer n is a way to write n as a sum of...
 5.3.48E: Consideran inductive definition of a version of Ackermann's functio...
 5.3.49E: Consideran inductive definition of a version of Ackermann's functio...
 5.3.50E: Consideran inductive definition of a version of Ackermann's functio...
 5.3.51E: Consideran inductive definition of a version of Ackermann's functio...
 5.3.52E: Consideran inductive definition of a version of Ackermann's functio...
 5.3.53E: Consideran inductive definition of a version of Ackermann's functio...
 5.3.54E: Consideran inductive definition of a version of Ackermann's functio...
 5.3.55E: Consideran inductive definition of a version of Ackermann's functio...
 5.3.56E: Use mathematical induction to prove that a function F defined by sp...
 5.3.57E: Use strong induction to prove that a function F defined by specifyi...
 5.3.58E: how that each of these proposed recursive definitions of a function...
 5.3.59E: Show that each of these proposed recursive definitions of a functio...
 5.3.60E: deal with iterations of the logarithm function. Let log n denote th...
 5.3.61E: deal with iterations of the logarithm function. Let log n denote th...
 5.3.62E: deal with iterations of the logarithm function. Let log n denote th...
 5.3.63E: deal with values of iterated functions. Suppose that f(n) is a func...
 5.3.64E: deal with values of iterated functions. Suppose that f(n) is a func...
 5.3.65E: deal with values of iterated functions. Suppose that f(n) is a func...
Solutions for Chapter 5.3: Discrete Mathematics and Its Applications 7th Edition
Full solutions for Discrete Mathematics and Its Applications  7th Edition
ISBN: 9780073383095
Solutions for Chapter 5.3
Get Full SolutionsThis textbook survival guide was created for the textbook: Discrete Mathematics and Its Applications, edition: 7. Chapter 5.3 includes 63 full stepbystep solutions. Since 63 problems in chapter 5.3 have been answered, more than 171615 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.

Adjacency matrix of a graph.
Square matrix with aij = 1 when there is an edge from node i to node j; otherwise aij = O. A = AT when edges go both ways (undirected). Adjacency matrix of a graph. Square matrix with aij = 1 when there is an edge from node i to node j; otherwise aij = O. A = AT when edges go both ways (undirected).

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

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

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.

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.

Identity matrix I (or In).
Diagonal entries = 1, offdiagonal entries = 0.

Incidence matrix of a directed graph.
The m by n edgenode incidence matrix has a row for each edge (node i to node j), with entries 1 and 1 in columns i and j .

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

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 matrix.
If N NT = NT N, then N has orthonormal (complex) eigenvectors.

Pascal matrix
Ps = pascal(n) = the symmetric matrix with binomial entries (i1~;2). Ps = PL Pu all contain Pascal's triangle with det = 1 (see Pascal in the index).

Plane (or hyperplane) in Rn.
Vectors x with aT x = O. Plane is perpendicular to a =1= 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.

Random matrix rand(n) or randn(n).
MATLAB creates a matrix with random entries, uniformly distributed on [0 1] for rand and standard normal distribution for randn.

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!

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

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

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

Unitary matrix UH = U T = UI.
Orthonormal columns (complex analog of Q).