 3.1.1: For Exercises 112, write the first five values in the sequence.
 3.1.2: For Exercises 112, write the first five values in the sequence.
 3.1.3: For Exercises 112, write the first five values in the sequence.
 3.1.4: For Exercises 112, write the first five values in the sequence.
 3.1.5: For Exercises 112, write the first five values in the sequence.
 3.1.6: For Exercises 112, write the first five values in the sequence.
 3.1.7: For Exercises 112, write the first five values in the sequence.
 3.1.8: For Exercises 112, write the first five values in the sequence.
 3.1.9: For Exercises 112, write the first five values in the sequence.
 3.1.10: For Exercises 112, write the first five values in the sequence.
 3.1.11: For Exercises 112, write the first five values in the sequence.
 3.1.12: For Exercises 112, write the first five values in the sequence.
 3.1.13: In Exercises 1318, prove the given property of the Fibonacci number...
 3.1.14: In Exercises 1318, prove the given property of the Fibonacci number...
 3.1.15: In Exercises 1318, prove the given property of the Fibonacci number...
 3.1.16: In Exercises 1318, prove the given property of the Fibonacci number...
 3.1.17: In Exercises 1318, prove the given property of the Fibonacci number...
 3.1.18: In Exercises 1318, prove the given property of the Fibonacci number...
 3.1.19: In Exercises 1922, prove the given property of the Fibonacci number...
 3.1.20: In Exercises 1922, prove the given property of the Fibonacci number...
 3.1.21: In Exercises 1922, prove the given property of the Fibonacci number...
 3.1.22: In Exercises 1922, prove the given property of the Fibonacci number...
 3.1.23: Exercise 17
 3.1.24: Exercise 18
 3.1.25: F(n) < 2n for n 1
 3.1.26: F(n) > a 3 2 b n1 for n 6
 3.1.27: Write a pseudocode recursive algorithm for a function to compute F(...
 3.1.28: Walk through your recursive algorithm from Exercise 27 to compute F...
 3.1.29: a. In the iterative Fibonacci algorithm, the condition B for loop c...
 3.1.30: a. Write the loop invariant Q for the iterative Fibonacci algorithm...
 3.1.31: The values p and q are defined as follows: p = 1 + "5 2 and q = 1 "...
 3.1.32: he Lucas sequence is defined by L(1) = 1 L(2) = 3 L(n) = L(n 1) + L...
 3.1.33: The sequence A(n), where A(n) = 1 + (the sum of the first n terms o...
 3.1.34: The sequence B(n), where B(n) = (n 1)2n2 + 1, n 1. The first four v...
 3.1.35: The sequence C(n), where C(n) is the number of ways in which n coin...
 3.1.36: The sequence D(n), where D(n) describes the number of ways to paint...
 3.1.37: a. The original problem posed by Fibonacci concerned pairs of rabbi...
 3.1.38: a. The sequence of Catalan numbers is defined recursively by C(0) =...
 3.1.39: A sequence is recursively defined by S(1) = 2 S(2) = 2 S(3) = 6 S(n...
 3.1.40: A sequence is recursively defined by T(5) = 6 T(6) = 10 T(n) = 2T(n...
 3.1.41: A sequence is recursively defined by S(0) = 1 S(1) = 1 S(n) = 2S(n ...
 3.1.42: A sequence is recursively defined by T(0) = 1 T(1) = 2 T(n) = 2T(n ...
 3.1.43: Write a recursive definition for a geometric progression with initi...
 3.1.44: Write a recursive definition for an arithmetic progression with ini...
 3.1.45: In an experiment, a certain colony of bacteria initially has a popu...
 3.1.46: An amount of $500 is invested in an account paying 1.2% interest co...
 3.1.47: A set T of numbers is defined recursively by 1. 2 belongs to T. 2. ...
 3.1.48: A set M of numbers is defined recursively by 1. 2 and 3 belong to M...
 3.1.49: A set S of strings of characters is defined recursively by 1. a and...
 3.1.50: A set W of strings of symbols is defined recursively by 1. a, b, an...
 3.1.51: A set S of integers is defined recursively by 1. 0 and 3 belong to ...
 3.1.52: A set T of strings is defined recursively by 1. pqq belongs to T. 2...
 3.1.53: Give a recursive definition for the set of all unary predicate wffs...
 3.1.54: Give a recursive definition for the set of all wellformed formulas...
 3.1.55: Give a recursive definition for the set of all odd integers.
 3.1.56: Give a recursive definition for the set of all strings of wellbala...
 3.1.57: Give a recursive definition for the set of all binary strings conta...
 3.1.58: Give a recursive definition for the set of all binary strings conta...
 3.1.59: Give a recursive definition for the set of all binary strings endin...
 3.1.60: Give a recursive definition for the set of all binary strings with ...
 3.1.61: Use BNF notation to define the set of positive integers
 3.1.62: Use BNF notation to define the set of decimal numbers, which consis...
 3.1.63: Give a recursive definition for x R , the reverse of the string x.
 3.1.64: Give a recursive definition for 0 x 0 , the length of the string x.
 3.1.65: Give a recursive definition for the factorial operation n! for n 1.
 3.1.66: Give a recursive definition for the addition of two nonnegative int...
 3.1.67: Give a recursive definition for the addition of two nonnegative int...
 3.1.68: a. Give a recursive definition for the conjunction of n statement l...
 3.1.69: Let A and B1, B2, , Bn be statement letters. Prove the finite exten...
 3.1.70: Let B1, B2, , Bn be statement letters. Prove the finite extension o...
 3.1.71: In Exercises 7176, write the body of a recursive function to comput...
 3.1.72: In Exercises 7176, write the body of a recursive function to comput...
 3.1.73: In Exercises 7176, write the body of a recursive function to comput...
 3.1.74: In Exercises 7176, write the body of a recursive function to comput...
 3.1.75: In Exercises 7176, write the body of a recursive function to comput...
 3.1.76: In Exercises 7176, write the body of a recursive function to comput...
 3.1.77: What value is returned by the following recursive function Mystery ...
 3.1.78: The following recursive function is initially invoked with an i val...
 3.1.79: Informally describe a recursive algorithm to reverse the entries in...
 3.1.80: Informally describe a recursive algorithm to compute the sum of the...
 3.1.81: Informally describe a recursive algorithm to compute the greatest c...
 3.1.82: The famous Towers of Hanoi puzzle involves 3 pegs with n disks of v...
 3.1.83: Simulate the execution of algorithm SelectionSort on the following ...
 3.1.84: Simulate the execution of algorithm SelectionSort on the following ...
 3.1.85: The binary search algorithm is used with the following list; x has ...
 3.1.86: The binary search algorithm is used with the following list; x has ...
 3.1.87: Do a proof of correctness for the iterative function given in this ...
 3.1.88: The Online Encyclopedia of Integer Sequences (OEIS) was originated ...
Solutions for Chapter 3.1: Recursive Definitions
Full solutions for Mathematical Structures for Computer Science  7th Edition
ISBN: 9781429215107
Solutions for Chapter 3.1: Recursive Definitions
Get Full SolutionsThis expansive textbook survival guide covers the following chapters and their solutions. This textbook survival guide was created for the textbook: Mathematical Structures for Computer Science, edition: 7. Chapter 3.1: Recursive Definitions includes 88 full stepbystep solutions. Mathematical Structures for Computer Science was written by and is associated to the ISBN: 9781429215107. Since 88 problems in chapter 3.1: Recursive Definitions have been answered, more than 19097 students have viewed full stepbystep solutions from this chapter.

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

Basis for V.
Independent vectors VI, ... , v d whose linear combinations give each vector in V as v = CIVI + ... + CdVd. V has many bases, each basis gives unique c's. A vector space has many bases!

Big formula for n by n determinants.
Det(A) is a sum of n! terms. For each term: Multiply one entry from each row and column of A: rows in order 1, ... , nand column order given by a permutation P. Each of the n! P 's has a + or  sign.

Complete solution x = x p + Xn to Ax = b.
(Particular x p) + (x n in nullspace).

Condition number
cond(A) = c(A) = IIAIlIIAIII = amaxlamin. In Ax = b, the relative change Ilox III Ilx II is less than cond(A) times the relative change Ilob III lib II· Condition numbers measure the sensitivity of the output to change in the input.

Eigenvalue A and eigenvector x.
Ax = AX with x#O so det(A  AI) = o.

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.

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

Free columns of A.
Columns without pivots; these are combinations of earlier columns.

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.

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

Linear combination cv + d w or L C jV j.
Vector addition and scalar multiplication.

Pascal matrix
Ps = pascal(n) = the symmetric matrix with binomial entries (i1~;2). Ps = PL Pu all contain Pascal's triangle with det = 1 (see Pascal in the index).

Pivot columns of A.
Columns that contain pivots after row reduction. These are not combinations of earlier columns. The pivot columns are a basis for the column space.

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

Schwarz inequality
Iv·wl < IIvll IIwll.Then IvTAwl2 < (vT Av)(wT Aw) for pos def A.

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

Sum V + W of subs paces.
Space of all (v in V) + (w in W). Direct sum: V n W = to}.

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

Vector v in Rn.
Sequence of n real numbers v = (VI, ... , Vn) = point in Rn.