What Are Solutions for Universal Linear Recursions?

[coolul007]

TL;DR Summary

I may have reinvented the wheel, here is a pdf on my observations

https://www.testsite.cocoams.org/linrec.pdf

 

[fresh_42]

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

 

[coolul007]

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.

 

[Svein]

Recursive formulas occur everywhere. Some examples:

• The Fibonacci series: $x_{n+1}=x_{n}+x_{n-1}$
• The Mandelbrot series: $z_{n+1}=z_{n}^{2}+c$ where c is a given constant
• Factorials: n! = n⋅(n-1)!, (n integer >0, 0!=1)
• Square roots: $x_{n+1}=\frac{1}{2}(x_{n}+\frac{a}{x_{n}})$ (for a>0)

Other recursives inlude the Sierpinski curves and the Hilbert curves.

 

[coolul007]

Recursive formulas occur everywhere. Some examples:

• The Fibonacci series: $x_{n+1}=x_{n}+x_{n-1}$
• The Mandelbrot series: $z_{n+1}=z_{n}^{2}+c$ where c is a given constant
• Factorials: n! = n⋅(n-1)!, (n integer >0, 0!=1)
• Square roots: $x_{n+1}=\frac{1}{2}(x_{n}+\frac{a}{x_{n}})$ (for a>0)

Other recursives inlude the Sierpinski curves and the Hilbert curves.

There already exists a Benet formula for the Fibonacci numbers.

 

[jbriggs444]

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.

 

[coolul007]

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.

 

[jbriggs444]

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.