# 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,553 questions
Filter by
Sorted by
Tagged with
31 views

### How to prove the following statement regarding the successor function and addition of natural numbers?

Natural numbers (including 0) and the successor function are defined as per the Peano Axioms (you can check them on wikipedia). Addition is defined recursively as follows: $a+0=a$ $a+S(b)=S(a)+b$ With ...
365 views

### Proving a recursive formula is indeed a function

Recently, I have been studying induction proofs, because I wanted to learn about all kinds of different proof techniques. However, I have been stuck now on this particular exercise for a while now. ...
95 views

### An interesting recurrent equality, possibly easier to solve in its differential form?

I encountered an interesting inequality that I'm not sure how to approach. Here $c$ is a positive constant. $$f(n+1) - f(n) = c f(n)\sum_{m=0}^n f(m)$$ I am not familiar with techniques to solve ...
16 views

### Why does not the second recursion theorem guarantee a lest fixed point?

What does it mean that the first recursion theorem guaranties the existence of the lest fixed point, but the second one does not? If there is at least one (pseudo) fixed point then there must be a ...
27 views

### Trouble understanding a simple exercise about primitive recursion on natural number set theory.

Consider the function $f: \omega \rightarrow P\omega$ defined recursively through: \begin{equation*} \omega \in P\omega \quad \text{and} \quad h : \omega \times P\omega, (n,A) \rightarrow \{n^+ + k \...
137 views

### Possible positions of the knight after moving $n$ steps in Chessboard.

Problem There is a knight on an infinite chessboard. After moving one step, there are $8$ possible positions, and after moving two steps, there are $33$ possible positions. The possible position after ...
79 views
+50

### How do you prove the existence of the addition function without pre-supposing it?

Context: self-study from Smullyan and Fitting's Set Theory and the Continuum Problem (revised ed., 2010). So I have this question, which is exercise 8.4 (a) in Chapter 3 (page 44 of Dover edition). ...
1 vote
29 views

1 vote
14 views

### Analytical expression for tetrahedral progression

During my engineering studies we did get some Calculus and Algebra background, but I have a lack of knowledge in other topics such as Combinatorics, Recurrences and Progressions. Therefore I would ...
37 views

### Finding sequence [closed]

I'm looking for the pattern of this series -> $1, 2, 1, 2, 1, 2$. Any help would be appreciated. $S_k = 2/S_{k-1}, k \in \mathbb{Z}, k \ge 2, S_1 = 1.$
71 views

### Is this formula stable? $\frac{|x|-|y|}{x-y}$ as $x$ approaches $y$.

I want to analyze the stability of this formula $\frac{|x|-|y|}{x-y}$ as $x$ approaches $y$. But this formula is not a recursion! I used to analyze the stability of recursion by computing the first n ...
1 vote
17 views

1 vote