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

0
votes
0answers
7 views

How to solve a nonlinear recursion relation?

Given the following recursion relation \begin{equation} E^{(n)}=(E^{(n-1)}-\alpha_1)\,e^{-\alpha_2\,(\alpha_3E^{(n-1)}+b)} \end{equation} where $\alpha_i$'s and $b$ are some constants. I am trying ...
1
vote
2answers
37 views

Recurrence to find P(n). P(n) is the number of ways to decorate a strip of size n with tiles.

There are three kind of tile. One is of size 1. Second is of size 2 of green color. Third is of size 2 with blue color. These are the values I found but I can not figure out the formula. P1 1 p2 3 p3 ...
0
votes
0answers
19 views

Are these functions computable - Understanding computable functions

There is a theorem in computability theory which states: B.Cooper: If $A\subseteq N$ is computable, then $A$ is also computably enumerable. In the proof of this theorem -which is an ...
2
votes
3answers
44 views

Recursion Proof by Induction

Given: f(1) = 2 f(n) = f(n-1) + 3, for all n>1 It can be evaluated to: ...
1
vote
1answer
24 views

What is the slowest growing function that is total but not primitive recursive?

For what I have in mind is the Ackermann-Buck function. If there isn't a slowest growing function do you have examples of other function slower growing than Ackermann-Buck's function?
3
votes
1answer
121 views

Is there some kind of deep relationship between substitution and recursion?

Define $\mathbb{N}$ as the initial object in the following category: Objects. Sets $X$ equipped with a function $S : X \rightarrow X$ and an element $0:X$. Morphisms. Functions that preserves ...
0
votes
1answer
19 views

A Question About Recursive Functions

We want to find a recursive function $f(x,y)$ in order to have this equality: $$ \mathbf \varphi_{f(x,y)} = \varphi_x + \varphi_y$$ I know we should use "s-m-n" theorem, but I can't find the ...
0
votes
2answers
28 views

Finding Recursive formula for value of a game

I understand the value of the game changes depending on what pile I take the coin from. If I take a coin from the front, I get $i+1$ coins (if I take $i = 1$, now $i =2$). This happens until $i = j$ ...
0
votes
0answers
17 views

Ordinals defined by successor and union

Let $M$ be the smallest set of ordinals satisfying $0\in M$ $x\in M\implies x+1\in M$ $S\subseteq M\implies \bigcup S\in M$ What does $M$ look like? Is it all ordinals? Is it all countable ...
1
vote
1answer
74 views

Recursive calculation - How would it be started?

First off, let me assure you that this is my very last resource. I have tried everything, because I understand that posting a question that needs a hyperlink to be understood is annoying. But I would ...
0
votes
0answers
58 views

How to find the first 5 values of a recursive relation where certain sequences are not known?

Write down the first five values of each of the following recursive sequences. (a) r(0) = 2, r(n) = [r(n-1)] -n -1 for all integers n>=1 (I couldn't write the values as ace of r and s so I just wrote ...
0
votes
1answer
50 views

Find a Recursion Formula with boundary conditions

A game is played as follows. Coins with value $x_1, . . . , x_n$ are laid on a table in a row. Two players alternate turns taking a coin from either end of what’s left of the row of coins until the ...
0
votes
1answer
38 views

Valuing a game using recursion

An urn contains 4 marbles: 2 red and 2 green. You extract them one by one without replacement. If you extract a green marble, I pay you 1 dollar; if you extract a red marble, you pay me $1.25. You can ...
0
votes
0answers
23 views

Solving a recurrence relation using a subtitution method $T(n+1)=T(\frac {n} {2} )+ \Theta\left(n^2 \right) $

I got stuck when I want to solve this recursive relations by substitution $$ T(n+1)=T(\frac {n} {2} )+ \Theta\left(n^2 \right) . $$ $$ T(n+1)=2 T(\frac {n} {2} )+ \Theta\left(n\right) . $$ $$ ...
0
votes
0answers
25 views

Finding a shorter recursive equation

The assignment is the following: (a) Given a sequence $(a_n)_n$ which satisfies the recursive equation $a_n = \sum\limits_{k = 1}^d c_k \cdot a_{n-k}$ with $c_d \not= 0$. Furthermore $Q = 1 - c_1t - ...
0
votes
0answers
14 views

Nature of state - recursion?

I always wondered how mathematicians define state (or rather: where it comes from?). This is tricky, because I always thought that in math there is only one "thing" - a pure, stateless function. Few ...
1
vote
1answer
46 views

How to generate (recursively?) all non-isomorphic trees with 2 types of vertex labels with degree restrictions?

I am not sure if the title makes a whole lot of sense, but what I am trying to do is generate all non-isomorphic trees that obey the following: 1) Each vertex (including leaves) has one of two labels ...
0
votes
1answer
20 views

