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. ...
• 415
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 ...
• 475
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 \...
• 599
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 ...
• 843
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). ...
• 4,038
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
72 views

• 1,212
42 views

Recursive formula does not work as intended

For my cs class Ive been given the following task. I have n different beers, and the i'th beer has a price of p[i]. the prices are: p1 = 2, p[2] = 3, p[3] = 2, p[4] = 1, p[5] = 4. I also have c coins, ...