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

3
votes
1answer
129 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
0answers
28 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) . $$ $$ T(n)=T(\...
0
votes
0answers
26 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 ...
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 ...
2
votes
2answers
162 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
253 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 ...
1
vote
1answer
64 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
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 ...
0
votes
0answers
7 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 ...
0
votes
1answer
22 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....
4
votes
1answer
67 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
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
55 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 ...
2
votes
1answer
37 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 ...
0
votes
4answers
71 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 $x_0=...
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
43 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
0answers
39 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 \end{...
0
votes
1answer
47 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
23 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) (x+...
10
votes
1answer
325 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 q_2=1/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 what'...
0
votes
0answers
26 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 ...
3
votes
1answer
40 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
1answer
45 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 stuck. ...
0
votes
3answers
55 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
24 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} f_n(...
1
vote
2answers
54 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: ...
1
vote
1answer
25 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: $$\begin{align*...
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)$ ...
2
votes
1answer
73 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 ...
0
votes
4answers
56 views

If $a_1=1/2$ and $a_{n+1} = a_n^2$, the sequence is convergent

If $a_1=1/2$ and $a_{n+1} = a_n^2$, prove that this recursive sequence is convergent. I know I need to show that it is bounded and monotone decreasing, but I'm not sure how to go about doing that.
2
votes
1answer
33 views

Closed Form Solution to Exponential Recursion

Is there a closed form solution to the function $f_n=2^{f_{n-1}}$ where $f_0=2$ ? For instance, the first few values of the function are 2, 4, 16, 65536.
0
votes
0answers
16 views

Finding Height, Number of Leaves, and Value at of Each Node on Recursive Trees

I have an exam tomorrow and am struggling to understand how to get the height of a tree, the number of leaves, and the value of each node. The image is a practice exam. Any tips and help on the first ...
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. $0$...
2
votes
1answer
103 views

What's the real life purpose of Knuth arrows?

I recently read about Knuth's Arrows. Didn't even know those operations existed. My questions is: Do they have real-life applications? Most of the times a mathematical development follows a real-life ...
1
vote
1answer
40 views

Find a recurrence expression which solution have $\sin$ or $\cos$.

I, I'm a computer science student of the first course. My teacher have told us to try to find a recurrence equation for the closed-form expression: $$f(n) = 2^n + 3^n \cos\left(\frac{n\pi}{2}\right) ...
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 ...
0
votes
3answers
39 views

Finding general formula for a sequence that is not arithmetic and neither geometric progression?

I have this $$a_{n+1} = a_n + 4n - 1\qquad a_1 = 2$$ And I need to find general formula for $a_n$. This is one of the last exercises for the question related to it so I'll give a summary of what I ...
0
votes
0answers
22 views

Converting Non-linear Recursive Series into Explicit Form

I know it's possible to convert any (I think it's any, at least) first-order recursion into an explicit form. For example (assuming I did this right): ...
1
vote
0answers
25 views

Probability Method Of Recursive number patterns in everyday things

I'd like to know how to go about calculating the probability of a recursive number pattern happening in everyday things for an essay which I'm writing. The example of a recursive number pattern would ...
3
votes
1answer
66 views

Fractal fundamentals

I am a programmer by trade, and am very interested in fractals. To be very basic about the concept, one might say a 'circle of circles' is a fractal. Where each circle is made up of circles, and ...
0
votes
0answers
18 views

Plotting y=x^(1/y)

So I was toying around with the idea of recursive functions, where there are two variables, and one of them is on both sides of the equation. I stumbled upon/came up with this function: y = x^(1/y), ...
1
vote
2answers
37 views

A semi-recursive infinite set is the range of some injective recursive total function

The wikipedia article for semi-recursive sets (formally titled "recursively enumerable sets") claims: A set S of natural numbers is called recursively enumerable if there is a partial recursive ...
3
votes
1answer
19 views

Showing the number of y < x such that xRy is primitive recursive.

Suppose that $Rxy$ is a (primitive) recursive relation. Let the function $ \phi $ be defined as follows: $\phi(x)$ = the number of $y < x$ such that $Rxy$. Show that $ \phi $ is (...
1
vote
1answer
35 views

how do I prove this by induction? (recursion)

The terms are given recursively: $P_0=3$ $P_1=7$ and $P_n = 3P_{n-1}-2P_{n-2}$ for $n\ge2$ What should I assume and what step proves that $P_n=2^{n+2}-1$ is a closed form of the sequence. Suppose $...
0
votes
1answer
48 views

Find and solve a recurrence relation for the number of matches played in a knockout tournament with $n$ teams, where $n$ is a power of $2$

Find and solve a recurrence relation for the number of matches played in a knockout tournament with $n$ teams, where $n$ is a power of $2$ I have already found a recurrence relation based on the two ...
0
votes
0answers
31 views

I have a proposal on recursive functions, but I need a second voice to be sure it makes sense.

My main field is computer science. Although I am mostly familiar with computer science theory, I lack in math theory. So, to an average computer scientist, the term ‘recursive function’ will invoke ...