How to find the function that is computed from a recursive algorithm? [closed]

The following is a recursive algorithm : Procedure unknown(n belongs to N) If n=0 then return 0 else return unknown (n-1)+5 The function that is computed from ...
0
votes
1answer
586 views

Maximize profit with dynamic programming

I have 3 tables… $$\begin{array}{rrr} \text{quantity} & \text{expense} & \text{profit}\\ \hline 0 & 0 & 0 \\ 1 & 100 & 200 \\ 2 & 200 & 450 \\ 3 & 300 & 700 ...
2
votes
2answers
160 views

Understanding the step-hop problem mathematically

I am working on a problem where one is given n number of steps. They can take either one, two, or three steps. How many number different possible ways are there to climb the n steps? I can solve this ...
0
votes
2answers
223 views

Solving the Recurrence Relation/Series fn = 1 + fn-1*(M) where M is a constant

So I'm trying to solve this week's FiveThirtyEight Riddler. In a building’s lobby, some number (N) of people get on an elevator that goes to some number (M) of floors. There may be more people ...
0
votes
1answer
26 views

primitive recursive conditional

I am confronted with the assertion that the following expression describes the conditional: $\text{Cond}\left[ t, f, g \right] = \text{Pr} \left[pr^2_1, pr^4_2 \right] \circ(f,g,t)$. This is meant ...
1
vote
2answers
129 views

Proof of x-intersection of the Mandelbrot Set?

I'm trying to prove that the Mandelbrot set intersects the X-axis on the interval [-2,.25]. I understand and have proven that the Mandelbrot set lies in a radius of 2. Mostly, I'm wondering how to ...
0
votes
0answers
6 views

Time complexity for recursion

For, this recursion, What's the time complexity? T(n) = 3T(n/2) + O(log n) I think I can't use the master's theorem because a = 3, b = 2 then log2(3) = 1.58 and f(n) = n^0*log(n), so c = 0 and it ...
4
votes
1answer
64 views

Prove that for $k>1$ $a_n$ is a perfect square

I'm having problems with this exercise. Let $k > 1$ be an integer. We define $(a_n)_{n \in \Bbb N_0}$ as: $$a_0 = 1$$ $$a_1 = 1$$ $$a_{n+2} = (k^2-2)a_{n+1}-a_n-2(k-2)$$ Prove that $\forall n \in ...
0
votes
1answer
18 views

Midpoints of a recursively subdivided square

