The set of leaves and the set of internal vertices of a

Problem 1E Find f(1), f (2), f (3), and f (4) if f (n) is defined recursively by f (0) = 1 and for n = 0, 1, 2, a) f (n + 1) =f (n) + 2. b) f (n + 1) =3 f (n). c) f (n+ 1) = 2 f (n). d) f (n+ 1) = f (n)2 + f (n)+ 1.

Problem 65E deal with values of iterated functions. Suppose that f(n) is a function from the set of real numbers, or positive real numbers, or some other set of real numbers, to the set of real numbers such that f(n) is monotonically increasing [that is, f(n)<f(m) when n<m) and f(n)<n for all n in the domain of f.] The function f(k)(n) is defined recursively by Furthermore, let c be a positive real number. The iterated function is the number of iterations of f required to reduce its argument to c or less, so is the smallest nonnegative integer k such that fk(n) ? c. Let f(n) = . Find a formula for f(k)(n). What is the value of when n is a positive integer?

Problem 2E Find f (l), f (2), f (3), f (4), and f (5) if f (n) is defined recursively by f (0) = 3 and for n = 0, 1, 2,… a) f(n + 1) = ?2 f(n). b) f (n +1) =3 f (n)+7. c) f (n + l)= f (n)2 - 2 f (n)- 2. d) f (n + 1) = 3f(n)/3.

Problem 3E Find f (2), f (3), f (4), and f (5) if f is defined recursively by f (0) = ?1, f (l) = 2, and for n = 1,2,… a) f (n+1) = f (n) + 3 f (n?1). b) f (n + 1) = f (n) 2 f (n ?1) c) f (n + 1) = f (n)2 – 4 f (n ?1)2. d) f ( n + 1) = f ( n ?1) f (n).

Problem 4E Find f (2), f (3), f (4), and f (5) if f is defined recursively by f (0) = f (l) = 1 and for n = 1.2,… a)f ( n + 1) = f (n) - f (n ? 1). b) f ( n + 1) = f (n) f (n ? 1). c) f ( n + 1) = f (n) 2 + f (n ? l)3. d) f ( n + 1) = f ( n) f ( n ? 1)

Problem 5E Determine whether each of these proposed definitions is a valid recursive definition of a function f from the set of nonnegative integers to the set of integers. If f is well defined, find a formula for f(n) when n is a nonnegative integer and prove that your formula is valid. a) f (0) = 0. f (n) = 2 f (n ? 2) for n ? 1 ________________ b) f (0) = 1, f( 1) = f (n ? 1) ? 1 for n ?1 ________________ c) f (0) = 2, f (1) = 3, f (n) = f(n ? 1) ? 1 for n ? 2 ________________ d) f (0)= 1. f (1) = 2, f (n) = 2 f (n ? 2) for n ?2 ________________ e) f (0) = 1, f(n) = 3 f (n ?1) if n is odd and n ?1 and f(n) = 9 f(n ? 2) if n is even and n ?2

Problem 7E Give a recursive definition of the sequence {an}, n=1, 2, 3…. if a) an = 6n. b) an = 2n + 1. c) an = 10n. d) an =5.

Problem 8E Give a recursive definition of the sequence {an}, n = 1,2, 3.…if a) an = 4n - 2. b) an = 1 + (?1)n. c)an = n(n + 1). d) an = n2.

Problem 9E Let F be the function such that F(n) is the sum of the first /i positive integers. Give a recursive definition of F(n).

Problem 10E Give a recursive definition of Sm (n), the sum of the integer m and the nonnegative integer n.

Problem 11E Give a recursive definition of Pm(n), the product of the integer m and the nonnegative integer n.

