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

1
vote
3answers
47 views

A recursive sequence is defined by…

A sequence is defined recursively by $a_1=1$ and $a_{n+1} = 1 + \frac{1}{1+a_{n}}$. Find the first eight terms of the sequence $a_n$. What do you notice about the odd terms and the even terms? By ...
3
votes
0answers
71 views

uniform convergence in recursive function

Let $\varphi:[0,+\infty)\to \mathbb{R}$ an increasing continuous function that satisfies that $1/2\leq \varphi(x) <1$ for all $x>0$. Let $f_0:[0,+\infty)\to \mathbb{R}$ an increasing function ...
0
votes
1answer
19 views

Recursive equation, inhomogeneous for the Fibonacci numbers [on hold]

Recursively applies the inhomogeneous: $$F_n = F_{n-1} + F_{n-2} + g(n)$$ for $n \geq 2$ $$F_1 = g(1)$$ $$F_0 = g(0)$$ where $g: \mathbb{N} \to \mathbb{R}$ is any function. How can the recursive ...
1
vote
2answers
52 views

Finding the limit of a recursively defined sequence (recurrence relation). Specifically and generally

Whilst reading Goldrei's Classic Set Theory, I have come across a recursively defined sequence $a_0=0, a_1=1, a_n=\frac{1}{2}\left(a_{n-1} + a_{n-2} \right) $ The first few terms of which are: $0, ...
0
votes
2answers
39 views

A non-homogeneous recurrence of Fibonacci sequence

I am working on Fibonacci sequence (recursively) But the hack is that I have the following non-homogeneous version: $$F_n =F_{n-1} +F_{n-2} +g(n)$$ Where: $F_1=g(1)$ $F_0=g(0)$ I have to use: ...
2
votes
3answers
80 views

Is there official notation to represent “perform an operation n times”?

I would like to know if you can represent the idea of say, $$n^n$$ n amount of times without defining a function. For example: $$1$$ $$2^2$$ $$3^{3^3}$$ $$4^{4^{4^4}}$$ $$5^{5^{5^{5^5}}}$$ and so ...
2
votes
1answer
36 views

How do I find an analytic solution to this recursive function?

I was playing with some recurrence relations, and I ended up with this a long nested function. How can I generalize the following relationship: $$ f_n = a + \frac{b}{f_{n-1}} $$ $$ f_1 = a + ...
1
vote
1answer
31 views

Reference for a proof of the recursion theorem, for a general case.

Herbert Enderton in his A Mathematical Introduction to Logic 2nd edition, proves a theorem (a "recursion theorem") in section 1.4, p. 39. Using his example, the idea is the following: We have some ...
0
votes
0answers
27 views

Sum and recursion [closed]

In Barry Cooper's Computability theory, the author defines inductively a primitive recursive function as follows (paraphrased). The initial functions are recursive: $\mathbf{0}(n) = 0$ $\forall n ...
1
vote
1answer
53 views

Universal languages are primitive recursive.

First of all, this are the definitions I am working with. Definitions: A language $L$ is $universal$ if it is countable, has infinitely many constants, and for each $n$, $1 \leq n$ has infinitely ...
0
votes
0answers
13 views

Name of this function

Is there a name for the following function? $f(x,y) = \begin{cases} y+1, & \text{if $x=0$} \\ f(x-1,1), & \text{if $y=0$} \\ f(x-1, f(x-1,y-1)), & \text{otherwise} \end{cases}$
1
vote
2answers
38 views

Prove that the following formula is true for $n \geq 1$ by induction

Prove that the following formula is true for $n \geq 1$ by induction. $a_{n} = a_{n-1} + 4n - 3 \\ a_{n} = 2n^{2} - n + 1 \\ a_{1} = 2$ My attempt follows below. I almost succeed in proving the ...
0
votes
2answers
28 views

Linear Recurrences

I was working on linear recurrence... But I am having trouble with it. $a_0 = 1; a_1 = 2; a_k = 4a_{k-1} - 2a_{k-2}$ I found $a_2$ which is $$4a_1 - 2 a_0=4\cdot2 - 2\cdot 1 = 6$$ I found $a_3$ ...
0
votes
2answers
60 views

A series with the recursive formula.

A sequence $\lbrace a_{n}\rbrace_{n\geq 0}$ is constructed by choosing a value of $a_{n}$, and then the following elements are determined from the equation $a_{n}=2-\frac{1}{2}a_{n-1}$ for ...
0
votes
0answers
33 views

Fourier transform and recursion

Starting with the first derivative of a continuous general function $u(x)$, say $\frac {du}{dx}$ and I take the Fourier Transform of it, I know the solution is $i\cdot k\cdot U$, where $ U$ is the ...
-1
votes
0answers
28 views

Solve the following difference equation: $u_{n+1}=2u_n+n$ with $u_0=1$

Solve the following difference equation: $u_{n+1}=2u_n+n$ with $u_0=1$ Since $u_{n+1}=2u_n+n$, then $u_{n}=2u_{n-1}+(n-1)$. Thus, $v_n:=u_{n+1}-u_{n}=2(u_n-u_{n-1})+1$. So we can break this down ...
0
votes
2answers
25 views

