Reduction of Order For Recursions

  • Insights
  • Thread starter topsquark
  • Start date
  • Tags
    Reduction
In summary, recursion relations, also known as recurrence relations, are a mathematical concept commonly taught in secondary school. They involve starting with a number and repeatedly adding a constant value to it to create a series of numbers. This process can be represented by a rule, such as ##a_{n + 1} = a_n + 3##, where ##a_0 = 1##. Recursion relations can be used to represent more complex series, such as the Fibonacci series, and can also be solved using finite difference calculus.
  • #1
topsquark
Science Advisor
Insights Author
Gold Member
MHB
2,021
790
This is not meant as a full introduction to recursion relations but it should suffice for just about any level of the student.
Most of us remember recursion relations from secondary school. We start with a number, say, 1. Then we add 3. That gives us 4. Now we that number and add 3 again and get 7. And so on. This process creates a series of numbers ##\{ 1, 4, 7, 10, \dots \}##. Once we get beyond that stage we start talking about how to represent these. Well, let’s call the starting number ##a_0##. Then the next number in the series would be ##a_1##, then ##a_2##, …, on to ##a_n## where n is the nth number in the series. We may now express our recursion as a rule: ##a_{n +1} = a_n + 3##, where ##a_0 = 1##.
We may go much further. We can talk about things like the Fibonacci series: ##F_{n + 2} = F_{n + 1} + F_{n}##, where ##F_1 = F_2 = 1##. This is the famous series ##\{ 1, 1, 2, 3, 5, 8, 13, \dots \}##. But what if we want a formula to find out what ##F_n## is for the nth number...

Continue reading...
 
  • Like
Likes malawi_glenn, pbuk, fresh_42 and 1 other person
Mathematics news on Phys.org
  • #2
topsquark said:
Is the term "recursion relation" in common use? I would call it a "recurrence relation".

Also I would say "finite difference calculus" instead of "difference calculus".
 
  • Like
Likes topsquark
  • #3
pbuk said:
Is the term "recursion relation" in common use? I would call it a "recurrence relation".

Also I would say "finite difference calculus" instead of "difference calculus".
Sorry! As I understand it both terms (the recursive and finite difference) are in use. However, the only work I've done with recurrence relations comes from High School and I couldn't really find much on the web about finite difference calculus. I had to fill in a lot of gaps to do this, so I may not be using standard terminology.

-Dan
 

1. What is the purpose of using reduction of order for recursions?

The purpose of using reduction of order for recursions is to simplify complex recursive equations into a lower order. This can make the equation easier to solve and understand.

2. How does reduction of order work for recursions?

Reduction of order for recursions involves rewriting the recursive equation in terms of a lower order term. This is typically done by finding a pattern in the recursive equation and using that pattern to create a new equation with a lower order.

3. When is reduction of order for recursions necessary?

Reduction of order for recursions is necessary when the recursive equation has a high order and is difficult to solve or understand. It can also be used to find closed-form solutions for recursive equations.

4. What are the steps for performing reduction of order for recursions?

The steps for performing reduction of order for recursions are: 1) Identify the pattern in the recursive equation, 2) Write a new equation using the pattern with a lower order term, 3) Substitute the new equation into the original recursive equation, and 4) Solve the resulting equation for the unknown term.

5. Are there any limitations to using reduction of order for recursions?

Yes, there are limitations to using reduction of order for recursions. It may not always be possible to find a pattern and rewrite the equation with a lower order term. Additionally, the resulting equation may still be difficult to solve or may not have a closed-form solution.

Similar threads

Replies
1
Views
896
  • General Math
Replies
7
Views
1K
  • General Math
Replies
11
Views
1K
  • General Math
Replies
1
Views
998
  • General Math
Replies
8
Views
1K
Replies
12
Views
882
  • General Math
Replies
7
Views
2K
Replies
4
Views
253
Replies
20
Views
1K
Replies
7
Views
1K
Back
Top