Prove that \(f_{1}^{2}+f_{2}^{2}+\cdots+f_{n}^{2}=f_{n} f_{n+1}\) when \(n\) is a positive integer. ________________ Equation Transcription: Text Transcription: f_{1}^{2}+f_{2}^{2}+\cdots+f_{n}^{2}=f_{n} f_{n+1 n

Problem 13E Prove that when n is a positive integer.

Problem 14E Show that when n is a positive integer.

Show that \(f_{0} f_{1}+f_{1} f_{2}+\cdots+f_{2 n-1} f_{2 n}=f_{2 n}^{2}\) when \(n\) is a positive integer. ________________ Equation Transcription: Text Transcription: f_{0} f_{1}+f_{1} f_{2}+\cdots+f_{2 n-1} f_{2 n}=f_{2 n}^{2} n

Show that \(f_{0}-f_{1}+f_{2}-\cdots-f_{2 n-1}+f_{2 n}= f_{2 n-1}-1\) when \(n\) is a positive integer. ________________ Equation Transcription: Text Transcription: f_{0}-f_{1}+f_{2}-\cdots-f_{2 n-1}+f_{2 n}= f_{2 n-1}-1 n

Problem 17E Determine the number of divisions used by the Euclidean algorithm to find the greatest common divisor of the Fibonacci numbers fn and fn+1 where n is a nonnegative integer. Verify your answer using mathematical induction.

Problem 18E Let Show that when n is a positive integer.

Problem 19E By taking determinants of both sides of the equation in Exercise 18. prove the identity given in Exercise 14. (Recall that the determinant of the matrix is ad ?bc.)

Problem 20E Give a recursive definition of the functions max and min so that max(a1, a2,…. an) and min(a1, a2,…. an) are the maximum and minimum of the n numbers a1, a2,…. an respectively.

Problem 21E Let a1, a2,…. an and b1,b2.... bn be real numbers. Use the recursive definitions that you gave in Exercise 20 to prove these. a)max(?a1, ?a2,…, ?an) = ?min(a1, a2,…. an) ________________ b)max(a1 + b1, a2 + b2,…, an + bn)? max(a1, a2,…. an) + max(b1, b2…., bn) ________________ c)min(a1 + b1, a2 + b2,…, an + bn) ? min(a1, a2,…. an) + min(b1, b2…., bn)

Problem 23E Give a recursive definition of the set of positive integers that are multiples of 5.

Problem 22E Show that the set S defined by 1 ? S and s + 1 ? S whenever s ? S and t ? S is the set of positive integers.

Problem 24E Give a recursive definition of a) the set of odd positive integers. ________________ b) the set of positive integer powers of 3. ________________ c) the set of polynomials with integer coefficients.

Problem 25E Give a recursive definition of a) the set of even integers. ________________ b) the set of positive integers congruent to 2 modulo 3. ________________ c) the set of positive integers not divisible by 5.

Problem 26E Let S be the subset of the set of ordered pairs of integers defined recursively by Basis step: (0, 0) ? S. Recursive step: If (a, b)? S, then (a + 2, b + 3) ? S and (a +3,b + 2) ? S. a) List the elements of S produced by the first five applications of the recursive definition. ________________ b) Use strong induction on the number of applications of the recursive step of the definition to show that 5 | a + b when (a, b) ? S. ________________ c) Use structural induction to show that 5 | a + b when (a,b) ? S.

Problem 27E Let S be the subset of the set of ordered pairs of integers defined recursively by Basis step: (0,0) ? S. Recursive step: If (a,b) ? S, then (a, b + 1) ? S , (a + 1, b + 1) ? S, and (a + 2, b + 1) ? S. a) List the elements of S produced by the first four applications of the recursive definition. ________________ b) Use strong induction on the number of applications of the recursive step of the definition to show that a ? 2b whenever (a, b) ? S. ________________ c) Use structural induction to show that a ? 2b whenever (a, b) ? S.

Problem 28E Give a recursive definition of each of these sets of ordered pairs of positive integers. [Hint: Plot the points in the set in the plane and look for lines containing points in the set.] a) S = {(a, b) | a ? Z+, b? Z+, and a + b is odd} ________________ b) S = {(a. b) | a ? Z+, b ? Z+, and a | b} ________________ c) S = ¡(a, b) | a ? Z+, b ? Z+, and 3 | a + b}

Problem 29E Give a recursive definition of each of these sets of ordered pairs of positive integers. Use structural induction to prove that the recursive definition you found is correct. [Hint: To find a recursive definition, plot the points in the set in the plane and look for patterns.] a) S = {(a, b) | a ? Z+, b? Z+, and a + b is even} ________________ b) S = {(a. b) | a ? Z+, b ? Z+, and a or b is odd } ________________ c) S = ¡(a, b) | a ? Z+, b ? Z+, a + b is odd and 3 | b}

Problem 31E Define well-formed formulae of sets, variables representing sets, and operators from {? ,?,?,?}.

Problem 32E a) Give a recursive definition of the function ones(s),which counts the number of ones in a bit string s. ________________ b) Use structural induction to prove that ones(st) = ones(s) + ones(t).

Problem 33E a) Give a recursive definition of the function m(s),which equals the smallest digit in a nonempty string of decimal digits. ________________ b) Use structural induction to prove that m(st) = min(m(s), m(t)). The reversal of a string is the string consisting of the symbols of the string in reverse order. The reversal of the string w is denoted by wR.

