Reduction of Order For Recursions

[topsquark]

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...

 

[pbuk]

Continue reading...

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".

 

[topsquark]

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

 

[pbuk]

https://mathworld.wolfram.com/FiniteDifference.html

 

[topsquark]

https://mathworld.wolfram.com/FiniteDifference.html

I knew most of the article, but there were a number of topics in the links that are new to me. Thanks!

-Dan