Solving Non-Linear Recurrence Relation?

[FeDeX_LaTeX]

Hello;

I do not have any experience in solving non-linear recurrence relations, so I was just wondering how one solves them.

For example, consider the sequence: 1, 2, 6, 15, 31, 56

In general, $$F_{n+1} = F_{n} + n^{2}$$

Do I still substitute $$F_{n} = k^{n}$$?

Thanks.

 

[CRGreathouse]

First transform into a homogeneous linear recurrence relation. In your case, a(n) = 4a(n-1) - 6a(n-2) + 4a(n-3) - a(n-4).

 

[FeDeX_LaTeX]

Hello;

Thanks for the reply. How did you transform it into a homogeneous linear recurrence relation? Did you use trial and error, or is there a method to do this (or is there something obvious I'm missing here)? Can all non-linear recurrence relations be transformed into homogeneous linear recurrence relations?

 

[Petr Mugver]

Hello;

I do not have any experience in solving non-linear recurrence relations, so I was just wondering how one solves them.

For example, consider the sequence: 1, 2, 6, 15, 31, 56

In general, $$F_{n+1} = F_{n} + n^{2}$$

Do I still substitute $$F_{n} = k^{n}$$?

Thanks.

Introduce the operator R that retards sequences:

$$R(f_n)=f_{n-1}$$

then you can express you equation as

$$(R-1)f_n=(n-1)^2$$

Multiply this by (R-1)^3 from the left, you'll get

$$(R-1)^4f_n=0$$

(check it...)

This last equation is linear and is of fourth order, the solutions depends on 4 arbitrary constants. 3 of then can be eliminated by substitution into the original equation.

 

[CellCoree]

Hello,

Thank you for your question. Solving non-linear recurrence relations can be a challenging task, but there are methods and techniques that can help us find the solution. One approach is to use the characteristic equation method, where we transform the recurrence relation into a polynomial equation and solve for its roots. Another method is to use generating functions, which can help us find a closed-form expression for the sequence. As for your specific example, substituting F_{n} = k^{n} may not always work, but it is a good starting point. I recommend doing some research and practicing with different examples to get a better understanding of how to solve non-linear recurrence relations. Best of luck!