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

2
votes
1answer
33 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
69 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
42 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
323 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
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
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
54 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
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: ...
1
vote
1answer
22 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
55 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
30 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
12 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
100 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
39 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
37 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
64 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
35 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
18 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
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
1answer
46 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 ...
0
votes
1answer
47 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
28 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
21 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 ...
0
votes
1answer
42 views

Recursive Definitions

I have two recursive definitions that I need to determine if they are correct. The first one is: The set S of all positive integer multipliers of 5 can be described by the following recursive ...
3
votes
0answers
34 views

Is math recursive or iterative?

Is the process of solving a mathematical problem (algebraic equations, limits, derivatives, integrals, EDOs, trigonometric identities proof) recursive or iterative? For example, for solving $x=1+2+3$ ...
0
votes
1answer
20 views

Iterated Function System for Cosine

So, if we let $f_1(x) = 2x^2-1$ and say $f_{n+1}(x) = f(f_{n}(x))$ then some graphing and experimenting seems to indicate that $\lim_{n\to\infty} f_n(2^{-n}x) = \cos(x)$. They converge pretty quickly ...
0
votes
1answer
33 views

How to define a set of trees recursively?

In particular, consider the set of integer-labelled binary trees (T). How could this set be defined in a recursive way from $\mathbb Z$ and T itself? Examples: $(-2, 1, (3, 1, 0)) \in T$ $(-1, (7, 2, ...
1
vote
1answer
22 views

Troubleshooting Textbook: Using Generating Functions for Non-Homogenous Recurrence

I am learning about Generating Functions to solve non-homogenous linear recurrences, and I can't seem to get the right solution, no matter what I do. Also, the example I have to work off of in the ...
0
votes
1answer
25 views

Need help finding general formula for an iterative equation.

If we have a iterative equation defined as for $i=1:n$ $$a=a(4-a),$$ I need help finding the general formula for this in terms of n. I know some obvious ones like, $$n=1\quad\quad a=4a-a^2$$ $$n=2 \...
0
votes
2answers
45 views

Prove a Recursive Formula by Induction?

So I have a bonus question on a homework assignment I am working on that literally just asks "How would you prove a recursive formula by induction?" There are no numbers, or sequences given. I ...
0
votes
1answer
26 views

Do I have these recursive and closed forms correct?

For the sequence: $0,1,5,12,22,35,51,70,92,117,145,176$ I have the closed form (dashes indicate subtext): $$a_n=\frac{n(3n-1)}{2}$$ For recursive: $$a_{n+1}=\frac{a_n+3n^2+5n+2}{2}$$ If they are ...
0
votes
1answer
15 views

given an integer i and a range r of real numbers, i divides ranges exactly in half sequentially, where does i split the next r? (without recursion)

Say I have a range r from a - b, $a\in \mathbb{R}$ and $b\in \mathbb{R} $. Then, I have an integer i. Now, if I were to break the range in half, decrease i, then continue breaking the remaining ...
1
vote
1answer
53 views

Material with half-life that is being added to periodically

I am having trouble calculating this problem: $X$ amount of material with $Y$ half-life is administered on a patient. When an interval of time $=A$ elapses, ( as a given fraction of half-life) an ...
8
votes
2answers
162 views

Find Nth formula of recursive formula $a_n=a_{n-1}+n(n-1)a_{n-2}$

$$a_n=a_{n-1}+n(n-1)a_{n-2}$$ $$a_0=1, a_1=-\frac{1}{2}$$ Is it possible to find explicit formula for $a_n$ just by using $a_0$ and $a_1$? I know how to solve this problem if $a_n=Aa_{n-1}+Ba_{n-2}$ ...