1
$\begingroup$

While I'm still familiarizing myself with the general picture of combinatorics, and maybe pure math and general; the process of doing so attracts me to (perhaps) smaller parts of it which I find tantalizing to pursue. I don't believe I have yet developed a (completely) stable understanding of discrete mathematics, hence I feel the need to ask for help from the more professional.

While I was trying to contemplate the idea of recursively defined functions, I entertained myself with the following function: $f_0 = 5$ and $f_n = f_{n – 1} + 2$. I soon realized myself being able to try and define the function $f_n$ in terms of $n$ directly. Hence I found that I can follow a general pattern that I can derive consequently: $f_n = f_{n – 2} + 2 + 2$, $f_n = f_{n – 3} + 2 + 2 + 2$, $f_n = f_{n – 4} + 2 + 2 + 2 + 2$.

Judging by the progression of this pattern based or sheer intuition, I generalized the function to be: $f_n = f_0 + 2n$. Therefore, I have defined the function $f$ in terms of $n$ itself. What is the generalization of this method? Just now I intuitively identified the end product of a pattern; how do I do this systematically?

My request is that I would like to learn more about this procedure. I have searched multiple sources using multiple keywords hoping to find the right one, but without guidance I am lost. I have found myself incapable of converting the recursive function into a regular function of $n$ when it came to the Fibonacci function, for example ($f_n = f_{n – 1} + f_{n – 2}$); or how would I go about converting a regural function to a recursively defined one. For example, maybe defining $f_n = 2n + 4$ recursively? Thank you in advance.

$\endgroup$
2
  • $\begingroup$ Not every recursive function is "unfolded" by the same technique. You can use undetermined coefficients (in the same way for differential equations via an ansatz), generating functions, or just tinkering around. $\endgroup$ Dec 18, 2022 at 0:17
  • $\begingroup$ See en.wikipedia.org/wiki/Lucas_sequence $\endgroup$ Dec 18, 2022 at 0:17

1 Answer 1

1
$\begingroup$

You asked

Just now I intuitively identified the end product of a pattern; how do I do this systematically?

but intuition, by definition, can not be systematized. However, over time, mathematicians have worked on specific kinds of recursive functions and found some direct formulas for them as described in the Wikipedia article Recurrence relation.

You also asked

how would I go about converting a regular function to a recursively defined one.

which is a very general question which requires the precise definition of a regular function and recursive function. However, there are algorithms that given sufficiently many function values as a sequence $(a_1,a_2,\dots)$ can find implicit recurrence relations such as, for example, $$0 = -a_{n+2} +a_{n+1} +a_n$$ if such relations exist.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .