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
0answers
48 views

What is the maximum amount of solutions to $f(x+1)f(x)= ax^2+bx+c$.

$f(x)$ is going to be in the form $mx+h$ thus, $(mx+m+h)(mx+h) = ax^2+bx+c$. With basic algebra $m= \pm \sqrt{a}$. Also $(m+h)(h)=c$. I would guess that because $(m+h)h=c$ has two solutions max if $m$ ...
1
vote
4answers
71 views

How do I solve following recursion

I have been trying to solve this $f(n) = 2 \cdot f(n-1) - f(n-2) + 2 \cdot k$ and failed , can anybody help ? $n>4$ The values of $ f(1) = a,\,f(2) = b,\, f(3) = c$ and $f(4) =d $ where $ ...
0
votes
1answer
32 views

Does the solution to $C_n = 2C_1 C_{n-1} - C_{n-2}$ can only be solved with $A = B = \frac{1}{2}$?

I was trying to solve the following recurrence in closed form (in terms of the initial conditions/base cases): $$ C_n = 2 C_1 C_{n-1} - C_{n-2} $$ with base cases: $$ C_1 = C_1 $$ $$ C_2 = 2 C^2_1 ...
2
votes
1answer
79 views

How to calculate the $n$-th member of sequence $a_{n+1}=\sqrt{y+a_{n}}$

I was searching for a smooth continuous concave function $$f:R^{+}\times R^{+}\to R^{+}$$ so that $$f(x+1,y)=\sqrt{y+f(x,y)}\quad\text{and}\quad f(0,y)=0.$$ But I couldn't find a general function, ...
0
votes
1answer
12 views

Understanding recursive function for finding GCF of 2 numbers

So I get how this code works, but I don't understanding why it works. The function assumes input num1 > num2. Algorithms are hard for me to grasp, so please explain to me like I'm five. Heres the ...
1
vote
1answer
46 views

Find recursive formula - Question from exam, check my answer

We want to demolish and move a bridge from one location to another. The bridge is made out of $m$ road segments all connected $[0,1]$, $[1,2]$, $[2,3]$...$[m-1,m]$ We have a given function $f$ which ...
3
votes
2answers
226 views

Can the recurrence $C_n = 2 C_1 C_{n-1} - C_{n-2}$ be expressed in a closed expression?

I was wondering if the expression: $$ C_n = 2 C_1 C_{n-1} - C_{n-2} $$ could be expressed as a closed expression in terms of (hopefully polynomials of) $C_1$ (or $C_2$). The bases cases for this ...
0
votes
1answer
11 views

Recursive formula for minimal editing distance - check my answer

Given a word $X=x_1x_2x_3...x_i$ and $Y=y_1y_2y_3...y_j$, the minimal editing distance is defined to be the minimal number of actions needed to transform $X$ to $Y$ where the legal actions are: 1) ...
-1
votes
0answers
30 views

Number of simple, connected graphs with K edges and N distinctly labelled vertices [closed]

Ok. I'm aware of this question and answer, but it's over my head. I've written a recursive function that I thought would do the job, but it doesn't, apparently. Could someone explain to me why it's ...
2
votes
1answer
29 views

Find recursive formula for special function

Kind of a strange question I know, but here goes: We are given a string of letters $T$ without any gaps or commas, just letters. Depending on what $T$ is, it could be broken down to form a valid ...
2
votes
1answer
35 views

Why is $f(x)=x^{2}+1$ a primitive recursive function?

I'm trying to find out why $f:\mathbb{N}\rightarrow\mathbb{N},f(x)=x^{2}+1$ is a primitive recursive function. For $f(S(y))$ I can't seem to get it to fit the axioms known to me about primitive ...
0
votes
0answers
25 views

De-recursifyng a recursive sequence

I'm working on a recursive function for my IB Maths exploration, of the form $f(x)=f((x+a)^{-b})$ I've worked out a general formula for the n-th term of the sequence when $b = 1$, but whenever I'm ...
2
votes
4answers
46 views

Solve recurcion using generating function

I have got a problem with solving this equation using generating functions. $$ P_{n}=2nP_{n-1}-10n+5 $$ $$ P_{0}=5 $$ I started like that: $$ ...
0
votes
1answer
18 views

