 3.1: Let S be the set of positive even integers and for an even integer ...
 3.2: Let S = {0, 1, 4, 5} and let P(n) : n2 5n+6 2 is odd. be an open se...
 3.3: Let m and n be two integers. Prove that mn+m is odd if and only if ...
 3.4: Let n be an integer. Prove that if 11n 9 is even, then n is odd.
 3.5: Let x be a real number. Prove that if (x2 1)2 = 0, then x4 x2 = 0.
 3.6: Disprove: If r and s are irrational numbers, then rs is irrational.
 3.7: Prove that if r and s are rational numbers and s 6= 0, then r/s is ...
 3.8: Let x and y be real numbers. Prove that if (x 3)2 + (y 4)2 = 0, the...
 3.9: Let n be an integer. Prove that 5n + 1 is even if and only if n is ...
 3.10: Let a and b be integers. Prove that if a and b are of the same pari...
 3.11: Disprove the following by providing a counterexample in each case. ...
 3.12: Prove that there exist two integers a and b such that a + b > ab.
 3.13: Prove that if n is an even integer, then 5n 7 is an odd integer usi...
 3.14: Prove for every integer n that if 3n + 5 is odd, then n is an even ...
 3.15: Give a proof of Let n Z. Then n is odd if and only if 7 n is even. ...
 3.16: Prove that if r is a rational number and s is an irrational number,...
 3.17: Prove that 10 cannot be expressed as the sum of an odd integer and ...
 3.18: Prove that 100 cannot be written as the sum of three integers, an e...
 3.19: Prove that there exists no positive integer x such that x < x2 < 2x.
 3.20: Let m and n be integers. Prove that if m+ n 10, then m 5 or n 5.
 3.21: Let m and n be integers. Prove that if mn = 1, then either m = n = ...
 3.22: Let m and n be integers. Prove that if m2 = n2, then either m = n o...
 3.23: For a real number x, let x be the absolute value of x, that is, ...
 3.24: For n Z, consider the following: P(n): n2 < 4. Q(n): n3 = n. State ...
 3.25: Prove that if a is an odd integer and b is an even integer, then 3a...
 3.26: Let x R. Prove that if x3 = x, then x2 < 2.
 3.27: For two real numbers a and b, min(a, b) denotes the smaller of a an...
 3.28: Let a and b be real numbers. Prove that min(a, b) + max(a, b) = a +...
 3.29: Let a and b be real numbers. Prove that min(a, b) a+b 2 max(a, b) (...
 3.30: Let x R. Prove that if x 3 < 2, then 1 < x < 5.
 3.31: Prove that there exist a rational number a and an irrational number...
 3.32: Prove that there exist a rational number a and an irrational number...
 3.33: Prove that 3 2 is irrational.
 3.34: Prove that 3 3 is irrational. (Use the fact that if n is an integer...
 3.35: In the proof of Result 3.38, we began by considering 2 2 . Give a n...
 3.36: Prove the following De Morgans law for sets: For every two sets A a...
 3.37: It is known that 3 and 5 are irrational. Prove that 3 + 5 is irrati...
 3.38: Prove for every integer n that there exist two integers a and b of ...
 3.39: Let a and b be two integers of opposite parity and let n Z. Prove t...
Solutions for Chapter 3: Methods of Proof
Full solutions for Discrete Mathematics  1st Edition
ISBN: 9781577667308
Solutions for Chapter 3: Methods of Proof
Get Full SolutionsThis expansive textbook survival guide covers the following chapters and their solutions. This textbook survival guide was created for the textbook: Discrete Mathematics, edition: 1. Discrete Mathematics was written by and is associated to the ISBN: 9781577667308. Since 39 problems in chapter 3: Methods of Proof have been answered, more than 12861 students have viewed full stepbystep solutions from this chapter. Chapter 3: Methods of Proof includes 39 full stepbystep 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).

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

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

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

Diagonal matrix D.
dij = 0 if i # j. Blockdiagonal: zero outside square blocks Du.

Distributive Law
A(B + C) = AB + AC. Add then multiply, or mUltiply then add.

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

Independent vectors VI, .. " vk.
No combination cl VI + ... + qVk = zero vector unless all ci = O. If the v's are the columns of A, the only solution to Ax = 0 is x = o.

Kirchhoff's Laws.
Current Law: net current (in minus out) is zero at each node. Voltage Law: Potential differences (voltage drops) add to zero around any closed loop.

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.

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.

Linear transformation T.
Each vector V in the input space transforms to T (v) in the output space, and linearity requires T(cv + dw) = c T(v) + d T(w). Examples: Matrix multiplication A v, differentiation and integration in function space.

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.

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

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

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

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

Transpose matrix AT.
Entries AL = Ajj. AT is n by In, AT A is square, symmetric, positive semidefinite. The transposes of AB and AI are BT AT and (AT)I.

Tridiagonal matrix T: tij = 0 if Ii  j I > 1.
T 1 has rank 1 above and below diagonal.

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.