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.