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
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
41 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
99 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
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
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
63 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
20 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
52 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
161 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}$ ...
1
vote
2answers
28 views

How can I solve this linear recursion?

Let be $a_{0}=1,a_{1}=1,a_{n}=4a_{n-1}-2a_{n-2}$ if($n\ge 2)$ Should I first find the generating function of the recursion and after that? I solved it with Wolfram Alpha and after it the result is $\...