Sec 53

35 .
: I Induction and Recursion

-. a recursive definition of the sequence {an}, n =
:. _. , .. . if
a an = 6n. b) an = 2n + l.
e an = lO
n
. d) an = 5.
a recursive definition of the sequence {an}, n =
: __ . 3, .. . if
a) a
n
=4n-2. b) a
n
=l+(-1)n.
e an = n(n + 1). d) an = n2.
. Ler F be the function such that F (n) is the sum of the first
'1 positive integers_ Give a recursive definition of F(n).
1 . GiYe a recursive definition of Sm(n), the sum of the inte-
ger m and the nonnegative integer n.
11. GiYe a recursive definition of Pm (n), the product of the
inreger m and the nonnegative integer n .
." Exercises 12-19 In is the nth Fibonacci number.
12. Prove that If + + ... + I;; = Inln+1 when n is a
positive integer.
13. Prove that 11 + /3 + ... + hn-l = hn when n is a pos-
iti e integer.
* Show that In+! In-l - I;; = (_1)n when n is a positive
integer.
* 15. Show that 10/1 + hh + ... + hn-1hn = whenn
is a positive integer.
* 16. Show that 10 - h + 12 - . .. - hn-l + hn =
12n-1 - 1 when n is a positive integer .
. 1 . Determine the number of divisions used by the Euclidean
algorithm to find the greatest common divisor of the Fi-
bonacci numbers In and In+1, where n is a nonnegative
integer. Verify your answer using mathematical induction.
18. Let
A = [i
Show that
An = [li:1
In ]
In-1
when n is a positive integer.
19. By taking determinants of both sides of the equation in
Exercise 18, prove the identity given in Exercise 14. (Re-
call that the determinant of the matrix is ad - be.)
* 20. 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
aI, a2,., an, respectively.
*21. Let aI , a2, ... , an, and b1, b2, ... , b
n
be real numbers.
Use the recursive definitions that you gave in Exercise 20
to prove these.
a) max ( -aI, -a2, .. . , -an) = - min(a1, a2 , . . . , an)
b) max(a1 + b1 , a2 + b, . . . , an + bn)
S max(al , a2, ... , an) + max(bl, b2 , . .. , b
n
)
c) min(a1 + b1, a2 + b2 , . .. , an + bn)
:::: min(al , a2, ... , an) + min(b1, b, ... , bn)
22. Show that the set S defined by 1 E Sand s + t E S when-
ever s E Sand t E S is the set of positive integers.
23. Give a recursive definition of the set of positive integers
that are multiples of 5.
24. 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.
25. 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.
26. Let S be the subset of the set of ordered pairs of integers
defined recursively by
Basis step: (0,0) E S.
Recursive step: If (a, b) E S, then (a + 2, b + 3) E S
and (a + 3, b + 2) E S.
a) List the elements of S produced by the first five ap.
plications of the recursive definition.
b) Use induction on the number of applications
of the recursive step of the definition to show that
51 a + b when (a, b) E S.
c) Use structural induction to show that 51 a + b when
(a , b) E S.
27. Let S be the subset of the set of ordered pairs of integers
defined recursively by
Basis step: (0,0) E S.
Recursive step: If (a, b) E S, then (a, b + 1) E S,
(a + 1, b + 1) E S, and (a + 2, b + 1) E S.
a) List the elements of S produced by the first four ap-
-J3lications of The recursive definition.
b) Use strong induction on the number of applications or
the recursive step of the definition to show that a ::: 2h
whenever (a, b) E S. .
c) Use structural induction to show that a S 2b when-
ever (a , b) E S.
28. Give a recursive definition of each of these sets of ordered
pairs of positive integers. [Hint: Plot the points in the sel
in the plane and look for lines containing points in the
set. ]
a) S = {(a, b) I a E Z+, bE Z+, and a + b is odd}
b) S={(a,b)laEZ+,bEZ+,andalb}
c) S={(a,b)laEZ+,bEZ+,and3Ia+b}
29. Give a recursive definition of each of these sets of or
dered 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) I a E Z+, b E Z+, and a + b is even)
b) S = {(a , b) I a E Z+, b E Z+, and a or b is odd}
c) S = { (a , b) I a E Z+, b E Z+, a + b is odd, and 31 h)
30. Prove that in a bit string, the string 01 occurs at most one
more time than the string 10.
31. Define well-formed formulae of sets, variables represent-
ing sets, and operators from C U, n, -}.

Sec 53

Uploaded by

Copyright:

Available Formats

Sec 53

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Sec 53

Uploaded by

Copyright:

Available Formats

35 .

: I Induction and Recursion

You might also like