I have a rectangle that I recursively subdivide along the horizontal and vertical axis in successiv order. The sides of the rectangle are both equal to one so the original midpoint is (x, y) = (0.5, ...
0
votes
0answers
14 views

Recurrence relation without master's theorem

$$T(n) = T(n/2) + O(n \log n).$$ I don't think I can use master's theorem because $a = 1$, $b = 1$ then $\log b a$ is $log_2(1) = 0$. And $f(n) = n\log(n)$, so $c = 1$. Then $c \ne 0$. So second form ...
1
vote
4answers
51 views

Mathematical Notation of Sequence of Functions

Let's say I have a finite set of functions $F=\{f_1,f_2,f_3,...,f_n\}$ and I want to show a recursive function that is constructed by an arbitrary sequence of applications of functions in $F$ to input ...
0
votes
4answers
68 views

Power series solution (Why the constant of the recurrence relation can be chosen arbitrarily?)

Please help me understand this: Solve $(x+1)y''-(2-x)y'+y =0$ First, since $x_0=0$ is an ordinary point, it can be guaranteed that we can find two independent power series solutions centered at ...
2
votes
1answer
32 views

Enumerating the primitive recursive functions without repetition

According to this paper (and this one), it is possible to enumerate the primitive recursive functions without duplication, even though equality of primitive recursive functions is not decidable. I am ...
10
votes
1answer
319 views

Limit of recursive sequence $n^2q_n=1+(n-1)^2q_{n-1}+2(n-2)q_{n-2}$

When looking at this riddle, I came across the following sequence for the frequency of sampled integers between 1 and $n$ in a without replacement/without neighbour sampling: $$q_1=1,\quad ...
0
votes
2answers
26 views

Solving inequality with a recursive formula without its closed form?

I have the following problem: $$a_{1}=1$$ $$a_{2}=3$$ $$a_{n+2}=a_{n+1}+5a_{n}$$ I have to prove this inequality: $$a_{n}<1+3^{n-1}$$ So my question, is there a way to solve this inequality without ...
0
votes
1answer
36 views

Is there a general approach to find an explicit formula to a recursive sequence?

I've been doing a bunch of exercises where I need to find the explicit formula for a given sequence... $$a_{n+2} = 6 a_{n+1} - 9 a_{n}$$ The first were easy with $a_{0} = 1$ and $a_{1} = 3$ i.e.. But ...
1
vote
1answer
48 views

Solving a Recurrence Relationship

Given recurrence relationship: $g(1) = 5;\\ g(2n) = 4g(n);\\ g(2n+1) = 4g(n).$ I feel lost because of $g(2n)$ and $g(2n+1)$. Based on my coursebook, there is the common standard form, which can be ...
0
votes
2answers
26 views

Recurrence relations with multiplication

I have a recurrence relation and I am not quite sure if I am solving it correctly. The relation is this: $$t_n = 2n~t_{n-1}$$ where $t_0 = 1$ Here is how I went about solving this: First step is to ...
0
votes
0answers
37 views

Recurrence Relation; unusual exercise (For me at least)

I'm having some trouble with this reccurence problem. Usually we have just one term like $2^n$ or $3n$, but this time there one of each kind. $$\begin{align} a_{n}=5a_{n-1} - 6a_{n-2} + 2^n + 3n ...
0
votes
1answer
46 views

Solve $T(n)=16T(n/2)+2n^4$

Solve using the iteration method: $$T(n)=16T(n/2)+2n^4$$ My attempt: $$\begin{align} T(n) &=16\cdot16T(n/2^2)+2(n/2)^4+2n^4 \\ &=16\cdot16\cdot 16T(n/2^3)+2(n/2^2)+2(n/2)^4+2n^4\\ ...
0
votes
0answers
20 views

Help with a proof of the computability of the monus function by recursion

Reading a text on computability by a guy called Cutland, and he basically asserts the following, which is suppose to be a proof by recursion that x ∸ 1 is a computable function: (1) 0 ∸ 1 = 0 (2) ...
1
vote
2answers
26 views

Solve the recursion $p_n = p \cdot(1 - p_{n-1}) + (1-p)p_{n-1}$

Solve the recursion $p_n = p \cdot(1 - p_{n-1}) + (1-p)p_{n-1}$ $p_n = p \cdot(1 - p_{n-1}) + (1-p)p_{n-1}$ $= p + (1-2p)p_{n-1}$ I can see that this step simply rearranges the expression, but ...
3
votes
1answer
39 views

Solving the recursion $p_n = p \cdot p_{n-2} + (1-p)p_{n-1}$

Solving the recursion $p_n = p \cdot p_{n-2} + (1-p)p_{n-1}$ $p_n = p \cdot p_{n-2} + (1-p)p_{n-1}$ $p_n = p \cdot p_{n-2} +p_{n-1} - p\cdot p_{n-1}$ $p_n - p_{n-1} = (-p)(p_{n-1} - p_{n-2})$ $= ...
0
votes
0answers
25 views

linear, homogeneous recursion, biological interpretation

Given the recursion $u_{k+1}=\frac{1}{2}(3 u_k - u_{k-1})$ find the expression of $u_k$ in dependence on the values $u_0$ and $u_1$. What is the limit as $ k\rightarrow \infty$ of $\{u_k\}_{k}$? Give ...
0
votes
1answer
43 views

Finding a recurrence that satisfies a sequence

Consider the sequence: $1,1,1,3,5,9,17,31,\ldots$ Find both a recurrence and a different sequence that satisfies this recurrence. Saw a decent pattern until the 31 appeared...Pretty ...
0
votes
3answers
53 views

explicit formula for $a_n$ and $b_n$ [duplicate]

Let $a_n$ and $b_n$ be natural sequence such that $$a_n+b_n\sqrt3=(1+\sqrt3)^n$$ How can I find explicit formula for $a_n$ and $b_n$
0
votes
1answer
22 views

Find $f$ explicitly when $f_n$ is defined recursively and $\lim_{n\to\infty} f_n = f.$

Given that $f_1(x) = 0$ and \begin{equation} f_{n+1}(x) = e^{-2x} + \int_0^x e^{-2t}f_n(t) \; dt, \; \text{ where }n = 1,2,\dots \end{equation} identify $f(x)$ explicitly where $\lim_{n\to\infty} ...
1
vote
2answers
52 views

How can you prove this by strong induction?

The sequence $b_1,b_2,...$ is defined recursively as:\begin{align} b_1&=0;\\ b_2&=1;\\ b_n&=2b_{n-1}-2b_{n-2}-1 \ \text{for} \ n\geq3. \end{align} Prove that this means: $$\forall n\geq1: ...
2
votes
1answer
21 views

induction with 2 recursive sequnces

I'm having trouble solving this problem. I have relation for two sequences of natural numbers. $$a(n)+\sqrt3\cdot b(n)=\left(1+\sqrt3\right)^n$$ and I have to prove that recursions: ...
1
vote
0answers
24 views

Cutting cheese into chunks [duplicate]

Into how many chunks can one cut a round piece of cheese with n straight cuts? Consider the $3D$ version My try: f(x) = number of pieces and $'x'$ as number of cuts. $f(1)=2$ $f(2)= 2 + f(1)$ ...
1
vote
1answer
32 views

n-th number with given prime divisors

I would like to compute th $n$-th positive integer whose prime divisors are among numbers $2$, $3$ and $5$. $n$ is at most $12500$. My first approach was sieving but i found out that there are less ...
2
votes
1answer
70 views

What is $\lim\limits_{n \to \infty} x_n$ where $x_1=2$ and $x_{n+1}=123+\sqrt{4+5 \sin(x_n) + 6\sqrt{x_n}}$?

$$x_{n+1}=123+\sqrt{4+5 \sin(x_n) + 6\sqrt{x_n}}, \quad x_1=2$$ At first glance, this sequence seems like it will diverge, since it seems like every term is growing by at least $123$. However, I ...
1
vote
2answers
30 views

How would I find the characteristic equation of this Recurrence Relation?

Find and solve a recurrence relation for the number of $n$-digit ternary sequences with no consecutive digits being equal. Since for ternary, meaning only $3$ possible entries for each space, e.g. ...