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

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.

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

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

Complete solution x = x p + Xn to Ax = b.
(Particular x p) + (x n in nullspace).

Diagonalizable matrix A.
Must have n independent eigenvectors (in the columns of S; automatic with n different eigenvalues). Then SI AS = A = eigenvalue matrix.

Elimination.
A sequence of row operations that reduces A to an upper triangular U or to the reduced form R = rref(A). Then A = LU with multipliers eO in L, or P A = L U with row exchanges in P, or E A = R with an invertible E.

Factorization
A = L U. If elimination takes A to U without row exchanges, then the lower triangular L with multipliers eij (and eii = 1) brings U back to A.

Fibonacci numbers
0,1,1,2,3,5, ... satisfy Fn = Fnl + Fn 2 = (A7 A~)I()q A2). Growth rate Al = (1 + .J5) 12 is the largest eigenvalue of the Fibonacci matrix [ } A].

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.

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.

Markov matrix M.
All mij > 0 and each column sum is 1. Largest eigenvalue A = 1. If mij > 0, the columns of Mk approach the steady state eigenvector M s = s > O.

Normal matrix.
If N NT = NT N, then N has orthonormal (complex) eigenvectors.

Projection p = a(aTblaTa) onto the line through a.
P = aaT laTa has rank l.

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.

Rank one matrix A = uvT f=. O.
Column and row spaces = lines cu and cv.

Schur complement S, D  C A } B.
Appears in block elimination on [~ g ].

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

Solvable system Ax = b.
The right side b is in the column space of A.

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