How do I compute this recursive function efficiently? [closed]

Let $f(x,y) = xy + f(x-1,y-1) $ where $f$ equals $0$ if either $x$ or $y$ is $0$. Also $x,y$ belong to $\mathbb{N}$. Describe an efficient (less then $O(n)$) algorithm for computing $f(x,y)$.
0
votes
3answers
36 views

First order difference equation. Solve $u_{n+1}=3u_n+2$.

First order difference equation. Solve $u_{n+1}=3u_n+2$ with $u_0=0$ My notes are very sparse on this topic, so I need some help solving what should be an easy question. I would really appreciate ...
2
votes
1answer
28 views

Is this the correct minimum number of coins needed to make change?

The Problem: On Venus, the Venusians use coins of these values [1, 6, 10, 19]. Use an algorithm to compute the minimum number of coins needed to make change for 42 on Venus. State which coins are used ...
0
votes
1answer
19 views

How would you apply the Greedy technique in this situation/why wouldn't it work?

I am going over the Rod Cutting Problem The author states "Selling a rod of length $i$ units earns $P$[i] dollars." Here is the table $P$ for this problem I'am currently going over this question ...
1
vote
2answers
18 views

Help with induction step of proving a recursive definition / sequence

I'm a bit of a maths noob so please bear with me with what is probably a really dumb question, but I could really do with some help - I'm self-learning at home. I'm stuck on the question below from ...
2
votes
2answers
68 views

Ackermann's function is $\mu$-recursive

In my book there is the following proof that Ackermann's function is $\mu$-recursive: We propose to show that Ackermann's funcition is $\mu$-recursive. The first part of the job is to devise a ...
1
vote
1answer
57 views

Undecidable definition of pure function

I am trying to come up with a formal definition for functional purity in a simple programming language (think JavaScript). What I've got so far is this: DEFINITION: A statement is impure if ...
1
vote
3answers
53 views

Finding a recursion

I am supposed to find a recursion for the following sequence: $$a_{n} = (1+\sqrt{s})^{n} + (1-\sqrt{s})^{n}$$ where $s \in \mathbb{N}$ fixed. I tried playing around with it using the binomial theorem, ...
1
vote
0answers
49 views

Primitive recursivness of a function. How does the function work?

So, I need some help with an homework assignment. Firstly: understanding the following function: $h(x) = \prod_{m=0}^{f(x)} m*f(m)$ From my limited knowledge of the product of sequences my guess is ...
2
votes
1answer
41 views

$\mu-$recursive functions

In my book there is the following: Although the class of primitive recursive functions contains a great many functions of practical interest, it does not include all the Turing-computable or ...
0
votes
0answers
61 views

Why is $y + 1$ infinite?

This is related to SO question : http://stackoverflow.com/questions/30150877/why-does-this-cause-ghci-to-hang but I'm having difficulty understanding why Haskell enters an infinite loop but since ...
0
votes
1answer
34 views

Discrete math, Showing a recursive equation as equivalent to a non recursive equation.

I'm having trouble with this: Show that this recursive function: $L(n) = \{0 : n = 1\ ,\ \lfloor(L(n/2))\rfloor +1 : n \gt 1\}$ is equivalent to this non-recursive equation: $L(n) = ...
1
vote
1answer
26 views

Right notation to recurse over a sequence or list

I have a function $f(x, a)$ which is invoked over all the elements of a sequence feeding the result to the next call, with $x$ being the next element in the list and $a$ the accumulated result. What ...
0
votes
1answer
28 views

Where does the root of this tree come from?

I am doing a practice question from Midterm Dynamic Programming The Problem : Consider a row of n numbers a1, ..., an. The numbers are all positive, and n is even. We play a game against an ...
0
votes
0answers
9 views

Indexing for partitions

I'm using spatial hashing for broad-phase collision detection and I'm trying to squeeze some more performance out of it. Currently, it creates a new hashset for every partition which works well ...
1
vote
2answers
24 views

Differential Equations: Recursive Functions

Functions I have some familiarity with look so, $y^\prime(x) = \tan(x+2)$: straightforward expression of the first derivative of y as a function of x. But say I have a function, $y^\prime(x) = ...
1
vote
3answers
43 views

How to apply Master theorem to this relation?

This is the definition of master theorem I am using(from Master Theorem) I am trying to use that master theorem to find the tight bound for this relation $T(n) = 9T(\frac{n}{3}) + n^3*log_2(n)$ ...
0
votes
0answers
15 views

Recurrence relation for the colored balls problem

