 4.1: Prove that 1 + 3 + 6 + + n(n+1)2 = n(n+1)(n+2)6 for every positive ...
 4.2: Find a formula for 1+4+7+ +(3n2) for positive integers n, and then ...
 4.3: Prove that 12 + 32 + + (2n 1)2 = n(2n1)(2n+1)3 for every positive i...
 4.4: Prove that 1 2 3 + 2 3 4 + + n (n + 1) (n + 2) = n(n+1)(n+2)(n+3)4 ...
 4.5: Prove that 1(1!) + 2(2!) + + n(n!) = (n + 1)! 1 for every positive ...
 4.6: Prove that 2n > n2 + n + 1 for every integer n 5.
 4.7: Prove in two ways that 2n+1 < 1 + (n + 1)2n for every positive inte...
 4.8: Prove that 3n > n2 for every positive integer n.
 4.9: Prove that 2n > n3 for every integer n 10.
 4.10: Prove that 4n > n3 for every positive integer n.
 4.11: Prove by induction that nn > n! for every integer n 2.
 4.12: Prove that 1 + 14 + 19 + + 1n2 2 1n for every positive integer n.
 4.13: Prove that 13p1 + 13p2 + + 13pn > (n + 1)2/3 for every integer n 4.
 4.14: Use induction to prove that n2 + n is even for every nonnegative in...
 4.15: Use induction to prove that for every real number x > 1 and every p...
 4.16: Let a be a real number. Use induction to prove that Pni=0(a+i) = 12...
 4.17: Let a and b be two real numbers. Use induction to prove that Pni=0(...
 4.18: A sequence {an} is defined recursively by a1 = 5, a2 = 7 and an = 3...
 4.19: A sequence a0, a1, a2, . . . of integers is defined recursively by ...
 4.20: A sequence {an} is defined recursively by a1 = 2, a2 = 4 and an = a...
 4.21: A sequence {an} is defined recursively by a1 = 2, a2 = 6 and an = 2...
 4.22: A sequence {an} is defined recursively by a1 = 2, a2 = 2 and an = a...
 4.23: Let = 1 +5_ /2. Prove that the nth Fibonacci number Fn > n2 for eve...
 4.24: (a) Show that there do not exist nonnegative integers x and y such ...
 4.25: Let A be a nonempty set of real numbers. A number m A is a least el...
 4.26: The WellOrdering Principle states: The set N of positive integers ...
 4.27: Let S = {1, 2, . . . ,m}, where m N. The following is called the Pr...
 4.28: Prove for every positive integer n and the Fibonacci numbers F1, F2...
 4.29: Prove for every positive integer n thats2 +r2 +q2 + +2 = 2 cos2n+1 ...
Solutions for Chapter 4: MATHEMATICAL INDUCTION
Full solutions for Discrete Mathematics  1st Edition
ISBN: 9781577667308
Solutions for Chapter 4: MATHEMATICAL INDUCTION
Get Full SolutionsChapter 4: MATHEMATICAL INDUCTION includes 29 full stepbystep solutions. Discrete Mathematics was written by and is associated to the ISBN: 9781577667308. This textbook survival guide was created for the textbook: Discrete Mathematics, edition: 1. Since 29 problems in chapter 4: MATHEMATICAL INDUCTION have been answered, more than 10850 students have viewed full stepbystep solutions from this chapter. 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.

Associative Law (AB)C = A(BC).
Parentheses can be removed to leave ABC.

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

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

Companion matrix.
Put CI, ... ,Cn in row n and put n  1 ones just above the main diagonal. Then det(A  AI) = ±(CI + c2A + C3A 2 + .•. + cnA nl  An).

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.

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

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.

Least squares solution X.
The vector x that minimizes the error lie 112 solves AT Ax = ATb. Then e = b  Ax is orthogonal to all columns of A.

Nilpotent matrix N.
Some power of N is the zero matrix, N k = o. The only eigenvalue is A = 0 (repeated n times). Examples: triangular matrices with zero diagonal.

Orthonormal vectors q 1 , ... , q n·
Dot products are q T q j = 0 if i =1= j and q T q i = 1. The matrix Q with these orthonormal columns has Q T Q = I. If m = n then Q T = Q 1 and q 1 ' ... , q n is an orthonormal basis for Rn : every v = L (v T q j )q j •

Pivot.
The diagonal entry (first nonzero) at the time when a row is used in elimination.

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

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.

Triangle inequality II u + v II < II u II + II v II.
For matrix norms II A + B II < II A II + II B II·

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

Volume of box.
The rows (or the columns) of A generate a box with volume I det(A) I.