- #1

coolul007

Gold Member

- 271

- 8

- TL;DR Summary
- I may have reinvented the wheel, here is a pdf on my observations

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- B
- Thread starter coolul007
- Start date

- #1

coolul007

Gold Member

- 271

- 8

- TL;DR Summary
- I may have reinvented the wheel, here is a pdf on my observations

- #2

- 17,591

- 18,096

Looks ok so far (re-opened).Summary::I may have reinvented the wheel, here is a pdf on my observations

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

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:

- #3

coolul007

Gold Member

- 271

- 8

- #4

Svein

Science Advisor

- 2,249

- 773

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

- #5

coolul007

Gold Member

- 271

- 8

There already exists a Benet formula for the Fibonacci numbers.

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)

- #6

jbriggs444

Science Advisor

Homework Helper

- 11,419

- 6,034

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.There already exists a Benet formula for the Fibonacci numbers.

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

It seems these are solutions for a particular recursion, what I have supplied is a universal formula for all positive linear recursions.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.

- #8

jbriggs444

Science Advisor

Homework Helper

- 11,419

- 6,034

As I understand your terminology, your "positive linear recursion" would be what we would call an "inhomogeneous first order linear recurrence relation".It seems these are solutions for a particular recursion, what I have supplied is a universal formula for all positive linear recursions.

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:

Share:

- Last Post

- Replies
- 2

- Views
- 359

- Replies
- 1

- Views
- 332

Insights
Reduction of Order For Recursions

- Last Post

- Replies
- 4

- Views
- 861

- Replies
- 45

- Views
- 1K

- Last Post

- Replies
- 19

- Views
- 806

- Replies
- 18

- Views
- 1K

- Replies
- 1

- Views
- 273

- Last Post

- Replies
- 2

- Views
- 433

- Last Post

- Replies
- 3

- Views
- 439

- Replies
- 8

- Views
- 654