Right now I am attempting to solve the recurrence thats solves a famous problem (the colored balls problem: http://mathoverflow.net/questions/41939/a-balls-and-colours-problem) given by $2i(n-i)Z_i = ...
0
votes
0answers
22 views

Runtime Complexity | Recursive calculation using Master's Theorem

I have the following recurrence relation (arising from some kind of augmented merge sort): $$ T(n) = T\left({2n\over5}\right) + T\left({3n\over5}\right) + n$$ and I need to find the worst-case ...
0
votes
1answer
26 views

Solving recurrence with moebius inversion

what's up folks? I'm solving the red book of math problems, problem 16 which is to solve the following recurrence relation: $\sum_{k=1}^n {n \choose k} a(k) = \frac{n}{n+1}$ PS: ${n \choose k} = ...
0
votes
1answer
28 views

Recurrence relations

For each integer $n ≥ 1$, let $t_n$ be the number of strings of $n$ letters that can be produced by concatenating (running together) copies of the strings $“a”$, $“bc”$ and $“cb”$. For example, $t_1$ ...
0
votes
0answers
11 views

Formula for a recursive function

Given the recursive function $T: \mathbb{N}_0 \to \mathbb{R}_+$ $$T(n) ≤ max_{1 ≤ k ≤ n - 1}\{T(k-1) + T(n - k) + c n^2\}$$ with c > 0 constant, I want to determine an absolute formula to quickly ...
1
vote
1answer
43 views

Proof that mappings $K$ and $L$ are primitive recursive.

Let $J$ be the function: \begin{equation*} J(m,n)= \begin{cases} n^2+m \text { if } m\le n \\ m^2 + m + (m-n) \text { if } m > n \\ \end{cases} \end{equation*} Let $K, L$ such that $K(k)$ is ...
1
vote
1answer
22 views

$2^n=na_n+na_{n-1}-a_{n-1}$ by range transformation

I want to range transform $2^n=na_n+na_{n-1}-a_{n-1}$ to get rid of the $2^n$ term and then solve it with any other method (seems like telescoping will work once it's reduced). I've tried ...
0
votes
1answer
17 views

Proving $1+2CZ+3C^2Z^2+…=1/(1-CZ)^2$, considering $\sum\limits_{i=1}^{\infty}c^iZ^i=(1-CZ)(1+2CZ+3C^2Z^2+…)$

I'm told that we can prove this common identity for solving generating functions: $1+2CZ+3C^2Z^2+....=1/(1-CZ)^2$ Using only the property ...
0
votes
1answer
19 views

Demonstrating Strassen's method using domain transformation: $T(n)=7T(n/2)+an^2$

I want to solve the recurrence for Strassen's method (for multiplying square matrices) with domain transformation and get a closed form. The equation is given below: $T(n)=b$, at $n=2$ ...
0
votes
1answer
28 views

Getting rid of exponents with n when solving with annihilators: $a_n=a_{n-1}+2a_{n-2}+2^n+n^2$

To solve the following with annihilators: $a_n=a_{n-1}+2a_{n-2}+2^n+n^2$, for $n\ge2$, with initial conditions $a_1=0$ and $a_0=0$ we would have to get rid of the $2^n$ term at least, otherwise any ...
1
vote
1answer
31 views

Solving $\scriptsize a_n=\sqrt{a_{n-1}+\sqrt{a_{n-2}+\sqrt{a_{n-3}+\ldots}}}$ with range transformation

This is a practice problem provided by a textbook on recurrences. Solve using range transformation: $a_n=\sqrt{a_{n-1}+\sqrt{a_{n-2}+\sqrt{a_{n-3}+...}}}$, where $a_0$ =4 The hint is to view the ...
0
votes
1answer
22 views

Why is $X_m$ and $Y_m$ not included in the shaded region(where median can lie)?

This problem is from Algorithms, problem 2 The Problem Given two sorted list of numbers $X$[1..$n$] and $Y$[1..n]. we need to come up with a O($\log n$) time algorithm to find the median of the 2$n$ ...
5
votes
0answers
116 views

Recursive and Primitive recursive functions

According to the book that I'm reading, we can define the $\mu-$recursive functions inductively, as follows: The constant, projection, and successor functions are all $\mu-$recursive. If $g_1, ...
1
vote
3answers
33 views

Solving $a_n=5a(n/3)-6a(n/9)+2log_3n$ using domain transformation

$a_n=5a(n/3)-6a(n/9)+2log_3n$, For $n\ge9$ and n is a power of 3. $a_3=1$, and $a_1=0$ Transforming the first two terms is straightforward, but I'm not sure what to do with the log term. Should I ...
2
votes
1answer
40 views

Proving the principle of definition by generalized recursion using the inductive closure of an induction system

I'm working through Hinman's Fundamentals of Mathematical Logic in order to review some things, and got stuck in an exercise from section 1.2. Specifically, he asks us to prove (what he calls) the ...
1
vote
0answers
24 views

Is a linear random walk with jump recurrent?

Let $\lambda_0=10^5$ or any other large integer. Define the recursive "process": $\lambda_t=\text{sample from a Poisson distribution with mean }\lambda_{t-1}$. Is this process recurrent? I mean, after ...
-2
votes
1answer
18 views

show that $\neg(p_1 \vee p_2 \vee… \vee p_n)$ is equivalent to $\neg p_1 \wedge \neg p_2 \wedge… \wedge \neg p_n$ by induction

Use mathematical induction to show that $\neg(p_1 \vee p_2 \vee... \vee p_n)$ is equivalent to $\neg p_1 \wedge \neg p_2 \wedge... \wedge \neg p_n$ whenever $p_1,p_2,...,p_n$ are propositions. So ...