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 the functions for some inputs in ...

learn more… | top users | synonyms

1
vote
1answer
93 views

How to argue that a set is recursive or recursively enumerable?

I have the two sets listed below, and I want to argue whether each of them is recursive, recursively enumerable or neither recursive nor recursively enumerable. the set $A = \{ i | ...
2
votes
2answers
120 views

How to define $f(x) = 2x$ as a recursive and lamba function?

How can I exhibit a recursive function and a $\lambda$-term simulating the function $f : \mathbb{N} \rightarrow \mathbb{N}$, such that $f(x) = 2x$? For $\lambda$ part, I thought to create a mult ...
2
votes
2answers
45 views

number of ternary trees: finding a recurrent relationship

If $t_n$ is the number of ternary trees with n nodes, with $t_0=0$, what would be the convenient manner for finding a recurrent relationship for $t_n$? It is given that $t_1=1, t_2=3, t_3=12$. A ...
0
votes
0answers
18 views

Is the maximum value of this recursively defined function bounded?

If we define $$f_1(x)=x^\frac{1}{x}$$ $$f_{n+1}(x)=x^\frac{1}{f_n(x)}$$ Then what is the value of the following $$\lim_{k\to\infty} f_k \left( [f_k^\prime]^{-1}\left( 0\right)\right)$$ where ...
-1
votes
4answers
40 views

Can someone clarify step-by-step how to solve such Recursion & Induction question?

I've a discrete math exam coming up in two weeks and the only thing I've problem with is induction and recursion. I do know how to check the base case of a certain induction i.e. check and compare if ...
2
votes
0answers
43 views

Asymptotics of recursion

suppose we have the following two sequences $$\alpha_k = (k-1)\left(1-\frac {1}{1+(k+1)l}\right) \quad , k \geq 2$$ $$\beta_k = (k-1)\left(1+\frac {1}{1+(k-1)l}\right) \quad , k \geq 2$$ where ...
0
votes
1answer
67 views

How do I find a recurrence relation?

Let n1, n2, . . . , n100 be a sequence of integers. Initially, n1 = 1, n2 = −1 and all the other numbers are 0. After every second, we replace the kth term of the sequence with the sum of the kth and ...
10
votes
2answers
633 views

The set that only contains itself

Ignoring the axiom of regularity (and therefore the implication of "no set can contain itself"), would it be correct to state that the set that contains only itself is unique? My argument is that if ...
0
votes
2answers
92 views

Perplexing integral

First and foremost, is it possible to get the integral you are trying to solve as the solution? I just got the same integral twice. I have also tried MATLAB but it gives the same result. Below is the ...
0
votes
2answers
104 views

Solve the functional equation $f (2x)=f (x)\cos x$

Find all $f: \mathbb R\longrightarrow \mathbb R $ such that $f $ is a continuous function at $0$ and satisfies $$\;\forall \:x \in \mathbb R,\; f\left(2x\right) = f\left(x\right)\cos x $$ My try: ...
0
votes
0answers
37 views

A particular recursion

Given $s_0=2^r>0$ let $s_i=\frac{s_{i-1}}{2^{\log^c{r_{i-1}}}}$ where $c\geq1$ and $r_{i+1}=\log_2(s_{i+1})=r_i-(\log_2(r_{i}))^c\leq r_{i}$. What is the value of smallest $i$ at which $s_i<1$ ...
0
votes
1answer
92 views

Formula to calculate directly $ 1 + 2 \cdot 3 + 3 \cdot 4 \cdot 5 + 4 \cdot 5 \cdot 6 \cdot 7 + \dots + n \cdot (n+1) \cdot \dots \ (2n-1)$

Is it some formula to calculate $$ 1 + 2 \cdot 3 + 3 \cdot 4 \cdot 5 + 4 \cdot 5 \cdot 6 \cdot 7 + \dots + n \cdot (n+1) \cdot \dots \ (2n-1)$$ for a given $n$ without iteration? comes from : ...
0
votes
3answers
2k views

Proof by induction for a recursive function $F(n) = F(n–1)+F(n–2)$

I'm having a lot of trouble with the following homework question: Consider the following recursive function: Base Case: $F(0) = 0,F(1) = 1$. Recursive Step: $F(n)=F(n−1)+F(n−2)$ for all ...
4
votes
2answers
65 views

Mathematically, how does one find the value of the Ackermann function in terms of n for a given m?

Looking at the Wikipedia page, there's the table of values for small function inputs. I understand how the values are calculated by looking at the table, and how it's easy to see that 5,13,29,61,125 ...
1
vote
2answers
49 views

Does an infinite iteration of a function still have my solution and why does it work?

I found the other day that you could find some solutions to an equation in the form $$f[f(x)]=x$$As a matter of fact, I found some solutions to$$f[f(f(\cdots f(x)\cdots))]=x$$ The solution, if one ...
3
votes
1answer
38 views

Prove $A(x,y)= 2[x](y+3)-3$. Where A is the Ackermann-Peter function and [x] is x-th hyperoperator.

I've successfully proven $A(x,y)$ for some fixed x and any y with induction but I'm having a hard time proving this for any x and y. I think the next useful step would be proving $A(x,0)= 2[x]3-3 $ ...
3
votes
1answer
83 views

A little question about convergence of sequence

It's known that: $$\begin{cases}x_n=\sqrt[3]{6+x_{n-1}}\\x_1 = \sqrt[3]{6}\end{cases}$$ $$x_n\to2,\space x_n\uparrow,\space x_n\in(0, 2)$$ $$a_n=\frac{x_n^2+2x_n+4}{12}\space, a_n\to1,\space ...
0
votes
1answer
30 views

being explicit with recursion in a basic proof

related: induction (vs recursion) in proof I want to be explicit with this principle (PCR): Principle of Countable Recursion. Let $T$ be a set, and let $p$ be some map­ping from $\{$finite ...
0
votes
1answer
38 views

Recursive Enumeration of Total Recursive Functions vs Partial Recursive Functions

We have: Primitive Recursive $\subseteq$ Total Recursive Functions $\subseteq$ Partial Recursive Functions There are three points that appear at odds with eachother: 1) The primitive recursive ...
2
votes
2answers
35 views

Find out $n$-th term of monotonic functions increasing and decreasing

I have a series whose max and min values are defined. the values in the series have an increase monotonically by $x\%$ and decrease once the maximum is reached. For example, this series has a min ...
3
votes
7answers
3k views

Find the nth term of a recursive sequence

I have a the following sequence: $$\begin{gather} a_1 = 3 \\ a_{n + 1} = 1 + \frac{a_n}{2} \end{gather} $$ How can I find the $a_n$ term?
0
votes
1answer
40 views

Use geometric progression formula to expand generating function into a power series?

I am a software engineer and I am studying combinatorics on my own to enhance my learning. I have been finally starting to get the hang of generating functions, but the following problem below has me ...
0
votes
1answer
29 views

Recursive Definition

Consider the following informal definition for a function calc(x,y) = (0*y) + (1*y) + … + (x*y) For example, we have that calc(2,5) = (0*5) + (1*5) + (2*5) Give a recursive definition for the ...
2
votes
2answers
148 views

Computationally finding roots of a recursive function

I'm having a pretty complex function $h(n,d) = f(n,d) -n$ where $n \in \mathbb{N}$ and $d \in [1,9] \subset \Bbb{R}$. $f(n,d)$ is recursively defined. $$f(n, d) = \begin{cases} n<0\quad f(|n|,d) ...
0
votes
0answers
22 views

Recursive formula for an integral involving multiple inner products

Motivation: I am trying to form a Bayesian model where I will be performing frequent state-updates. I am seeking to find a recursive formula for a certain quantity that will enable me to perform this ...
0
votes
2answers
34 views

Finding Recursive Definition for the following:

How would i start off to find a recursive definition for $X_{0}$=.19 $X_{1}$=.1919 $X_{2}$=.191919 ... $X_{n+1}$= what goes here?
2
votes
2answers
37 views

How to use recurrence to define generating function? How to write generating function as power series?

I am a software engineer teaching myself combinatorics. This problem is destroying me, but I am following what I thought was the appropriate strategy to solve a recurrence. I am also confused as to ...
3
votes
1answer
85 views

What lies between primitive recursion and total recursion?

My understanding is that there are total recursive functions that are not primitive recursive, such as the Ackermann function. What classes of functions (or sets) lie between primitive recursion and ...
0
votes
4answers
46 views

Finding the $S_n$ of a recursion

$$\sum_{k=0}^{n} (1+2k+4(k(k+1)))=?$$ In order to find the $S_n$ what methods are best fitted for such problem? Is it possible to use the lemma $\sum_{i=0}^{n} i= {n(n+1)}/2$ and plug in? I tried but ...
2
votes
1answer
18 views

How to prove the recurrence relation for this generating function problem?

I am a software engineer and I am learning combinatorics theory on my own. I recently got stumped by the following problem. Problem Let $a_{0} = 2$ where $a_{n} = 3a_{n-1} - 2$ with $n>0$. ...
2
votes
3answers
57 views

Finding the sum of n terms $S_n$ starting from sigma $k=0$

$$\sum_{k=0}^{n} ((4k-3)\cdot 2^k)+4=(2^{n+3}+4)n-7\cdot2^{n+1}+15$$ How? I've tried everything but i don't see it. Any equivalent solutions are also welcome, thanks.
0
votes
2answers
84 views

Finding the nth term of 1, 6, 24, 76,212,…

What different methods of recursion can I use to find the nth term of this recursion? This should be simple but I don't know what I'm missing. Could you demonstrate the method? $n(0)= 1$, $n(1)= 6$, ...
0
votes
2answers
35 views

Solving recurrence using recurrence trees.

I have a recurrence which I know has the solution $O(\lg n)$, it looks like this: $$T(n) = T(\sqrt n) + \lg n$$ If I understand correctly, the recurrence tree method involves looking for the term ...
0
votes
1answer
21 views

Proving recursive formula is an integer

This seems like a trivial question, but I can't seem to wrap my head around the proof using induction. Prove: $a_n=2a_{n-1}+a_{n-2}$, with initial condition $a_0=1$ and $a_1=1$, is an integer for $n ...
1
vote
1answer
20 views

Using rsolve in Maple

I have tried using rsolve in Maple to obtain a recursion formula from an ordinary differential equation with summations. I get Is there some reason for Maple ...
0
votes
1answer
25 views

Recursive writing involving arithmetic progression

I've been trying to figure out this recursion problem but I'm getting stuck trying to find the nth-term sequence for the last recursion. I found one but the second i'm so clueless about. I don't know ...
0
votes
2answers
25 views

How do you formulate an equation that require its own result to replace one of its unknown?

Is the concept of recursion used in Mathematics as it is in computer science? How would you express it in a formula?
0
votes
1answer
42 views

What is the basin of attraction for the attracting fixed point $x_-$ of $f(x) = x^2+c$

Attempt: If $x_-^2+c=x_-$ then $x_-=\dfrac{1-\sqrt{1-4c}}{2}$ which is attracting for $|f(x)|<1$ i.e $-2<c<\dfrac14$. How do I find the set of points $x$ such that the orbit $f^n(x) \to x_-$ ...
-1
votes
1answer
43 views

Time Complexity

Prepping for an exam and wondering whether I correctly calculated the time complexity. Function is given as: $function XYZ(n:integer)\\ begin for\ i:=1 \ do \ 2*n^2 \ do;\\ ...
0
votes
1answer
20 views

Giving recursive definition

I need to give the recursive function of $3n^2$. I'm pretty sure the base case needs to be $3 \cdot 0^2 = 0$, but I don't know where to go from there. Any help is appreciated.
1
vote
1answer
159 views

Determining the effective tax rate in a tax on tax situation

There are taxation situations where the taxable amount includes the tax calculated on the taxable amount (e.g. this is a recursive calculation, as follows)... ...
2
votes
0answers
48 views

Almost sure convergence of a martingale

I just learned martingales (with no depth) and I am working on the following question. Suppose $S_n$ is a a random walk on the integers and at each step, it increases by 1 with probability $p$ or ...
0
votes
1answer
23 views

Factorial Series Written As Recursive Definition

I have a factorial series as shown below: \begin{equation} (2n+1)!~\text{for all $n \geq 0$} \end{equation} And I would like to know if the recursive definition that I wrote is accurate: ...
1
vote
1answer
22 views

Recursive Definition of a Series

I have a series such as the one below: \begin{equation} 2^n(\sum\limits_{i=2}^{n+1}i)\text{ for all $n \geq 1$} \end{equation} I need to write a recursive definition for it. Here's what I have so ...
4
votes
0answers
67 views

Distribution of $\max_{n \ge 0} S_n$, random walk.

Say I have a random walk that's a nearest neighbor random walk on the integers where at each step the probability of moving one step to the right is $p$ and the probability of moving one step to the ...
7
votes
1answer
189 views

Compute a probability in Random Walk by Martingales

Let $X_n$ be the state at time $n$ of a Markov chain with these transition probabilities : $$p_{i,i+1}=p_i\qquad,\qquad p_{i,i-1}=q_i=1-p_i$$ $(a)$ Show that $Z_n=g(X_n)\,;\,n\geq0$, is a ...
1
vote
2answers
44 views

Proof concerning Fibonacci and recursively defined sequences

The series $(a_n)_{n\in\mathbb{N}}$ is given through $$a_1=1,\quad a_2=\frac{1}{2},\quad a_{n+2}=a_na_{n+1} \quad\text{ for } n\geq1.$$ I want to show that $$a_n = 2^{-f_{n-1}}$$ whereas ...
0
votes
4answers
52 views

Find the general formula for the sequences

1=1 2+3+4+=1+8 5+6+7+8+9=8+27 10+11+12+13+14+15+16=27+64 Find the formula is suggested by these equations?Prove your answer is correct. I saw this question on practice exam and ...
1
vote
1answer
28 views

How to give a recursive definition and a direct formula and prove that they both are equivalent.

How to give a recursive definition and a direct formula and prove that they both are equivalent. for example, 10,13,16,19,22,25 I know the formula for this is a,a+d,a+2d,a+3d,... ...
0
votes
1answer
29 views

given $n$ stairs, how many number of ways can you climb either step up one stair or hop up two?

this is the question given $n$ stairs, how many number of ways can you climb either step up one stair or hop up two? I need to include the number of ways for $n=1$ through $6$ as well. My ...