Recursive Formula

5/5 - (1 bình chọn)

Before going to learn the recursive formula, let us recall what is a recursive function. A recursive function is a function that defines each term of a sequence using a previous term that is known, i.e. where the next term is dependent on one or more known previous term(s). A recursive function h(x) can be written as:

h(x) = a0 h(0) + a1h(1) + ……. + ax-1 h(x-1) where ai ≥ 0 and at least one of the ai > 0

Let us learn the recursive formulas in the following section.

What Are Recursive Formulas?

A recursive formula refers to a formula that defines each term of a sequence using the preceding term(s). The recursive formulas define the following parameters:

  • The first term of the sequence
  • The pattern rule to get any term from its previous term

Recursive Formulas

The following are the recursive formulas for different kinds of sequences.

Recursive Formula for Arithmetic Sequence

The recursive formula to find the nth term of an arithmetic sequence is:

an = an-1 + d for n ≥ 2

where

  • an is the nth term of a A.P.
  • d is the common difference.

Recursive Formula for Geometric Sequence

The recursive formula to find the nth term of a geometric sequence is:

an = an-1 r for n ≥ 2

where

  • an is the nthterm of a G.P.
  • r is the common ratio.

Recursive Formula for Fibonacci Sequence

The recursive formula to find the nth term of a Fibonacci sequence is:

an = an-1 + an-2 for n ≥ 2, where

  • a0 = 1 and
  • a1 = 1

where an is the nthterm of the sequence.

Let us see the applications of the recursive formulas in the following section.

Examples Using Recursive Rule

Example 1: The recursive formula of a function is, f(x) = 5 f(x-2) + 3, find the value of f(8). Given that f(0) = 0.

Solution:

f(8) = 5 f(6) + 3
f(6) = 5 f(4) + 3
f(4) = 5 f(2) + 3

It is given that f(0) = 0. Thus,

f(2) = 5 f(0) + 3 = 3
f(4) = 5 × 3 + 3 = 18
f(6) = 5 × 18 + 3 = 93
f(8) = 5 × 93 + 3 = 468

Answer: The value of f(8) is 468.

Example 2: Find the recursive formula for the following arithmetic sequence: 1, 6, 11, 16 …..

Solution:

Let an be the nth term of the series and d be the common difference.

d = a2 – a1= 6 – 1 = 5

an = an-1 + 5

Answer: The recursive formula for this sequence is an = an-1 + 5

Example 3: The 13th and 14th terms of the Fibonacci sequence are 144 and 233 respectively. Find the 15th term.

Solution:

Using the recursive formula for the Fibonacci sequence,

15th term is the sum of 13th term and 14th term.

15th term = 13th term + 14th term

= 144 + 233

= 377

Answer: The 15th term of the Fibonacci sequence is 377.

FAQs on Recursive Formula

What is the Recursive Formula in Math?

A recursive formula is a formula that defines any term of a sequence in terms of its preceding term(s). For example:

  • The recursive formula of an arithmetic sequence is, an = an-1 + d
  • The recursive formula of a geometric sequence is, an = an-1r

Here, an represents the nth term and an-1 represents the (n-1)th term.

How to Find the Recursive Formula for an Arithmetic Sequence?

To find a recursive sequence in which terms are defined using one or more previous terms which are given.

  • Step 1: Identify the nth term (an) of an arithmetic sequence and the common difference, d,
  • Step 2: Put the values in the formula, an+1 = an + d to find the (n+1)th term to find the successive terms.

What is the Recursive Rule For the Fibonacci series?

The Fibonacci series is characterized as the series in which each number is the sum of two numbers preceding it in the sequence. Thus, the Fibonacci formula is given as, Fn = F(n-1) + F(n-2), where n > 1.

What Is an in Recursive Formula?

In any recursive formula, an refers to the nth term in the sequence, which can be found using the recursive formulas:

  • nth term of A.P: an = an-1 + d for n ≥ 2
  • nth term of G.P: an = an-1 for n ≥ 2
  • nth term of a Fibonacci Sequence: an = an-1 + an-2 for n ≥ 2

What is the Difference Between Recursive and Explicit Formulas?

The recursive formula is used to find a term of a sequence when its previous term is known. The explicit formula is used to find the term of a sequence irrespective of information about its previous term. For example:

  • The recursive formula to find the nth term of AP is: an = an-1 + d
  • The explicit formula to find the nth term of AP is, an = a + (n – 1) d

What Is A Sequence

Formally, a sequence is an enumerated collection of objects, but informally, a sequence is a countable structure representing an ordered list of elements or numbers.

And we specify a sequence either recursively or explicitly.

Recursive Formula Definition

So, what is recursion?

