Mathematics
Recursion and Special Sequences
Recursion is a process of defining a function or an object in terms of itself. In mathematics, special sequences such as Fibonacci, Lucas, and Catalan numbers are examples of recursive sequences. These sequences have a recursive formula that defines each term in terms of the previous terms.
Written by Perlego with AI-assistance
Related key terms
1 of 5
4 Key excerpts on "Recursion and Special Sequences"
eBook - PDF- Peter Grossman(Author)
- 2017(Publication Date)
- Red Globe Press(Publisher)
Induction and recursion 7.1 Recursion and sequences The main purpose of this chapter is to introduce recursion. Recursion is a simple yet powerful idea that can be enormously useful in developing algorithms for solving complex problems. We will also introduce the method of proof by induction, a technique closely related to recursion. In addition to being one of the standard proof techniques in mathematics, induction is a useful technique for verifying the correctness of algorithms. A convenient way to introduce recursion is by considering infinite sequences of numbers, and this is the approach we will take here. A sequence is a list of numbers in a particular order. A general sequence can be written down in the following way: t (1), t (2), t (3), t (4), ... The numbers t (1), t (2), t (3), and so on are called the terms of the sequence. The purpose of the three dots (ellipsis) at the end is to indicate that the sequence can be regarded as continuing indefinitely. There is usually a definite pattern to the numbers in the kinds of sequences that arise in practice. For example, the positive even numbers form a sequence: 2, 4, 6, 8, 10, 12, ... In this example, t (1) = 2, t (2) = 4, t (3) = 6, and so on. A sequence can be defined by giving a formula for the general term t ( n ) in terms of the variable n . For the sequence given above, the general term is given by the formula t ( n ) = 2 n . There is a good reason for using ‘function-style’ notation for the general term of a sequence. We can think of a sequence as a particular kind of function; for example, the sequence 2, 4, 6, 8, 10, 12, ... can be identified with the following function from the set N of natural numbers to the set R of real numbers: t t n n : , ( ) N R ® = 2 114 CHAPTER 7 sequence term For convenience, we will always take the codomain of any sequence to be R , even though in the present example all the terms of the sequence are natural numbers.
eBook - PDF- Cynthia Y. Young(Author)
- 2021(Publication Date)
- Wiley(Publisher)
In mathematics, it means the same thing. For example, if we write x, 2x 2 , 3x 3 , 4x 4 , 5x 5 , ?, what would the next term in the sequence be, the one where the question mark now stands? The answer is 6x 6 . 12.1 Sequences and Series SKILLS OBJECTIVES • Find terms of a sequence given the general term. • Apply factorial notation. • Apply recursion formulas. • Use summation (sigma) notation to represent a series and evaluate finite series and infinite series (if possible). CONCEPTUAL OBJECTIVES • Recognize patterns in a sequence in order to identify the general term. • Understand why (mn)! Is not equal to m!n!. • Understand why the Fibonacci sequence is a recursion formula. • Understand why all finite series sum and why infinite series may or may not sum. In This Chapter We will discuss counting and probability in addition to three other topics: sequences and series, mathematical induction, and the binomial theorem. • Find the general nth term of a sequence or series. • Evaluate a finite arithmetic series. • Determine if an infinite geometric series converges or diverges. • Prove a mathematical statement using induction. • Use the binomial theorem to expand a binomial raised to a positive integer power. • Understand the difference between permutations and combinations. • Calculate the probability of an event. LEARNING OBJECTIVES 1114 CHAPTER 12 Sequences, Series, and Probability A Sequence A sequence is a function whose domain is a set of positive integers. The function values, or terms, of the sequence are written as a 1 , a 2 , a 3 , . . . , a n , . . . Rather than using function notation, sequences are usually written with subscript (or index) notation, a subscript . A finite sequence has the domain {1, 2, 3, . . . , n} for some positive integer n. An infinite sequence has the domain of all positive integers {1, 2, 3, . . .}. There are times when it is convenient to start the indexing at 0 instead of 1: a 0 , a 1 , a 2 , a 3 , .
eBook - PDFHow to Count
An Introduction to Combinatorics, Second Edition
- R.B.J.T. Allenby, Alan Slomson(Authors)
- 2010(Publication Date)
- Chapman and Hall/CRC(Publisher)
Recursive functions are studied in the branch of mathematical logic known as recursive function theory or computability theory. Recursive definitions are also allowed in several programming languages. Recurrence relations are classified according to the form of the function f that occurs in the relation. In this chapter we discuss recurrence relations that can be solved using the device of generating functions. Exercises 7.3.1A Find a recurrence relation and initial conditions for the sequence { a n }, where a n is the number of strings of n digits (that is, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9) that do not contain consecutive even digits (where 0 counts as an even digit). 7.3.1B Find a recurrence relation and initial conditions for the sequence { a n }, where n is the number of strings of n digits that contain no consecutive 0s, no consecutive 1s, and no consecutive 2s. 7.4 FIBONACCI NUMBERS We have already seen in Section 7.2 how to work out the generating function of the sequence defined by the recurrence relation given by Equation 7.8. We are now going to take this idea further. If we have an explicit formula for the generating function, we may be able to use this to derive a formula for the coefficients in its power series. These coefficients are, of course, just the terms of the sequence in which we are interested. Before discussing the general method we give another illustration in relation to, perhaps, the best known of all sequences defined by a recurrence relation, namely, the Fibonacci numbers . These numbers are named after the Italian mathematician Leonardo of Pisa,* who introduced them in connection with the following problem. * Leonardo of Pisa lived during the late twelfth and early thirteenth century.
eBook - PDF- Thomas Koshy(Author)
- 2004(Publication Date)
- Academic Press(Publisher)
Chapter 5 Recursion It is common sense to take a method and try it. If it fails, admit it frankly and try another. But above all, try something. — FRANKLIN ROOSEVELT R ecursion is an elegant and powerful problem-solving technique, used extensively in both discrete mathematics and computer science. Many programming languages, such as ALGOL, FORTRAN 90, C++, and Java, support recursion. This chapter investigates this powerful method in detail. In addition, we will study three simple methods for solving recurrence relations: iteration, characteristic equations, and generating functions. We also will establish the validity of recursive algorithms using induction and analyze their complexities using the big-oh and big-theta notations. Some of the interesting problems we pursue in this chapter are: • There are three pegs X, Y, and Z on a platform and 64 disks of increasing sizes at X. We would like to move them from X to Z using Y as an auxiliary peg subject to the following conditions: Only one disk can be moved at a time. No disk can be placed on the top of a smaller disk. If it takes one second to transfer a disk from one peg to another, how long will it take to solve the puzzle? • Is there a formula for the number of n -bit words containing no two consecutive 1’s? • Suppose we introduce a mixed pair (male and female) of 1-month-old rabbits into a large enclosure on January 1. By the end of each month, the rabbits become mature, and each pair produces k − 1 mixed pairs of offspring at the beginning of the following month. Find the average age of the rabbit pairs at the beginning of the n th month. • Can we estimate the number of divisions required to compute gcd { a , b } by the euclidean algorithm? • What is a divide-and-conquer algorithm? If f ( n ) denotes the number of operations required by such an algorithm, what can you say about its order of complexity? 261
Index pages curate the most relevant extracts from our library of academic textbooks. They’ve been created using an in-house natural language model (NLM), each adding context and meaning to key research topics.
