 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 Patricia 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 5502 students have viewed full stepbystep solutions from this chapter. This expansive textbook survival guide covers the following chapters and their solutions.

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

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.

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

Elimination matrix = Elementary matrix Eij.
The identity matrix with an extra eij in the i, j entry (i # j). Then Eij A subtracts eij times row j of A from row i.

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.

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.

Hessenberg matrix H.
Triangular matrix with one extra nonzero adjacent diagonal.

Hilbert matrix hilb(n).
Entries HU = 1/(i + j 1) = Jd X i 1 xj1dx. Positive definite but extremely small Amin and large condition number: H is illconditioned.

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

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

Minimal polynomial of A.
The lowest degree polynomial with meA) = zero matrix. This is peA) = det(A  AI) if no eigenvalues are repeated; always meA) divides peA).

Multiplication Ax
= Xl (column 1) + ... + xn(column n) = combination of columns.

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.

Positive definite matrix A.
Symmetric matrix with positive eigenvalues and positive pivots. Definition: x T Ax > 0 unless x = O. Then A = LDLT with diag(D» O.

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

Reflection matrix (Householder) Q = I 2uuT.
Unit vector u is reflected to Qu = u. All x intheplanemirroruTx = o have Qx = x. Notice QT = Q1 = Q.

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·

Vandermonde matrix V.
V c = b gives coefficients of p(x) = Co + ... + Cn_IXn 1 with P(Xi) = bi. Vij = (Xi)jI and det V = product of (Xk  Xi) for k > i.

Wavelets Wjk(t).
Stretch and shift the time axis to create Wjk(t) = woo(2j t  k).