 2.2.1: For all positive integers, let P(n) be the equation 2 + 6 + 10 + c+...
 2.2.2: For all positive integers, let P(n) be the equation 2 + 4 + 6 + c+ ...
 2.2.3: In Exercises 326, use mathematical induction to prove that the stat...
 2.2.4: In Exercises 326, use mathematical induction to prove that the stat...
 2.2.5: In Exercises 326, use mathematical induction to prove that the stat...
 2.2.6: In Exercises 326, use mathematical induction to prove that the stat...
 2.2.7: In Exercises 326, use mathematical induction to prove that the stat...
 2.2.8: In Exercises 326, use mathematical induction to prove that the stat...
 2.2.9: In Exercises 326, use mathematical induction to prove that the stat...
 2.2.10: In Exercises 326, use mathematical induction to prove that the stat...
 2.2.11: In Exercises 326, use mathematical induction to prove that the stat...
 2.2.12: In Exercises 326, use mathematical induction to prove that the stat...
 2.2.13: In Exercises 326, use mathematical induction to prove that the stat...
 2.2.14: In Exercises 326, use mathematical induction to prove that the stat...
 2.2.15: In Exercises 326, use mathematical induction to prove that the stat...
 2.2.16: In Exercises 326, use mathematical induction to prove that the stat...
 2.2.17: In Exercises 326, use mathematical induction to prove that the stat...
 2.2.18: In Exercises 326, use mathematical induction to prove that the stat...
 2.2.19: In Exercises 326, use mathematical induction to prove that the stat...
 2.2.20: In Exercises 326, use mathematical induction to prove that the stat...
 2.2.21: In Exercises 326, use mathematical induction to prove that the stat...
 2.2.22: In Exercises 326, use mathematical induction to prove that the stat...
 2.2.23: In Exercises 326, use mathematical induction to prove that the stat...
 2.2.24: In Exercises 326, use mathematical induction to prove that the stat...
 2.2.25: In Exercises 326, use mathematical induction to prove that the stat...
 2.2.26: In Exercises 326, use mathematical induction to prove that the stat...
 2.2.27: A geometric progression (geometric sequence) is a sequence of terms...
 2.2.28: An arithmetic progression (arithmetic sequence) is a sequence of te...
 2.2.29: Using Exercises 27 and 28, find an expression for the value of the ...
 2.2.30: Prove that (2) 0 + (2) 1 + (2) 2 + c+ (2) n = 1 2n+1
 2.2.31: Prove that n2 > n + 1 for n 2
 2.2.32: Prove that n2 2n + 3 for n 3.
 2.2.33: Prove that n2 > 5n + 10 for n > 6.
 2.2.34: Prove that 2n > n2 for n 5.
 2.2.35: Prove that n! > n2 for n 4.
 2.2.36: Prove that n! > n3 for n 6
 2.2.37: Prove that n! > 2n for n 4.
 2.2.38: Prove that n! > 3n for n 7
 2.2.39: Prove that n! 2n1 for n 1.
 2.2.40: Prove that n! < nn for n 2.
 2.2.41: Prove that a a b b n+1 < a a b b n for n 1 and 0 < a < b.
 2.2.42: Prove that 1 + 2 + c+ n < n2 for n > 1.
 2.2.43: Prove that 1 + 1 4 + 1 9 + c+ 1 n2 < 2 1 n for n 2
 2.2.44: a. Try to use induction to prove that 1 + 1 2 + 1 4 + c+ 1 2n < 2 f...
 2.2.45: Prove that 1 + 1 2 + 1 3 + c+ 1 2n 1 + n 2 for n 1 (Note that the d...
 2.2.46: 23n 1 is divisible by 7
 2.2.47: 32n + 7 is divisible by 8.
 2.2.48: 7n 2n is divisible by 5.
 2.2.49: 13n 6n is divisible by 7
 2.2.50: 13n 6n is divisible by 7.
 2.2.51: 2n + (1) n+1 is divisible by 3.
 2.2.52: 25n+1 + 5n+2 is divisible by 27.
 2.2.53: 34n+2 + 52n+1 is divisible by 14
 2.2.54: 72n + 16n 1 is divisible by 64
 2.2.55: 10n + 3 # 4n+2 + 5 is divisible by 9
 2.2.56: n3 n is divisible by 3.
 2.2.57: n3 + 2n is divisible by 3.
 2.2.58: xn 1 is divisible by x 1 for x 1.
 2.2.59: Prove DeMoivres Theorem: (cos + i sin ) n = cos n + i sin n for all...
 2.2.60: Prove that sin + sin 3 + c+ sin(2n 1) = sin2 n sin for all n 1 and ...
 2.2.61: Use induction to prove that the product of any three consecutive po...
 2.2.62: Suppose that exponentiation is defined by the equation xj # x = xj+...
 2.2.63: According to Example 20, it is possible to use angle irons to tile ...
 2.2.64: Example 20 does not cover the case of checkerboards that are not si...
 2.2.65: Prove that it is possible to use angle irons to tile a 5 5 checkerb...
 2.2.66: Find a configuration for a 5 5 checkerboard with one square removed...
 2.2.67: Consider n infinitely long straight lines, none of which are parall...
 2.2.68: A string of 0s and 1s is to be processed and converted to an evenp...
 2.2.69: What is wrong with the following proof by mathematical induction? W...
 2.2.70: What is wrong with the following proof by mathematical induction? W...
 2.2.71: An obscure tribe has only three words in its language, moon, noon, ...
 2.2.72: A simple closed polygon consists of n points in the plane joined in...
 2.2.73: The Computer Science club is sponsoring a jigsaw puzzle contest. Ji...
 2.2.74: OurWay Pizza makes only two kinds of pizza, pepperoni and vegetaria...
 2.2.75: Consider propositional wffs that contain only the connectives `, ~,...
 2.2.76: In any group of k people, k 1, each person is to shake hands with e...
 2.2.77: Prove that any amount of postage greater than or equal to 2 cents c...
 2.2.78: Prove that any amount of postage greater than or equal to 12 cents ...
 2.2.79: Prove that any amount of postage greater than or equal to 14 cents ...
 2.2.80: Prove that any amount of postage greater than or equal to 42 cents ...
 2.2.81: Prove that any amount of postage greater than or equal to 64 cents ...
 2.2.82: Your bank ATM delivers cash using only $20 and $50 bills. Prove tha...
 2.2.83: Show that 3 n 0 2x dx n m=1 2m 3 n+1 1 2x dx (see Exercise 2)
 2.2.84: Show that 3 n 0 x2 dx n m=1 m2 3 n+1 1 x2 dx (see Exercise 7).
Solutions for Chapter 2.2: Induction
Full solutions for Mathematical Structures for Computer Science  7th Edition
ISBN: 9781429215107
Solutions for Chapter 2.2: Induction
Get Full SolutionsMathematical Structures for Computer Science was written by and is associated to the ISBN: 9781429215107. Chapter 2.2: Induction includes 84 full stepbystep solutions. This textbook survival guide was created for the textbook: Mathematical Structures for Computer Science, edition: 7. This expansive textbook survival guide covers the following chapters and their solutions. Since 84 problems in chapter 2.2: Induction have been answered, more than 20096 students have viewed full stepbystep solutions from this chapter.

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

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.

Change of basis matrix M.
The old basis vectors v j are combinations L mij Wi of the new basis vectors. The coordinates of CI VI + ... + cnvn = dl wI + ... + dn Wn are related by d = M c. (For n = 2 set VI = mll WI +m21 W2, V2 = m12WI +m22w2.)

Circulant matrix C.
Constant diagonals wrap around as in cyclic shift S. Every circulant is Col + CIS + ... + Cn_lSn  l . Cx = convolution c * x. Eigenvectors in F.

Complex conjugate
z = a  ib for any complex number z = a + ib. Then zz = Iz12.

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

Dot product = Inner product x T y = XI Y 1 + ... + Xn Yn.
Complex dot product is x T Y . Perpendicular vectors have x T y = O. (AB)ij = (row i of A)T(column j of B).

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.

Exponential eAt = I + At + (At)2 12! + ...
has derivative AeAt; eAt u(O) solves u' = Au.

GaussJordan method.
Invert A by row operations on [A I] to reach [I AI].

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.

Iterative method.
A sequence of steps intended to approach the desired solution.

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.

Matrix multiplication AB.
The i, j entry of AB is (row i of A)·(column j of B) = L aikbkj. By columns: Column j of AB = A times column j of B. By rows: row i of A multiplies B. Columns times rows: AB = sum of (column k)(row k). All these equivalent definitions come from the rule that A B times x equals A times B x .

Polar decomposition A = Q H.
Orthogonal Q times positive (semi)definite H.

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.

Rotation matrix
R = [~ CS ] rotates the plane by () and R 1 = RT rotates back by (). Eigenvalues are eiO and eiO , eigenvectors are (1, ±i). c, s = cos (), sin ().

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.

Spanning set.
Combinations of VI, ... ,Vm fill the space. The columns of A span C (A)!