 3.7.1: Prove that there is no largest negative rational number.
 3.7.2: Prove that 100 cannot be expressed as the sum of three odd integers.
 3.7.3: Prove that 101 cannot be expressed as the sum of two even integers.
 3.7.4: Prove that no odd integer can be expressed as the sum of three even...
 3.7.5: Prove that if a is a rational number and b is an irrational number,...
 3.7.6: (a) Disprove: The product of a rational number and an irrational nu...
 3.7.7: Prove that there is no smallest positive irrational number.
 3.7.8: Use a proof by contradiction to prove that if n is an even integer,...
 3.7.9: Use a proof by contradiction to prove the following: Let n be an in...
 3.7.10: Prove that if a and b are positive real numbers, then a + b 6= a + b.
 3.7.11: Suppose that you are given the fact: Let n be an integer. Then n2 =...
 3.7.12: Prove that 2 + 3 is an irrational number.
 3.7.13: Prove that 6 is an irrational number. [Hint: Use the fact that if m...
 3.7.14: Let a, b, c R. Prove that if a + b, a + c and b + c are all rationa...
 3.7.15: Prove that there do not exist three distinct positive real numbers ...
Solutions for Chapter 3.7: Proof by Contradiction
Full solutions for Discrete Mathematics  1st Edition
ISBN: 9781577667308
Solutions for Chapter 3.7: Proof by Contradiction
Get Full SolutionsSince 15 problems in chapter 3.7: Proof by Contradiction have been answered, more than 13671 students have viewed full stepbystep solutions from this chapter. 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. This expansive textbook survival guide covers the following chapters and their solutions. Chapter 3.7: Proof by Contradiction includes 15 full stepbystep solutions.

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

Block matrix.
A matrix can be partitioned into matrix blocks, by cuts between rows and/or between columns. Block multiplication ofAB is allowed if the block shapes permit.

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

Echelon matrix U.
The first nonzero entry (the pivot) in each row comes in a later column than the pivot in the previous row. All zero rows come last.

Ellipse (or ellipsoid) x T Ax = 1.
A must be positive definite; the axes of the ellipse are eigenvectors of A, with lengths 1/.JI. (For IIx II = 1 the vectors y = Ax lie on the ellipse IIA1 yll2 = Y T(AAT)1 Y = 1 displayed by eigshow; axis lengths ad

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

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.

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.

Hankel matrix H.
Constant along each antidiagonal; hij depends on i + j.

Identity matrix I (or In).
Diagonal entries = 1, offdiagonal entries = 0.

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

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.

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.

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

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

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

Simplex method for linear programming.
The minimum cost vector x * is found by moving from comer to lower cost comer along the edges of the feasible set (where the constraints Ax = b and x > 0 are satisfied). Minimum cost at a comer!

Special solutions to As = O.
One free variable is Si = 1, other free variables = o.