 1.7.1.7.1: Prove that n 2 + I ::: 2 n when n is a positive integer with 1 ::::...
 1.7.1.7.2: Prove that there are no positive perfect cubes less 1 000 that are ...
 1.7.1.7.3: Prove that if x and y are real numbers, then max(x , y) + min(x, y)...
 1.7.1.7.4: Use a proof by cases to show that min(a , min(b, c = min(min(a , b)...
 1.7.1.7.5: Prove the triangle inequality, which states that if x and y are rea...
 1.7.1.7.6: Prove that there is a positive integer that equals the sum of the p...
 1.7.1.7.7: Prove that there are 1 00 consecutive positive integers that are no...
 1.7.1.7.8: Prove that either 2 1 0500 + 1 5 or 2 1 0500 + 16 is not a perfect ...
 1.7.1.7.9: Prove that there exists a pair of consecutive integers such that on...
 1.7.1.7.10: Show that the product of two of the numbers 65 1000  8 2001 + 3 1 ...
 1.7.1.7.11: Prove or disprove that there is a rational number x and an irration...
 1.7.1.7.12: Prove or disprove that if a and b are rational numbers, then a b is...
 1.7.1.7.13: Show that each of these statements can be used to express the fact ...
 1.7.1.7.14: Show that if a, b, and c are real numbers and a =I 0, then there is...
 1.7.1.7.15: Suppose that a and b are odd integers with a =I b. Show there is a ...
 1.7.1.7.16: Show that if r is an irrational number, there is a unique integer n...
 1.7.1.7.17: Show that if n is an odd integer, then there is a unique integer k ...
 1.7.1.7.18: Prove that given a real number x there exist unique numbers n and E...
 1.7.1.7.19: Prove that given a real number x there exist unique numbers n and E...
 1.7.1.7.20: Use forward reasoning to show that if x is a nonzero real number, t...
 1.7.1.7.21: The harmonic mean of two real numbers x and y equals 2xy /(x + y). ...
 1.7.1.7.22: The quadratic mean of two real numbers x and y equals J(x2 + y2)/2....
 1.7.1.7.23: Write the numbers 1 , 2, ... , 2n on a blackboard, where n is an od...
 1.7.1.7.24: Suppose that five ones and four zeros are arranged around a circle....
 1.7.1.7.25: Formulate a conjecture about the decimal digits that appear as the ...
 1.7.1.7.26: Formulate a conjecture about the final two decimal digits of the sq...
 1.7.1.7.27: Prove that there is no positive integer n such that n2 + n3 = too.
 1.7.1.7.28: Prove that there are no solutions in integers x and y to the equati...
 1.7.1.7.29: Prove that there are no solutions in positive integers x and y to t...
 1.7.1.7.30: Prove that there are infinitely many solutions in positive integers...
 1.7.1.7.31: Adapt the proof in Example 4 in Section 1 .6 to prove that if n = a...
 1.7.1.7.32: Prove that is irrational.
 1.7.1.7.33: Prove that between every two rational numbers there is an irrationa...
 1.7.1.7.34: Prove that between every rational number and every irrational numbe...
 1.7.1.7.35: Let S = xlYI + X2 Y2 + ... + XnYn, where XI , X2 , ... , Xn and YI ...
 1.7.1.7.36: Prove or disprove that if you have an 8gallon jug of water and two...
 1.7.1.7.37: Verify the 3x + 1 conjecture for these integers. a) 6 b) 7 c) 17 d) 21
 1.7.1.7.38: Verify the 3x + 1 conjecture for these integers. a) 16 b) 11 c) 35 ...
 1.7.1.7.39: Prove or disprove that you can use dominoes to tile the standard ch...
 1.7.1.7.40: Prove or disprove that you can use dominoes to tile a standard chec...
 1.7.1.7.41: Prove that you can use dominoes to tile a rectangular checkerboard ...
 1.7.1.7.42: Prove or disprove that you can use dominoes to tile a 5 x 5 checker...
 1.7.1.7.43: Use a proof by exhaustion to show that a tiling using dominoes of a...
 1.7.1.7.44: Prove that when a white square and a black square are removed from ...
 1.7.1.7.45: Show that by removing two white squares and two black squares from ...
 1.7.1.7.46: Find all squares, if they exist, on an 8 x 8 checkerboard so that t...
 1.7.1.7.47: a) Draw each of the five different tetrominoes, where a tetromino i...
 1.7.1.7.48: Prove or disprove that you can tile a l O x 10 checkerboard using s...
Solutions for Chapter 1.7: The Foundations: Logic and Proofs
Full solutions for Discrete Mathematics and Its Applications  6th Edition
ISBN: 9780073229720
Solutions for Chapter 1.7: The Foundations: Logic and Proofs
Get Full SolutionsDiscrete Mathematics and Its Applications was written by and is associated to the ISBN: 9780073229720. Chapter 1.7: The Foundations: Logic and Proofs includes 48 full stepbystep solutions. This textbook survival guide was created for the textbook: Discrete Mathematics and Its Applications, edition: 6. This expansive textbook survival guide covers the following chapters and their solutions. Since 48 problems in chapter 1.7: The Foundations: Logic and Proofs have been answered, more than 35604 students have viewed full stepbystep solutions from this chapter.

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

Characteristic equation det(A  AI) = O.
The n roots are the eigenvalues of A.

Cholesky factorization
A = CTC = (L.J]))(L.J]))T for positive definite A.

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.

Cross product u xv in R3:
Vector perpendicular to u and v, length Ilullllvlll sin el = area of parallelogram, u x v = "determinant" of [i j k; UI U2 U3; VI V2 V3].

Fast Fourier Transform (FFT).
A factorization of the Fourier matrix Fn into e = log2 n matrices Si times a permutation. Each Si needs only nl2 multiplications, so Fnx and Fn1c can be computed with ne/2 multiplications. Revolutionary.

Graph G.
Set of n nodes connected pairwise by m edges. A complete graph has all n(n  1)/2 edges between nodes. A tree has only n  1 edges and no closed loops.

Indefinite matrix.
A symmetric matrix with eigenvalues of both signs (+ and  ).

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

Linearly dependent VI, ... , Vn.
A combination other than all Ci = 0 gives L Ci Vi = O.

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

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

Saddle point of I(x}, ... ,xn ).
A point where the first derivatives of I are zero and the second derivative matrix (a2 II aXi ax j = Hessian matrix) is indefinite.

Similar matrices A and B.
Every B = MI AM has the same eigenvalues as A.

Skewsymmetric matrix K.
The transpose is K, since Kij = Kji. Eigenvalues are pure imaginary, eigenvectors are orthogonal, eKt is an orthogonal matrix.

Standard basis for Rn.
Columns of n by n identity matrix (written i ,j ,k in R3).

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

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

Vector space V.
Set of vectors such that all combinations cv + d w remain within V. Eight required rules are given in Section 3.1 for scalars c, d and vectors v, w.