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
3answers
70 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 ...
4
votes
1answer
165 views

Are hyperoperators primitive recursive?

I apologize if this question is too basic. I have read that the Ackerman function is the first example of a computable but NOT primitive recursive function. Hyperoperators seem to be closely related ...
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 [on hold]

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
49 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
12 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}$
0
votes
2answers
59 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 ...
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
0answers
32 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 ...
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 ...
2
votes
2answers
63 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
votes
0answers
27 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
27 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
17 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 ...
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
38 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 ...
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
52 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
1answer
24 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
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
33 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) = ...
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 ...
1
vote
3answers
42 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)$ ...
5
votes
0answers
114 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, ...
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) = ...
2
votes
1answer
39 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
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 ...
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
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
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
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$ ...
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 ...
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 ...
1
vote
0answers
23 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 ...
0
votes
1answer
35 views

How do I make my TI-89 evaluate a recursive function?

On my TI-89 I can assign variables recursively such as: $1\to x$ returns 1 $x+1 \to x$ returns 2 $x+1 \to x$ returns 3 etc. How could I do functions the same way: $x \to f(x)$ returns Done $2\cdot ...
0
votes
3answers
58 views

Prove that $1 \cdot 1!+2 \cdot 2!+\cdots+n \cdot n!=(n+1)!-1$

Prove that $1 \cdot 1!+2 \cdot 2!+\cdots+n \cdot n!=(n+1)!-1$ whenever $n$ is a positive integer. Basis step: $P(1)$ is true because $1 \cdot 1!=(1+1)!-1$ evaluate to $1$ on both sides. Inductive ...
1
vote
0answers
16 views

How to state a recurrence that expresses the worst case for good pivots?

The Problem Consider the randomized quicksort algorithm which has expected worst case running time of $\theta(nlogn)$ . With probability $\frac12$ the pivot selected will be between $\frac{n}{4}$ and ...
0
votes
1answer
48 views

Manipulating series to find the recursive formula

Ok so I am stuck. I need to get all the $n$'s to $=0$ but I can't reduce my series which has $n=2$ to $0$ because then I will have undone all my work in the first place to get all the $X^n$'s to the ...