- #1
coolul007
Gold Member
- 271
- 8
- TL;DR Summary
- I may have reinvented the wheel, here is a pdf on my observations
Looks ok so far (re-opened).coolul007 said:Summary:: I may have reinvented the wheel, here is a pdf on my observations
https://www.testsite.cocoams.org/linrec.pdf
There already exists a Benet formula for the Fibonacci numbers.Svein said:Recursive formulas occur everywhere. Some examples:
Other recursives inlude the Sierpinski curves and the Hilbert curves.
- The Fibonacci series: [itex]x_{n+1}=x_{n}+x_{n-1} [/itex]
- The Mandelbrot series: [itex]z_{n+1}=z_{n}^{2}+c [/itex] where c is a given constant
- Factorials: n! = n⋅(n-1)!, (n integer >0, 0!=1)
- Square roots: [itex]x_{n+1}=\frac{1}{2}(x_{n}+\frac{a}{x_{n}}) [/itex] (for a>0)
Linear, homogeneous recurrence relations (sequences which can be defined using the form ##a_n=k_1 a_{n-1} + k_2 a_{n-2} + ... k_m a_{n-m}##) can be turned into non-recursive formulae by obtaining solutions for the characteristic polynomial.coolul007 said:There already exists a Benet formula for the Fibonacci numbers.
It seems these are solutions for a particular recursion, what I have supplied is a universal formula for all positive linear recursions.jbriggs444 said:Linear, homogeneous recurrence relations (sequences which can be defined using the form ##a_n=k_1 a_{n-1} + k_2 a_{n-2} + ... k_m a_{n-m}##) can be turned into non-recursive formulae by obtaining solutions for the characteristic polynomial.
The motivation for the technique is straightforward. Suppose that a solution takes the form ##x^n## for some value x. Then the recurrence states that ##x^m=k_1 x^{m-1} + k_2 x^{m-2} + ... k_m##. This is the characteristic polynomial for the recurrence. It will normally have m solutions. Any of those solutions will have the property that ##x^n## solves the recurrence. Any linear combination of those (##a x_1^n + b x_2^n + ...##) will also solve the recurrence. You plug in initial values of the sequence to figure out which linear combination you need. You do have to worry about complex solutions. Those end up being sines and cosines.
Or one can consult Wikipedia where they describe the exact same thing and more.
As I understand your terminology, your "positive linear recursion" would be what we would call an "inhomogeneous first order linear recurrence relation".coolul007 said:It seems these are solutions for a particular recursion, what I have supplied is a universal formula for all positive linear recursions.
Linear recursion is a programming technique where a function calls itself repeatedly until a specific condition is met. It involves breaking down a larger problem into smaller sub-problems, and solving each sub-problem until the original problem is solved.
Linear recursion and iteration are both ways to solve problems through repetition, but they differ in their approach. In linear recursion, the function calls itself, while in iteration, a loop is used to repeat a set of instructions. Linear recursion is often more elegant and intuitive, while iteration can be more efficient in terms of time and space complexity.
The base case in linear recursion is the condition that stops the function from calling itself and allows the program to exit the recursive loop. It is the simplest form of the problem that can be solved without further recursion.
Linear recursion can simplify complex problems by breaking them down into smaller, more manageable sub-problems. It also allows for elegant and concise code, making it easier to understand and maintain. Additionally, linear recursion can be used to solve problems that are difficult or impossible to solve using iteration.
Linear recursion is commonly used in computer science and mathematics to solve problems such as searching, sorting, and data structures. It is also used in various fields of science, such as biology and physics, to model patterns and behaviors. Additionally, many programming languages use linear recursion to implement their own internal functions and algorithms.