# Questions tagged [recursion]

Recursion is the process of repeating items in a self-similar way. A recursive definition (or inductive definition) in mathematical logic and computer science is used to define an object in terms of itself. A recursive definition of a function defines values of a function for some inputs in terms of the values of the same function on other inputs. Please use the tag 'computability' instead for questions about "recursive functions" in computability theory

2,877 questions
Filter by
Sorted by
Tagged with
1 vote
46 views

### Proving that a recursive sequence is bounded and monotone

Let $a_0=2\sqrt3$ and $b_0=3$, and define two sequences recursively by $$a_n=\frac{2a_{n-1}b_{n-1}}{a_{n-1}+b_{n-1}}\quad\text{and}\quad b_n=\sqrt{a_nb_{n-1}}.$$ This is an exercise in Jay Cummings (...
• 21
49 views

• 1,365
84 views

### Getting explicit formula from non-homogenous recursive sequence

I am wondering whether there is an efficient way to find explicit formulas for non-homogenous recursive sequences. While writing out the first few terms and ...
64 views

### Counting "perfect a:b" sequences

I was given this question : a sequence of black and white balls is "$a:b$ perfect" if it starts and ends with a white ball, and in between every $2$ consecutive white balls there are at ...
3k views

### How do we define addition?

I've been trying to learn naive set theory through a YouTube series by 'The Bright Side of Mathematics'. So far, I've been able to understand successor maps and the definition of $\mathbb{N}_{0}$. I ...
78 views

### Number of possible circles with at least two people

I was given this question: In how many possible ways can we arrange $n$ people in circles such that the order between the circles does not matter, but the order ...
212 views

### An alternative way to solve a classic problem of combinatorics

The problem is to count how many permutations in $S_n$ have no fixed points. Let call this number $f(n)$, and define the set $N=\{1,\ldots,n\}$. The 'classic' solution is using the exclusion-inclusion ...
• 65.9k
98 views

### Proving the shortlex ordering is a well-ordering

Let $(A,<)$ be a nonempty linearly ordered set, and let $\operatorname{Seq}(A)$ denote the set of finite sequences of elements of $A$. That is, $f\in\operatorname{Seq}(A)$ is a function $f:n\to A$, ...
• 4,442
103 views

### Transform a recursive sequence to a iterative sequence

Consider the sequence $x_n=\sum_{j=0}^{n-1}y_{n-j}x_j$ with $x_0=1$ and $(y_n)_{n\in\mathbb N\backslash 0}$ is any arbitrary sequence. Show that \begin{align*} x_n=\sum_{j=0}^n a_{nj} \end{align*} ...
• 242
42 views

### What class of function does the recursive function $f_n(x)=(b+ax+x\partial_x)f_{n-1}(x)$ belongs to?

I derived a recursive relationship with respect to a function $$f_n(x)=(b+ax+x\partial_x)f_{n-1}(x)$$ where $$f_0(x)=1$$ The notation here is similar to the generating function of the combinatorics, ...
1 vote
109 views

### Is there a formal algebraic theory for recursive/inductive operators (lookup question: couldn't find after searching)

I'm aware of recursive functions in computer programming. Surprisingly I was having trouble finding similar books and articles on recursive or inductive mathematical structures (that is, in situations ...
• 894
53 views

### How to prove the recursively defined set L' is equal to L?

In the book https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-spring-2015/resources/mit6_042js15_textbook/ Page 199,there is an excercise on recursive sets and structural induction ...
1 vote
99 views

• 99
160 views

### How to justify why succession and addition cannot be circularly defined like this?

I am reading Tao's Analysis I, in which he states: One may be tempted to [define the successor of $n$ as] $n + 1$. . . but this would introduce a circularity in our foundations, since the notion of ...
• 3,029
42 views

• 739