Problem 34E Find the reversal of the following bit strings. a) 0101 ________________ b) 1 1011 ________________ c) 1000 1001 0111

Problem 35E Give a recursive definition of the reversal of a string. [Hint: First define the reversal of the empty string. Then write a string w of length n + 1 as xy, where x is a string of length n, and express the reversal of w in terms of xR and y.]

Problem 36E Use structural induction to prove that (w1w2)R = w2Rw 1R

Problem 37E Give a recursive definition of wi, where w is a string and i is a nonnegative integer. (Here wi represents the concatenation of i copies of the string w)

Problem 38E Give a recursive definition of the set of bit strings that are palindromes.

Problem 39E When does a string belong to the set 4 of bit strings defined recursively by ? ? A 0x 1 ? A if x ? A where ? is the empty string?

Problem 40E Recursively define the set of bit strings that have more zeros than ones.

Problem 41E Use Exercise 37 and mathematical induction to show that l(wi) = i l(w), where w is a string and i is a nonnegative integer.

Problem 42E Show that (wR)i = (wi)R whenever w is a string and i is a nonnegative integer; that is, show that the i th power of the reversal of a string is the reversal of the ith power of the string.

Problem 43E Use structural induction to show that n(T) ? 2h(T) + 1, where T is a full binary tree, n(T) equals the number of vertices of T, and h(T) is the height of T.

Problem 44E The set of leaves and the set of internal vertices of a full binary tree can be defined recursively. Basis step: The root r is a leaf of the full binary tree with exactly one vertex r. This tree has no internal vertices. Recursive step: The set of leaves of the tree T = T1 + T2 is the union of the sets of leaves of T1 and of T2 .The internal vertices of T are the root r of T and the union of the set of internal vertices of T1 and the set of internal vertices of T2. Use structural induction to show that l(T), the number of leaves of a full binary tree T, is 1 more than i(T), the number of internal vertices of T.

Use generalized induction as was done in Example 13 to show that if \(a_{m, n}\) is defined recursively by \(a_{0,0}=0\) and \(a_{m, n}= \begin{cases}a_{m-1, n}+1 & \text { if } n=0 \text { and } m>0 \\ a_{m, n-1}+1 & \text { if } n>0\end{cases}\) then \(a_{m, n}=m+n\) for all \((m, n) \in \mathbf{N} \times \mathbf{N}\). ________________ Equation Transcription: Text Transcription: a_{m, n} a_{0,0}=0 a_{m, n}= a_{m-1, n}+1 & { if } n=0 { and } m>0 \\ a_{m, n-1}+1 & { if } n>0 a_{m, n}=m+nl (m, n) \in N X N

Use generalized induction as was done in Example 13 to show that if \(a_{m, n}\) is defined recursively by \(a_{1,1}=5\) and \(a_{m, n}= \begin{cases}a_{m-1, n}+2 & \text { if } n=1 \text { and } m>1 \\ a_{m, n-1}+2 & \text { if } n>1,\end{cases}\) then \(a_{m, n}=2(m+n)+1\) for all \((m, n) \in \mathbf{Z}^{+} \times \mathbf{Z}^{+}\). ________________ Equation Transcription: Text Transcription: a_{m, n} a_{1,1}=5 a_{m, n}= a_{m-1, n}+2 & { if } n=1 \text { and } m>1 \\ a_{m, n-1}+2 & { if } n>1, a_{m, n}=2(m+n)+1 (m, n) \in Z^{+} X Z^{+}