A recursive definition, sometimes called an inductive definition, consists of two parts:

  1. Recurrence Relation
  2. Initial Condition

A recurrence relation is an equation that uses a rule to generate the next term in the sequence from the previous term or terms. In other words, a recurrence relation is an equation that is defined in terms of itself.

And all recurrence relations must come with an initial condition, which is a list of one or more terms of the sequence that precede the first term where the recurrence relation starts.

Example

For instance,

Notice that this looks just like the procedure we use for mathematical induction!

The idea behind inductive proofs is similar to a staircase, as the only way to reach the top is to climb all the steps before it, as noted by Math Bits. The same thing is happening with recursion – each step is generated from the step or steps preceding.

Recursive Formulas For Sequences

Alright, so as we’ve just noted, a recursive sequence is a sequence in which terms are defined using one or more previous terms along with an initial condition. And the most classic recursive formula is the Fibonacci sequence.

The Fibonacci sequence is as follows: 0, 1, 1, 2, 3, 5, 8, 13, 21,…

Notice that each number in the sequence is the sum of the two numbers that precede it. For example, 13 is the sum of 5 and 8 which are the two preceding terms.

In fact, the flowering of a sunflower, the shape of galaxies and hurricanes, the arrangements of leaves on plant stems, and even molecular DNA all follow the Fibonacci sequence which when each number in the sequence is drawn as a rectangular width creates a spiral.

Isn’t it amazing to think that math can be observed all around us?

But, sometimes using a recursive formula can be a bit tedious, as we continually must rely on the preceding terms in order to generate the next.

So now, let’s turn our attention to defining sequence explicitly or generally. All this means is that each term in the sequence can be calculated directly, without knowing the previous term’s value.

Example

In this problem,

What we will notice is that patterns start to pop-up as we write out terms of our sequences. And it’s in these patterns that we can discover the properties of recursively defined and explicitly defined sequences.

We want to remind ourselves of some important sequences and summations from Precalculus, such as Arithmetic and Geometric sequences and series, that will help us discover these patterns.

Arithmetic Sequence Formula
Geometric Sequence Formula
Summation Sequence Formulas

Armed with these summation formulas and techniques, we will begin to generate recursive formulas and closed formulas for other sequences with similar patterns and structures.

Example

So, using our known sequences, let’s find a recursive definition for the sequence 4,9,14,19,24,29,…

Arithmetic Recursive — Example

Now, using our known summation formulae, let’s find a closed definition for the same sequence of 4,9,14,19,24,29,…

Closed Form Arithmetic Sequence

Additionally, we will discover a superb procedure for finding the sum of an Arithmetic and Geometric sequence, using Gauss’s discovery of reverse-add and multiply-shift-subtract, respectively.

Example

Suppose we wanted to find the sum of the following sequence: 1,3,5,7,9,..,39.

First, we need to find the closed formula for this arithmetic sequence. To do this, we need to identify the common difference which is the amount that is being added to each term that will generate the next term in the sequence. The easiest way to find it is to subtract two adjacent terms. So, for our current example, if we subtract any two adjacent terms we will notice that the common difference is 2.

Find Closed Form Of Arithmetic Sequence

Now, we can use the explicit formula to determine the number of terms that we are summing.

Determine The Number Of Terms In Arithmetic Series

Finally, we apply the reverse and add method to find the sum, where we first list all the terms in one direction, then reverse and list all the terms in the opposite direction. In other words, we will “wrap” the series back onto itself, as MathBitsNotebook nicely states.

Gauss Method Sum

Summary

Throughout this video, we will see how a recursive formula calculates each term based on the previous term’s value, so it takes a bit more effort to generate the sequence. In contrast, an explicit formula directly calculates each term in the sequence and quickly finds a specific term.

Both formulas, along with summation techniques, are invaluable to the study of counting and recurrence relations. And with these new methods, we will not only be able to develop recursive formulas for specific sequences, but we will be on our way to solving recurrence relations!

So, let’s jump right in and discover the fun!

If you know the nth term and the common ratio , r , of a geometric sequence , you can find the (n+1)th

term using the recursive formula.

an+1=anr .

Example 2:

Write the first four terms of the geometric sequence whose first term is a1=3 and whose common ratio is r=2

Sequences as Functions – Recursive

Sample Problems

Question 1: Given a series of numbers with a missing number in middle 1, 11, 21, ?, 41. Using recursive formula find the missing term.

Solution:

Given,

1, 11, 21, _, 41

First term (a) = 1

Difference between terms = 11 – 1 = 10

21 – 11 = 10

So the difference between numbers is same.

Common Difference (d) = 10

Recursive Function to find nth term is an = an-1 + d

a4 = a4-1 + d

