Infinite sequences can often be defined in a recursive way. Every recursive definition needs a base case defining the first values in the sequence (at least one) and the rule for forming an element using previously computed ones.
Below are some examples:
Powers of 2
- 1, 2, 4, 16, 32, 64, …., 2n, …
- Base case: P(0) = 1, P(1) = 2
- P(n) = 2 x P(n-1)
An arbitrary sequence
- 2, 3, 6, 18, 108, 1944, ….
- Base cases: a(0) = 2 and a(1) = 3
- a(n) = a(n-1) x a(n-2)
- see Video at https://www.khanacademy.org/math/integral-calculus/sequences_series_approx_calc/calculus-sequences/v/term-of-recursive-sequence
Factorials
- n! is the product of all positive integers less than or equal to n.
- For example, 5! = 5 x 4 x 3 x 2 x 1 = 120
- Base case: F(1)=1
- F(n) = n x F(n-1) for n >1
- Interesting facts and uses of factorials can be found at http://www.mathsisfun.com/numbers/factorial.html.
Fibonacci sequence
- 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, …
- Base cases: f(0)=0 and f(1)=1
- f(n) = f(n-1) + f(n-2) for n>1
- we describe different ways computing f(n) in Example 5: Computing a Fibonacci number.
- Interesting information and historical facts about Fibonacci numbers can be found at
Exercises a teacher can do with students
- For Fibonacci numbers, ask students to compute a specified value, like f(15) , with paper and pencil. Let them find their own way of doing it and ask them to explain how the managed the results computed. Did they use recursion?
- Give students a sequence and ask them to determine the recursive definition generating the sequence. For example
- 1, 3, 9, 27, 81, 243, ….
- 1, 7, 49, 343, …
