Linear Recursion -- A look

  • B
  • Thread starter coolul007
  • Start date

Answers and Replies

  • #2
15,552
13,660
Summary:: I may have reinvented the wheel, here is a pdf on my observations

https://www.testsite.cocoams.org/linrec.pdf
Looks ok so far (re-opened).

You could try to prove why your closed formulas are correct, consider why there are repetitions in other number systems to a different basis, or what happens if ##a\in \mathbb{R}.##
 
Last edited:
  • Like
Likes pbuk and berkeman
  • #3
coolul007
Gold Member
271
8
I haven't got a clue how to prove my formulas, they are correct. My aha moment was seeing the rep digits in the different bases. As for the reals, I'm a positive integer kind of guy. I also looked to see if there was anything that may be useful for the 3N+1 conjecture. So far nothing. Thank you for your comments.
 
  • #4
Svein
Science Advisor
Insights Author
2,189
726
Recursive formulas occur everywhere. Some examples:
  • 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)
Other recursives inlude the Sierpinski curves and the Hilbert curves.
 
  • #5
coolul007
Gold Member
271
8
Recursive formulas occur everywhere. Some examples:
  • 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)
Other recursives inlude the Sierpinski curves and the Hilbert curves.
There already exists a Benet formula for the Fibonacci numbers.
 
  • #6
jbriggs444
Science Advisor
Homework Helper
10,241
4,860
There already exists a Benet formula for the Fibonacci numbers.
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.
 
  • #7
coolul007
Gold Member
271
8
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.
It seems these are solutions for a particular recursion, what I have supplied is a universal formula for all positive linear recursions.
 
  • #8
jbriggs444
Science Advisor
Homework Helper
10,241
4,860
It seems these are solutions for a particular recursion, what I have supplied is a universal formula for all positive linear recursions.
As I understand your terminology, your "positive linear recursion" would be what we would call an "inhomogeneous first order linear recurrence relation".

It is "inhomogeneous" because of the constant term.
It is "linear" because the contribution from prior terms is a fixed multiple of the terms. Not of their squares or anything fancier.
It is "first order" because it only goes back one term.

As I recall from many years ago (it's been about 40 years now since I studied these), the first move you make when attacking an inhomogeneous recurrence is to make it homogeneous with a change of variables. You can then solve the homogeneous recurrence and change variables back.

The same Wiki article I linked to above covers inhomogenous linear recurrence relations as well. It uses a different technique from the one that I recall.

https://en.wikipedia.org/wiki/Recur...currence_relations_with_constant_coefficients

Fibonacci is an example of a second order homogenous linear recurrence relation. It goes back two terms and has no constant term.
 
Last edited:

Related Threads on Linear Recursion -- A look

  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
12
Views
3K
  • Last Post
Replies
3
Views
2K
Replies
1
Views
1K
Replies
7
Views
2K
Replies
5
Views
1K
Replies
1
Views
12K
Replies
2
Views
947
Replies
1
Views
1K
Top