Mathematics Stack Exchange
Mathematics Stack Exchange

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

Recursion is the process of repeating items in a self-similar way. The most common application of recursion is in mathematics and computer science, in which it refers to a method of defining functions in which the function being defined is applied within its own definition.

Basically, a class of objects exhibiting recursive behaviour can be characterised by two features:

  • There must be a base criterion for which the function should not call itself.

  • Every other iteration of the function should move it closer to the base condition.

2829 questions
3
votes
3 answers

Finding the Closed Form of a Recursion

I wanted to find the closed form of the recursion: $$a_n = \frac{1}{n+1} + \frac{n-1}{n+1} a_{n-1}$$ where $a_0 = 0$. So far, my progress has been to multiply both sides by $\frac{n(n+1)}{2}$ which gives $$\frac{n(n+1)}{2} a_n = \frac{n}{2} +…
theGrind24
  • 119
3
votes
0 answers

Prove in a typical equation method, that $f(n)=n-\sqrt{n}+1 $ is the result of $f(n)$

A function $f(n)$ is defined for $n=4^k$, $k\geq0$. $f(n)$ is given in a recursion format: $$ f(n)= \begin{cases} &3f(\frac{n}{4})-2f(\frac{n}{16})+\frac{3}{8}n,\quad n\geq160 \\ &1,\quad n=1 \\ &3,\quad n=4 \end{cases} $$ I need to prove in a…
user12499410
  • 183
3
votes
4 answers

Iterative recurrence.. Iteration method

Here is the Equation and how far I got into solving this problem using the iteration method: $$T(1) = 8 \\ T(n) = 3T(n-1) - 15$$ Iterations: $i=1, $ $$T(n) = 3(3T(n-2) - 15) -15$$ $i=2, $ $$ 3(3(3T(n-3) - 15) -15) - 15$$ $i=3,$ $$3(3(3(3T(n-4) -…
Alice
  • 31
  • 1
  • 2
3
votes
1 answer

Proving a primitive recursive function

I'm asked to find a primitive recursive formula the function: $$ f: N × N → N, f(n, k) = {n \choose k} $$ My attempt: I know that ‏‏‎ $$ {n \choose k} = \frac{n!}{k! (n-k)!} $$ and so a primitive recursive function $$ g(n, k) $$ would be:…
Monika
  • 585
3
votes
1 answer

Proving the General Recursion Theorem

I want to prove the following version of the Recursion Theorem Let $S$ be a nonempty set and let $S^{*}=\bigcup_{n=1}^{\infty}S^{n}$. Let $s\in S$ and let $f:S^{*}\rightarrow S$ be a function. Then there exists a unique function…
Eigenfield
  • 1,532
3
votes
1 answer

Solving a recurrence where $a_{n} =a_{n-1} +\lfloor {\sqrt {a_{n-1}}}\rfloor$

Given $a_0 = 1$ $a_n = a_{n-1} + \lfloor{\sqrt{a_{n-1}}}\rfloor$ ; for $n > 0$ I need to find the solution of this recursion. The only thing I have noticed is that when $a_n$ is equal to or just greater than a perfect square say $x^2$ the…
Andariel
  • 159
3
votes
1 answer

Example of a r.e. equivalence relation but not recursive

I am looking for an example of an equivalence relation which is recursively enumerable but not recursive. I found the following statement: If R is an equivalence relation r.e. which is not recursive. Then for each $n$ there are infinitely many…
user350168
  • 393
3
votes
3 answers

How to solve recursive equations $F_{n+1} = F_{n} \cdot g + h$

Sorry if this is a duplicate or easy (a lot of the other 'how do i solve recursive equation' questions were for more complex equations). How can I solve this for arbitrary $F_n$ with arbitrary constants $c_1$ and $c_2$. $$F_{n+1} = F_{n} \cdot c_1 +…
Letseatlunch
  • 839
3
votes
1 answer

Minimum number of leaves in balanced binary tree

A balanced binary tree is a binary tree for which the difference in height between any node's two sub-trees is at most 1. (Such a tree is known as an AVL tree.) What is the minimum number of leaves in such a tree of height $h$? My thinking is…
josh
  • 35
3
votes
0 answers

Recursion asymptotic growth function proof of complexity

I have the following recursive function(an example from a textbook): $$ T(n)=\begin{cases}1&n=1\\T(\lfloor\tfrac n2\rfloor)+T(\lceil\tfrac n2\rceil)+1&n>1\end{cases} $$ A recursion is used in order to prove that $T(n) = O(n)$ The hypothesis is: for…
ThunderWiring
  • 141
3
votes
3 answers

How to explain recursion and iteration?

How to explain recursion and iteration to someone without using formulas or single line of code? Difference betwen them, why to use one over another? (a.k.a : How to explain recursion and iteration to my grandmother) (a.k.a : How to explain…
malakrsnaslava
  • 131
3
votes
1 answer

How to solve a recursively defined system

It has been a while since I have tackled a problem like this and could use a refresher. I have a recursive system of equations that looks a little like: $$x_{n}\left(\frac{1}{2}\right)+y_{n}\left(\frac{1}{4}\right)=x_{n+1}…
LOw
  • 33
2
votes
2 answers

Recursive Equation.

We have a recursive function: $$a_n = Aa_{n-1} + Ba_{n-2} $$ We assume that $ x ^ n = a_n $. From this equality quadratic equation we have two solutions $$ \alpha, \beta, \qquad\alpha \neq \beta $$ In that case: $ \alpha ^{n-1} = a_{n-1} \vee…
user180834
  • 1,453
2
votes
0 answers

A Problem about Recursion

Consider recursion $$a_n+c_1a_{n-1}+\cdots+c_ma_{n-m}=0~~~~~~~~~~(1)$$ Let $\lambda^m+c_1\lambda^{m-1}+\cdots+c_m=0$ be the characteristic function and $(\lambda_1,n_1),\cdots,(\lambda_s,n_s)$ be its solutions (the $\lambda_i$ are the roots with…
gaoxinge
  • 4,434
2
votes
3 answers

Use a recursion tree to determine a good asymptotic upper bound for the function $T(n) = 2T(n−2)+1$

I'm trying to schematize this type of exercise : Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n) = 2T(n−2)+1$. To do this I made this table : $$\begin{array}{c|c|} & \text{Levels} & \text{Dimension} &…
emacos
  • 249
1
2
3
…
12 13