 7.2.7.2.1: Determine which ofthese are linear homogeneous recurrence relations...
 7.2.7.2.2: Determine which ofthese are linear homogeneous recurrence relations...
 7.2.7.2.3: Solve these recurrence relations together with the initial conditio...
 7.2.7.2.4: Solve these recurrence relations together with the initial conditio...
 7.2.7.2.5: How many different messages can be transmitted in n microseconds us...
 7.2.7.2.6: How many different messages can be transmitted in n microseconds us...
 7.2.7.2.7: In how many ways can a 2 x n rectangular checkerboard be tiled usin...
 7.2.7.2.8: A model for the number of lobsters caught per year is based on the ...
 7.2.7.2.9: A deposit of $ 1 00,000 is made to an investment fund at the beginn...
 7.2.7.2.10: Prove Theorem 2.
 7.2.7.2.11: The Lucas numbers satisfy the recurrence relation and the initial c...
 7.2.7.2.12: Find the solution to an = 2an1 + an2  2an3 for n = 3, 4, 5, ......
 7.2.7.2.13: Find the solution to an = 7an2 + 6an3 with ao = 9, al = 10, and a...
 7.2.7.2.14: Find the solution to an = 5an2  4an4 with ao = 3, al = 2, a2 = 6...
 7.2.7.2.15: Find the solution to an = 2an1 + 5an2  6an3 with ao = 7, al = ...
 7.2.7.2.16: Prove Theorem 3.
 7.2.7.2.17: Prove this identity relating the Fibonacci numbers and the binomial...
 7.2.7.2.18: Solve the recurrence relation an = 6an1  12an2 + 8an3 with ao =...
 7.2.7.2.19: Solve the recurrence relation an = 3an1  3an2  an3 with ao = ...
 7.2.7.2.20: Find the general form of the solutions of the recurrence relation a...
 7.2.7.2.21: What is the general form of the solutions ofa linear homogeneous re...
 7.2.7.2.22: What is the general form ofthe solutions of a linear homogeneous re...
 7.2.7.2.23: Consider the nonhomogeneous linear recurrence relation an = 3an1 +...
 7.2.7.2.24: Consider the nonhomogeneous linear recurrence relation an = 2an_1 +...
 7.2.7.2.25: a) Determine values of the constants A and B such that an = An + B ...
 7.2.7.2.26: What is the general form of the particular solution guaranteed to e...
 7.2.7.2.27: What is the general form ofthe particular solution guaranteed to ex...
 7.2.7.2.28: a) Find all solutions of the recurrence relation an = 2an_1 + 2n 2 ...
 7.2.7.2.29: a) Find all solutions of the recurrence relation an = 2an_1 + 3n . ...
 7.2.7.2.30: a) Find all solutions of the recurrence relation an = 5an_1  6an...
 7.2.7.2.31: Find all solutions ofthe recurrence relation an = 5an1  6an2 + 2...
 7.2.7.2.32: Find the solution of the recurrence relation an = 2an1 + 32n .
 7.2.7.2.33: Find all solutions of the recurrence relation an = 4an_1  4an2 + ...
 7.2.7.2.34: Find all solutions of the recurrence relation an = 7an_1  16an_2 +...
 7.2.7.2.35: Find the solution ofthe recurrence relation an = 4an1  3an2 + 2 ...
 7.2.7.2.36: Let an be the sum of the first n perfect squares, that is, an = I:Z...
 7.2.7.2.37: Let an be the sum of the first n triangular numbers, that is, an = ...
 7.2.7.2.38: a) Find the characteristic roots of the linear homogeneous recurren...
 7.2.7.2.39: a) Find the characteristic roots of the linear homogeneous recurren...
 7.2.7.2.40: Solve the simultaneous recurrence relations an = 3anJ + 2bnJ bn =...
 7.2.7.2.41: a) Use the formula found in Example 4 for in, the nth Fibonacci num...
 7.2.7.2.42: Show that if an = anl + an2, ao = s and al = t, where s and t are...
 7.2.7.2.43: Express the solution of the linear nonhomogenous recurrence relatio...
 7.2.7.2.44: (Linear algebra required) Let An be the n x n matrix with 2s on its...
 7.2.7.2.45: Suppose that each pair of a genetically engineered species of rabbi...
 7.2.7.2.46: Suppose that there are two goats on an island initially. The number...
 7.2.7.2.47: A new employee at an exciting new software company starts with a sa...
 7.2.7.2.48: a) Show that the recurrence relation f(n)an = g(n)anl + h(n), for ...
 7.2.7.2.49: Use Exercise 48 to solve the recurrence relation (n + 1) an = (n + ...
 7.2.7.2.50: It can be shown that the average number of comparisons made by the ...
 7.2.7.2.51: Prove Theorem 4
 7.2.7.2.52: Prove Theorem 6.
 7.2.7.2.53: Solve the recurrence relation T(n) = nT2 (nj2) with initial conditi...
Solutions for Chapter 7.2: Advanced Counting Techniques
Full solutions for Discrete Mathematics and Its Applications  6th Edition
ISBN: 9780073229720
Solutions for Chapter 7.2: Advanced Counting Techniques
Get Full SolutionsThis expansive textbook survival guide covers the following chapters and their solutions. Discrete Mathematics and Its Applications was written by and is associated to the ISBN: 9780073229720. Chapter 7.2: Advanced Counting Techniques includes 53 full stepbystep solutions. This textbook survival guide was created for the textbook: Discrete Mathematics and Its Applications, edition: 6. Since 53 problems in chapter 7.2: Advanced Counting Techniques have been answered, more than 39384 students have viewed full stepbystep solutions from this chapter.

Back substitution.
Upper triangular systems are solved in reverse order Xn to Xl.

Conjugate Gradient Method.
A sequence of steps (end of Chapter 9) to solve positive definite Ax = b by minimizing !x T Ax  x Tb over growing Krylov subspaces.

Dimension of vector space
dim(V) = number of vectors in any basis for V.

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

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

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.

Hessenberg matrix H.
Triangular matrix with one extra nonzero adjacent diagonal.

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 .

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.

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

Length II x II.
Square root of x T x (Pythagoras in n dimensions).

Lucas numbers
Ln = 2,J, 3, 4, ... satisfy Ln = L n l +Ln 2 = A1 +A~, with AI, A2 = (1 ± /5)/2 from the Fibonacci matrix U~]' Compare Lo = 2 with Fo = O.

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

Plane (or hyperplane) in Rn.
Vectors x with aT x = O. Plane is perpendicular to a =1= O.

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.

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

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.

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

Symmetric matrix A.
The transpose is AT = A, and aU = a ji. AI is also symmetric.