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
1answer
27 views

Solve $T(n)=2T(n/2)+\log n$ with $T(1)=1$

Solve$$\begin{cases}T(n)=2T(n/2)+\log n\\ T(1)=1\end{cases}$$ I tried to use the master theorem but it didn't work, so I used the trees methode ...
0
votes
1answer
10 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 ...
-5
votes
0answers
14 views

$T(n)=2T(\frac{n}{2})+5n^3$, $T(1)=1$ where $n=2^k$ [on hold]

Solving recurrences relations. result should be in clear form of $n$
0
votes
0answers
5 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
63 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
14 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
11 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
45 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
62 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
31 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
305 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 ...
1
vote
2answers
25 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
34 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
47 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
25 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
1answer
29 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
44 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
18 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
24 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
51 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
51 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
26 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
votes
4answers
53 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 ...
2
votes
1answer
16 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
9 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 ...
2
votes
1answer
89 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
33 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) ...
0
votes
3answers
36 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
18 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): ...
0
votes
1answer
561 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 ...
1
vote
0answers
23 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 ...
2
votes
1answer
47 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
17 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), ...
0
votes
0answers
8 views

Showing a function that makes only substitutions in a sequence is primitive recursive?

Show that there is a primitive recursive function $sub(s,c,d)$ such that if $s$ codes a sequence, then $sub(s,c,d)$ is the code for the sequence that results from replacing all occurrences of $c$ ...
1
vote
2answers
31 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
17 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 ...
0
votes
1answer
42 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 ...
1
vote
1answer
34 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
0answers
30 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 ...
0
votes
1answer
44 views

Finding 1996'th term for given recurrence relation

I've been given the sequence $a_n$ defined by the recursion relation: $$a_{n+1}=\frac{a_n}{1+na_n}\qquad a_1=1$$ and have been tasked to find $a_{1996}$. How would I go about that? I have a basic ...
0
votes
1answer
26 views

Showing a relation is primitive recursive, recursive, or semirecursive.

I am not sure what strategy to use to I should use to show this is primitive recursive. I believe I am to show all three cases: primitive recursive, recursive, and semi-recursive. The diagonal of ...
1
vote
1answer
18 views

Induction on a Recursive Sequence?

So I don't really know where to go from here, or how to "guess a formula for an" a0, a1,a2... is a sequence that a0 = a1 = 1 and, for n >= 1, an + 1 = n (an +an-1) So I started off by doing the base ...