A partition of a positive integer \(n\) is a way to write \(n\) as a sum of positive integers where the order of terms in the sum does not matter. For instance, \(7=3+2+1+1\) is a partition of 7 . Let \(P_{m}\) equal the number of different partitions of \(m\), and let \(P_{m, n}\) be the number of different ways to express \(m\) as the sum of positive integers not exceeding \(n\). a) Show that \(P_{m-m}=P_{m}\) b) Show that the following recursive definition for \(P_{m, n}\) is correct: \(P_{m, n}= \begin{cases}1 & \text { if } m=1 \\ 1 & \text { if } n=1 \\ P_{m, m} & \text { if } m<n \\ 1+P_{m, m-1} & \text { if } m=n>1 \\ P_{m, n-1}+P_{m-n, n} & \text { if } m>n>1\end{cases}\) c) Find the number of partitions of 5 and of 6 using this recursive definition. Consider an inductive definition of a version ofAckermann's function. This function was named after WilhelmAckermann, a German mathematician who was a student of the great mathematician David Hilbert. Ackermann's function plays an important role in the theory of recursive functions and in the study of the complexity of certain algorithms involving set unions. (There are several different variants of this function. All are called Ackermann's function and have similar properties even though their values do not always agree.) \(A(m, n)= \begin{cases}2 n & \text { if } m=0 \\ 0 & \text { if } m \geq 1 \text { and } n=0 \\ 2 & \text { if } m \geq 1 \text { and } n=1 \\ A(m-1, A(m, n-1)) & \text { if } m \geq 1 \text { and } n \geq 2\end{cases}\) Equation Transcription: Text Transcription: n n P_m m P_m,n m n P_m, m P_m P_m, n = P_{m, n}= \begin{cases}1 & \text { if } m=1 \\ 1 & \text { if } n=1 \\ P_{m, m} & \text { if } m<n \\ 1+P_{m, m-1} & \text { if } m=n>1 \\ P_{m, n-1}+P_{m-n, n} & \text { if } m>n>1\end{cases}

Problem 48E Consideran inductive definition of a version of Ackermann's function. This function was named after Wilhelm Ackermann. a German mathematician w ho was a student of the great mathematician David Hilbert. Ackermann's function plays an important role in the theory of recursive functions and in the study of the complexity of certain algorithms involving set unions. (There are several different variants of this function. All are called Ackermann's function and have similar properties even though their values do not always agree.) involve this version of Ackermann's function. Find these values of Ackermann's function. a) A(1,0) ________________ b) A(0, 1) ________________ c) A(1, 1) ________________ d) A(2, 2)

Problem 49E Consideran inductive definition of a version of Ackermann's function. This function was named after Wilhelm Ackermann. a German mathematician w ho was a student of the great mathematician David Hilbert. Ackermann's function plays an important role in the theory of recursive functions and in the study of the complexity of certain algorithms involving set unions. (There are several different variants of this function. All are called Ackermann's function and have similar properties even though their values do not always agree.) involve this version of Ackermann's function. Show that A(m, 2) = 4 whenever m ? 1.

Problem 50E Consideran inductive definition of a version of Ackermann's function. This function was named after Wilhelm Ackermann. a German mathematician w ho was a student of the great mathematician David Hilbert. Ackermann's function plays an important role in the theory of recursive functions and in the study of the complexity of certain algorithms involving set unions. (There are several different variants of this function. All are called Ackermann's function and have similar properties even though their values do not always agree.) involve this version of Ackermann's function. Show that A(1, n) = 2n whenever n ? 1.

Find these values of Ackermann’s function. a) \(A(2, 3)\) *b) \(A(3, 3)\) Equation Transcription: Text Transcription: A(2, 3) A(3, 3)

Problem 52E Consideran inductive definition of a version of Ackermann's function. This function was named after Wilhelm Ackermann. a German mathematician w ho was a student of the great mathematician David Hilbert. Ackermann's function plays an important role in the theory of recursive functions and in the study of the complexity of certain algorithms involving set unions. (There are several different variants of this function. All are called Ackermann's function and have similar properties even though their values do not always agree.) involve this version of Ackermann's function. Find A(3.4).

Prove that \(A(m, n + 1) > A(m, n)\) whenever m and n are nonnegative integers. Equation Transcription: Text Transcription: A(m, n + 1) > A(m, n)

Problem 54E Consideran inductive definition of a version of Ackermann's function. This function was named after Wilhelm Ackermann. a German mathematician w ho was a student of the great mathematician David Hilbert. Ackermann's function plays an important role in the theory of recursive functions and in the study of the complexity of certain algorithms involving set unions. (There are several different variants of this function. All are called Ackermann's function and have similar properties even though their values do not always agree.) involve this version of Ackermann's function. Prove that A(m + 1,) > A(m.n) whenever m and n are nonnegative integers.

Problem 55E Consideran inductive definition of a version of Ackermann's function. This function was named after Wilhelm Ackermann. a German mathematician w ho was a student of the great mathematician David Hilbert. Ackermann's function plays an important role in the theory of recursive functions and in the study of the complexity of certain algorithms involving set unions. (There are several different variants of this function. All are called Ackermann's function and have similar properties even though their values do not always agree.) involve this version of Ackermann's function. Prove that A(i, j) ? j whenever i and j are nonnegative integers.

Problem 56E Use mathematical induction to prove that a function F defined by specifying F(0) and a rule for obtaining F(n + 1) from F(n) is well defined.

Problem 57E Use strong induction to prove that a function F defined by specifying F(0) and a rule for obtaining F(n + 1) from the values F(k) for k = 0, 1,2 .... n is well defined.

Problem 58E how that each of these proposed recursive definitions of a function on the set of positive integers does not produce a well-defined function. a) F(n) = 1 + F([n/2]) for n ? 1 and F(1) = 1. ________________ b) F(n) = 1 + F(n - 3) for n ? 2, F(1) = 2, and F(2) = 3. ________________ c) F(n) = 1 + F(n/2) for n > 2, F(l) = 1, and F(2) = 2. ________________ d) F(n) = 1 + F(n/2) if n is even and n? 2, F(n) = 1 - F(n - 1) if n is odd, and F(l) = 1. ________________ e) F(n) = 1 + F(n/2) if n is even and n? 2. F(n) = F(3n — 1) if n is odd and n ? 3, and F(l) = 1.

