Finding the explicit formula of linear homogeneous recurrence relations.

Question

I'm not sure if this equation is a linear homogeneous recurrence relation because I didn't learn math in english. what is the explicit formula for $f$?

$$f(x) = f(x-2)-{n^{x-1}\over NW-1} f(x-1)+n^{x-1}$$

$n$ and $NW$ are constants. $n = 3$ and $NW = 7000000000 = $7 billion I'm having a hard time because of the $n^{x-1}$ please help me.

Welcome to MSE! You should read this before posting questions — Michael Galuza, Jul 27 '15 at 16:57
Please review and edit your post. Is $m$ supposed to be the same as $n$? What is NW-? is the $*nf(d-1)$ supposed to be in the denominator or numerator? — Ross Millikan, Jul 27 '15 at 16:58
sorry, I didn't know how to use it, and i got many miss spellings. — urw7RSeeh8FR, Jul 27 '15 at 17:12
Is the second term on the right hand side really $-[f(x-1)]^2/(NW-1)$? — Intelligenti pauca, Jul 27 '15 at 18:12

score 0 · Accepted Answer · answered Aug 14 '15 at 12:27

This is a linear second order recurrence with variable coefficients. Just as in the case of differential equations, there are few such recurrences with closed form solutions.

As a first approximation (for smallish $x$) you can disregard the term in $f(x - 1)$, and get a first order linear recurrence (of step two) in $f(x)$:

$$ f(x) - f(x - 2) = n^{x - 1} $$

This has solution:

$$ f(2 x) = f(0) + \sum_{0 \le k \le x} n^{k - 1} = f(0) + \frac{n^{x + 1} - 1}{n (n - 1)} $$

This might be enough for your purposes, or use this as a starting point to construct a closer approximation.

Finding the explicit formula of linear homogeneous recurrence relations.

1 Answers1