= a3 + d

= 21 + 10

a4 = 31

Missing term in the given series is 31.

Question 2: Given series of numbers 5, 9, 13, 17, 21,… From the given series find the recursive formula 

Solution:

Given number series

5, 9, 13, 17, 21,…

first term (a) = 5

Difference between terms = 9 – 5 = 4

13 – 9 = 4

17 – 13 = 4

21 – 17 = 4

So the difference between numbers is same.

Common Difference (d) = 4

The given number series is in Arithmetic progression.

So recursive formula an = an-1 + d

an = an-1 + 4

Question 3: Given a series of numbers with a missing number in middle 1, 3, 9, _, 81, 243. Using recursive formula find the missing term.

Solution:

Given,

1, 3, 9, _, 81, 243

First term (a) = 1

The difference between numbers are large so It should not be in Arithmetic progression. 

Let’s check whether it is in Geometric progression or not,

a2/a1 = 3/1 = 3

a3/a2 = 9/3 = 3

a5/a4 = 243/81 = 3

Hence ratio between adjacent numbers are same. So given series is in Geometric Progression 

Common Ratio (r) = 3

Recursive Function to find nth term is an = an-1 × r

a4 = a4-1 × r

= a3 × r

= 9 × 3

a4 = 27

Missing term in the given series is 27.

Question 4: Given series of numbers 2, 4, 8, 16, 32, … From the given series find the recursive formula.

Solution:

Given number series,

2, 4, 8, 16, 32, …

First term (a) = 2

Difference between terms = 4 – 2 = 2

8 – 4 = 4

It is not in A.P as difference between numbers are not same.

Let’s check whether it is in Geometric progression or not

a2/a1 = 4/2 = 2

a3/a2 = 8/4 = 2

a4/a3 = 16/8 = 2

Common Ratio (r) = 2

The given number series is in Geometric progression.

So recursive formula an = an-1 × r

an = an-1 × 2

Question 5: Find the 5th term in a Fibonacci series if the 3rd and 4th terms are 2,3 respectively.

Solution:

Given that number series is in fibonacci series form.

Also given a3 = 2

a4 = 4

Then a5 = a3 + a4

= 2 + 3

a5 = 5

Question 6: Find the next term in the given series 1, 1, 2, 3, 5, 8, 13, …

Solution:

Given, 

1, 1, 2, 3, 5, 8, 13,…

The given series is in fibonacci form because every nth term is the result of addition between two previous terms i.e., n – 1th & n – 2th terms

Example: a3 = a1 + a2

3 = 1 + 2

Then a8 = a7 + a6

= 13 + 8

a8 = 21

Recursive Formula Examples

Example 1:

Let t1=10 and tn= 2tn-1+1

So the series becomes;

t1=10

t2=2t1+1=21

t3=2t2+1= 43

And so on…

Example 2: Find the recursive formula which can be defined for the following sequence for n > 1.
65, 50, 35, 20,….
Solution:
Given sequence is 65, 50, 35, 20,….
a1 = 65
a2 = 50
a3 = 35
a2 – a1 = 50 – 65 = -15
a3 – a2 = 35 – 50 = -15
Thus, a2 = a1 – 15
Similarly, a3 – a2 = -15
From this we can write the recursive formula as: an = an-1 – 15

Example 3: Calculate f(9) for the recursive series f(x) = 3. f(x – 2) + 4 which has a seed value of f(3) = 9.

Solution:
Given,
f(3) = 9
f(x) = 3.f(x – 2) + 4
f(9) = 3.f(9-2) + 4
= 3.f(7) + 5
f(7) = 3.f(7-2) + 4
= 3.f(5) + 4
f(5) = 3.f(5-2) + 4
= 3.f(3) + 4
Substituting f(3) = 9,
f(5) = 3(9) + 4 = 27 + 4 = 31
f(7) = 3(31) + 4 = 93 + 4 = 97
f(9) = 3(97) + 4 = 291 + 4 = 295

GIA SƯ TOÁN BẰNG TIẾNG ANH ⭐️⭐️⭐️⭐️⭐️

GIA SƯ DẠY SAT ⭐️⭐️⭐️⭐️⭐️

Mọi chi tiết liên hệ với chúng tôi :
TRUNG TÂM GIA SƯ TÂM TÀI ĐỨC
Các số điện thoại tư vấn cho Phụ Huynh :
Điện Thoại : 091 62 65 673 hoặc 01634 136 810
Các số điện thoại tư vấn cho Gia sư :
Điện thoại : 0902 968 024 hoặc 0908 290 601

Hãy bình luận đầu tiên

Để lại một phản hồi

Thư điện tử của bạn sẽ không được hiện thị công khai.


*