Recursive definitions and clauses

Question

When a recursive step is applied to an arbitrary set, is it acceptable to state that the resulting set after recursive application never remains the same as the previous given set, i.e. back-loop never exists during any recursion step? If it exists, could you provide a counterexample for that?

Example: If we define $a_{n} = n$, with base case $a_{1} = 1$, then our sequence will generate infinitely many large numbers with no back-going step. Is there any possibility where new $a_{i}$'s will go back to previous sets?

Note: Questions asks on whether recursive calls does indeed generate new objects, or it can be same as with previous one?

What you ask completely depends on the sequence you study (referring to your sequence example). — mathcounterexamples.net, Oct 26 '20 at 19:55
I mean, if we define $a_{n} = a_{n-1}$ for each $n \geq 1$, is it acceptable to say that resulting set remains the same as the previous one? — BlizzardWalker, Oct 26 '20 at 19:57
I think that you are confusing a sequence with its range. See my answer below. — mathcounterexamples.net, Oct 26 '20 at 20:05

score 1 · Accepted Answer · answered Oct 26 '20 at 20:05

I think that you are confusing a sequence and its range. What you call the resulting set is the range.

For a sequence $\{a_n\}$, its range is $$\{a_n \mid n \in \mathbb N\}.$$

For example, the range of a constant sequence is a set with a unique element.

The range of the first $N$ elements of a sequence is

$$r_N=\{ a_n \mid 1 \le n \le N\}$$

$r_N$ can be a set with much less elements than $N$.

score 1 · Answer 2 · answered Oct 26 '20 at 20:05

1

Given a function $f:\mathbb{N}\to \mathbb{N}\,$ defined by $\,f(x) = 2.\,$ Define the recursive sequence $\,a_1 = 1,\, a_{n+1} = f(a_n).\,$ Then $\,a_n = 2\,$ for all $\,n>1.$ Thus, the sequence loops back to $2$.

answered Oct 26 '20 at 20:05

Somos

35,251
3
30
76

Recursive definitions and clauses

2 Answers2