Problem 59E Show that each of these proposed recursive definitions of a function on the set of positive integers does not produce a well-defined function. a) F(n) = 1 + F([(n + 1)/2]) for n ? 1 and F(1) = 1. ________________ b) F(n) = 1 + F(n - 2) for n ?2 and F(l) = 0. ________________ c) F(n) = 1 + F(n/3) for n ? 3, F(l) = 1, F(2) = 2, and F(3) = 3. ________________ d) F(n) = 1 + F(n/2) if n is even and n ? 2,F(n) = 1 + F(n - 2) if n is odd, and F(l) = 1. ________________ e) F(n) = 1 + F(F(n - 1)) if n ? 2 and F(l) = 2.

Find these values. a) \(\log \left({ }^{2}\right) 16\) b) \(\log \left({ }^{3}\right) 256\) c) \(\log \left({ }^{3}\right) 2^{65536}\) d) \(\log (4) 2^{2^{65536}}\) Equation Transcription: Text Transcription: log^(2) 16 log^(3) 256 log^(3) 2^65536 log(^4) 2^2^65536

Find the value of \(\log ^{*} n\) for these values of \(n\). a) 2 b) 4 c) 8 e) 256 f) 65536 g) \(2^{2048}\) d) 16 Equation Transcription: Text Transcription: log*?n n 2^2048

Find the largest integer \(n\) such that \(\log ^{*} n=5\). Determine the number of decimal digits in this number. Exercises 63-65 deal with values of iterated functions. Suppose that \(f(n)\) is a function from the set of real numbers, or positive real numbers, or some other set of real numbers, to the set of real numbers such that \(f(n)\) is monotonically increasing [that is, \(f(n)<f(m)\) when \(n<m\) ) and \(f(n)<n\) for all \(n\) in the domain of \(f .]\) The function \(f^{(k)}(n)\) is defined recursively by \(f^{(k)}(n)= \begin{cases}n & \text { if } k=0 \\ f\left(f^{(k-1)}(n)\right) & \text { if } k>0\end{cases}\) Furthermore, let \(c\) be a positive real number. The iterated function \(f_{c}^{*}\) is the number of iterations of \(f\) required to reduce its argument to \(c\) or less, so \(f_{c}^{*}(n)\) is the smallest nonnegative integer \(k\) such that \(f^{k}(n) \leq c\). Equation Transcription: Text Transcription: n lof(n)g*?n=5 f(n)<n f(n)<f(m) n<m f^(k)(n) f^(k)(n)={n if k=0 f(f^(k-1)(n)) if k>0 f_c^* f^k(n) < or = c

Let \(f(n)=n-a\), where \(a\) is a positive integer. Find a formula for \(f^{(k)}(n)\). What is the value of \(f_{0}^{*}(n)\) when \(n\) is a positive integer? Equation Transcription: Text Transcription: f(n)=n-a f^(k)(n) f_0^*(n) n

Problem 64E deal with values of iterated functions. Suppose that f(n) is a function from the set of real numbers, or positive real numbers, or some other set of real numbers, to the set of real numbers such that f(n) is monotonically increasing [that is, f(n)<f(m) when n<m) and f(n)<n for all n in the domain of f.] The function f(k)(n) is defined recursively by Furthermore, let c be a positive real number. The iterated function is the number of iterations of f required to reduce its argument to c or less, so is the smallest nonnegative integer k such that fk(n) ? c. Let f(n) = n/2. Find a formula for f(k)(n). What is the value of when n is a positive integer?