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.