0
$\begingroup$

Consider a series of integers $a$ defined by:

$$\begin{cases} a_n & = c_n & \text{if $0 \le n \le 2$} \\ a_{2n} & = f(a_n, a_{n+1}) & \text{if $n > 1$} \quad \text{(even $n$)} \\ a_{2n+1} & = g(a_{n-1}, a_n) & \text{if $n \ge 1$} \quad \text{(odd $n$)} \end{cases}$$

where $c_0, c_1, c_2$ are constants. The subscript of the second and third cases is meant to convey multiplication (e.g. for $n=5,\enspace a_{10} = f(a_4, a_5)$).

It seems very similar to a recurrence relation, as latter terms are defined as a function of previous terms, except for the fact that the series isn't defined sequentially.

Note that for $a_6$ depends on terms $a_3$ and $a_4$ -- 3 and 2 terms "away", respectively -- while $a_{100}$ depends on terms $a_{50}$ and $a_{51}$.

Is this still a recurrence relation? If not (or if so, I suppose) is there a better name for this construction so I can get more information on how to approach generalizing it (i.e. calculating an arbitrary term without needing to generate the entire sequence).

Thanks in advance.

$\endgroup$
  • $\begingroup$ It's a recurrence relation. $\endgroup$ – Will Fisher Jul 24 '16 at 17:57
  • 1
    $\begingroup$ Also no, there is no general method for solving recurrence relations. Many of them can't be solved with today's methods. $\endgroup$ – Will Fisher Jul 24 '16 at 17:58
  • $\begingroup$ ... but a recurrence with such a structure gives an efficient way for computing Fibonacci or Lucas numbers, for instance. $\endgroup$ – Jack D'Aurizio Jul 24 '16 at 17:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.