There are problems where we need to find an explicit formula for some recursive sequence such as the Fibonacci sequence, defined by $f_0=0, f_1=1,f_n=f_{n-1}+f_{n-2}$ where we can find $f_n$ in terms of $n$ only, or another example is $a_1=1,a_2=2,a_n=2a_{n-1}+3a_{n-2}$ where we can find $a_n$ in terms of $a_1,a_2,n$. I'm wondering if it is possible to find an explicit function for any given recursive sequence, in terms of at least one term of the set $\{a_1,a_2,...,a_k,n\}$.

  • 1
    $\begingroup$ Are you specifically interested in linear recurrences? If so, then yes. See, e.g., this for the examples you discuss. These methods can be generalized (but the linearity is crucial). $\endgroup$ – lulu Jan 4 '17 at 12:33
  • $\begingroup$ @lulu thanks for the link! $\endgroup$ – user394255 Jan 4 '17 at 12:46
  • $\begingroup$ @lulu thanks for the link as well. I'll probably have a better look at these in the future. $\endgroup$ – Michalis P. Jan 4 '17 at 13:18

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.