Solving a problem using the master theorem?

How can I solve this problem with master theorem. Giving asymptotic upper and lower bounds If $T(n)=4T(n/3)+ n log(n)$ a=4 b=3 k=1 for the formula $aT(n/b)+n^k log^b(n)$ if $a>b^k$ then ...
-2
votes
0answers
19 views

Help solving a 579 T(n) = T(n-2) +3 ( find max and min in array)

I have the following recursion function: T(2)=1 T(n)=T(n−2)+3 T(n-2)=T(n-4)+3+3 T(n-4)=T(n-6)+3+3+3 . . . T(2)+3+3+...+3 Is it possible to show how you can solve it? How to calculate the ...
1
vote
1answer
25 views

Eliminating a summation

I need to approach the new position $(x_t,y_t)$ at moment $t$ of a moving object at $(x_0,y_0)$ given its horizontal velocity $vx_0$, its vertical velocity $vy_0$ and some constant resistance $r$ that ...
0
votes
2answers
25 views

Recursive equation in graph theory

How many vertex-colorings with 3 colors has the cycle $C_n$? How to build a recursive equation for the number of colorings over n? I know that a cycle has either 2 or 3 colors. 2 when n is even and ...
0
votes
0answers
11 views

Question about the effect of the basic primitive recursive projection function.

Projections are said to allow us to use "any argument in any order", and the function below can be proved to be a PR function by projections and the composition rule. Let $ i_0,\cdots,i_{m-1} \in n = ...
1
vote
1answer
51 views

What is the meaning of 'recursive' in Boolos, Burgess and Jeffreys? (Computability and Logic)

In the book Computability and Logic by Boolos, Burgess and Jeffrey (page 71 - 5th edition) it defines a recursive function as follows: The functions that can be obtained from the basic functions ...
2
votes
2answers
42 views

Solution to Fibonacci Recursion Equations

Let the sequence $(a_n)_{n\geq0}$ of the fibonacci numbers: $a_0 = a_1 = 1, a_{n+2} = a_{n+1} + a_n, n \geq 0$ Show that: i) $$a^2_n - a_{n+1}a_{n-1} = (-1)^n \text{ for }n\geq1$$ I try to show ...
0
votes
1answer
54 views

The result of substituting recursive total functions in a recursive relation.

In the book Computability and Logic by Boolos, Burgess and Jeffrey it defines a recursive function as follows: The functions that can be obtained from the basic functions $z, s, id^i_n$ by the ...
2
votes
1answer
31 views

How to calculate the limit of a recursively defined sequence?

My attempt: (i) For r=1, $x_n$ = n+1 $\iff$ $\frac{n+1}{1+1/n}$ = $x_{n-1}$ $\iff$ $\frac{n(n+1)}{n+1}$ = $x_{n-1}$ $\iff$ n = $x_{n-1}$ But I don't know how to use what I have shown so far to ...
2
votes
1answer
27 views

Can a polynomial equation always be manipulated to give a recurrence formula?

Let $p(x)$ be a real (or maybe complex) polynomial. Suppose we wish to (numerically) solve $p(x) = 0$. This can be done for example with Newton's method of course, but I was thinking about if you ...
0
votes
0answers
7 views

Upper bound for recursive formula

I have the following recursive formula: $F(n,m) = F(n-1,m) + (n-1) F(n-1,m-1)$ $F(n,1) = 2$ $F(2,m) = 2$ When $m \geq n-1$, then $F(n,m) = n!$ My question: Is there any simple (non-asymptotic) ...
1
vote
1answer
41 views

A linear recursion with power coefficient

In my research, I encounter a linear recursion of the form: $$a_n = (AB^n+C)a_{n-1}-AB^na_{n-2},$$ where $A,B,C$ are all positive (arbitrary) constants such that $B,C>1$. Is it possible to get a ...
1
vote
3answers
62 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
100 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 ...
1
vote
2answers
75 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
42 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
86 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
41 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
34 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 ...
1
vote
1answer
59 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
16 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
40 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
30 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
61 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
40 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
2answers
28 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
46 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
35 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
25 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
20 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
77 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
65 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
50 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 ...
1
vote
1answer
48 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
69 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
37 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) = ...