- #1
- 2,019
- 825
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...
Is the term "recursion relation" in common use? I would call it a "recurrence relation".topsquark said:
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.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".
I knew most of the article, but there were a number of topics in the links that are new to me. Thanks!pbuk said:
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.
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.
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.
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.
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.