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
2answers
121 views

Recursion on a class instead of a set

According to Wikipedia, the recursion theorem states the following: Let $X$ be a set, and $f:X\to X$ a function. For any $x\in X$, there exists a unique function $g:\omega\to X$ such that $g(0)=x$ ...
0
votes
0answers
30 views

Financial mathematics: asion option

I've got a forward starting asian call option: $V_N = max\left( 0,\left(\sum_{j=m+1}^{N}{S_j} - K \right) \right) $ So the payoff is determined by the average stockprice over de latest N-m days and ...
0
votes
1answer
36 views

Solution to recursion equation

Solve the recursive equation $$ T(n) = T(n-1) * T(n-2) $$ with $T(1) = a$, $T(2) = b$ How do I solve this algebraically? I unrolled the recursion and got a solution of $a^{f_n}b^{f_{n+1}}$, ...
0
votes
1answer
76 views

How to find explicit formula using backwards iteration

For this problem I tried to solve it by iterating downward so: an = an-1 - n an-1 = 2*(2an-2 - (n-1)) - n = 4an-2 - 3n + 2 an-2 = 2*(4an-3 - 3n + 2) - n = 8an-3 - 7n + 4 an-3 = 2*(8an-4 - 7n + ...
-1
votes
1answer
26 views

How to prove that if $T(n)=\max_{1\le q \le n-1}(T(q)+T(n-q))+\Theta(n)$ then $T(n)=O(n^2)$

I have this recursion relation: $T(n)=\max_{1\le q \le n-1}(T(q)+T(n-q))+\Theta(n)$. How do I show that: $T(n)=O(n^2)$ Thank you!! (P.S. I hope it's OK to ask it, but I'm looking for the simple ...
2
votes
1answer
39 views

Ways of defining a recursive function that counts right-parenthesis in a string

I'm trying to find a more elegant way of defining a recursive function on $\{(,)\}$ that counts right-parenthesis in a string. Let r be a function on $\{(,)\}$ defined recursively so that: ...
0
votes
1answer
23 views

How to solve $T(n)=\frac2n\sum_{i=1}^{n-1}T(i)+\Theta(n)$

I need to solve this Recursion Relation:$$T(n)=\frac2n\sum_{i=1}^{n-1}T(i)+\Theta(n)$$ Do you have any idea how? (I try to find another way instead induction). (We should get: $T(n)=\Theta(n\log n)$) ...
1
vote
2answers
72 views

Solving recurrence relation $f(n) = f(\lfloor\sqrt n\rfloor) + 1; f(1) = 1, f(2) = 1$

As the title shows, I need help approaching a solution for recurrence relation: $f(n) = f(\lfloor\sqrt n\rfloor) + 1$ if $n\ge3$ with initial values $f(1) = 1$, $f(2) = 1$ I am particularly ...
0
votes
2answers
43 views

Using Master Theorem to prove a recurrence with f(n) = Θ(n/logn)

I'm trying to use the master theorem to solve the recurrence: $$T(n) = 4T\left(\frac{n}{5}\right) + \Theta\left(\frac{n}{\log n}\right)$$ I'm having trouble understanding how the ...
2
votes
2answers
133 views

how many even number faced dice will be their if 99 dices roll for eternity with some condition

Consider a six ­sided dice with number from 1 to 6. Imagine you have a jar with 99 of such dices. You throw all dices on the floor so they all land at different numbers. You look at one dice at a ...
2
votes
0answers
24 views

Complexities of Recurrences in the form $t(n) = t(\alpha n) + t(\beta n) + cn$ [duplicate]

When considering recurrence relations, they are generally of a form similar to $$t(n) = t(\alpha n) + t(\beta n) + cn$$ and there are three cases to be considered for our values of $\alpha$ and ...
2
votes
1answer
21 views

Recursion and Time Complexity Concept

The question prompt is as follows: Consider the function $f(n)$ defined as: $$f(n) = \begin{cases}n(n-1)f(n-2) & n > 1\\1 & n=0,\; n=1\end{cases}$$ How may be $g(n)$ be defined ...
1
vote
2answers
37 views

Recursive Equation.

We have a recursive function: $$a_n = Aa_{n-1} + Ba_{n-2} $$ We assume that $ x ^ n = a_n $. From this equality quadratic equation we have two solutions $$ \alpha, \beta, \qquad\alpha \neq \beta $$ In ...
1
vote
1answer
13 views

Using a recursion tree to obtain an algorithm classification with n^2 time

I'm having trouble getting the classification of this recurrence relation using a recursion tree. $$T(n) = 3T(n/2) + n^2$$ I have the tree written out correctly (I hope): ...
2
votes
1answer
37 views

Imaginary solutions of a recurrence relation

How to solve this recurrence relation using characteristic equation and imaginary numbers? We have $a_0 = 0$ and $a_1 = 1$ , and for all $j\in\mathbb N$: $$a_{j+2} = 6a_{j+1} - 10a_j$$ I would ...
0
votes
3answers
51 views

Solve recurrence relation problem

This is a recursion problem that I am stuck at. I need to use the characteristic equation. Let $a_0, a_1, a_2, . . .$ be defined by $a_0 = 5, a_1 = 0$, and $a_{n+2} = a_{n+1} + 6a_n$ for $n \ge 0$. ...
0
votes
2answers
38 views

If $T(0) = 0$ and $T(n>0) = 2T(n-1)+4^n+1$, what is the explicit formula (via recursion)?

All I know is that you'd have to use substitution to get rid of $T(n-1)$ and summations for the rest, but whenever I work through it I get to $2^{(n+2)}+2^{(n-1)}-2.5$ which is not the correct answer ...
1
vote
0answers
29 views

Approximate Solution to Backwards Recurrence of Dynamic Game

Suppose we keep tossing a fair dice until we reach some cumulative sum greater than or equal to $N$. Then, let $S_k$ be the expected value of the final sum, given that the current sum is $k$. We have ...
0
votes
1answer
22 views

Recursive sort that doesn't require list splicing?

I was just wondering if there was some form of sort algorithm that doesn't require any form of splicing of the original list? Thanks in advance.
0
votes
2answers
48 views

A nice recurrence sequence

I want to find general solution for recurrence: $a_n=7a_{n-1}-10a_{n-2}+4n$ with suppose $c_1, c_2, c_3$ is constant. I need some tutorial or solution on this challenging recurrence.
2
votes
2answers
73 views

How does mathematics fit into fractal generation for computer graphics?

I have to do a research paper on any mathematical concept. The mathematical concept must be complex, so I thought fractals would be a good choice (I was told it was a complex idea). I have been ...
1
vote
1answer
50 views

Solving recurrence equations with repeated substitution?

Say we have a recurrence equation as $$ T(n) = \begin{cases} T\left(\frac n2\right) +n & \text{if }n\ge2 \\ 1 & \text{if }n=1 \end{cases} $$ Would the first substitution be like this? ...
2
votes
0answers
93 views

$n^{\text{th}}$ digit of $\sqrt{2}$ decimal representation is primitive recursive function

An exercise from Maltsev's "Algorithms and recursive functions". Problem: Let $\sqrt{2} = a_0,a_1a_2\dots a_n\dots$ be the decimal representation of $\sqrt{2}$. Show that the function $f(n) = a_n$ ...
0
votes
2answers
39 views

I am kind of confused on how to solve this question. Can anyone help please

If we let $S$ be the set that is defined by the following two rules: 1 is an element of the set $s$ If $s$ is an element of the set $s$, then x+$2 \sqrt{x}+1$ is also an element of the set $s$ how ...
0
votes
2answers
75 views

How do i prove these type of questions? I am Really stuck.

How do I solve this textbook question: If we let $n\geq 1$ be an integer and define $A_n$ to be the number of bitstrings of length $n$ that do not contain $101$ How do I determine $A_1$, $A_2$, ...
1
vote
1answer
58 views

How can I solve this recursion question, I am really stuck. [duplicate]

I am doing a couple of exercise questions, How do I show that if we let $n \geq 1$ be an integer, and if we consider $n$ people $P_1$,$P_2$,...,$P_n$. If we let $A_n$ be the number of ways these $n$ ...
0
votes
1answer
67 views

Recursion: Dividing n people into groups of 1 or 2

Let $n \ge 1 $be an integer and consider $n$ people $P_1, P_2, . . . , P_n$. Let $A_n$ be the number of ways these $n$ people can be divided into groups, such that each group consists of either one ...
0
votes
0answers
20 views

Developing closed-form from recursive definition

Here is a recursively-defined function where c, d ∈ N. T(n) =    c, if n = 0 d, if n = 1 2T(n − 1) − T(n − 2) + 1, if n > 1 Carry out the five steps for repeated substitution to prove a ...
0
votes
0answers
33 views

Prove using Induction : Recursion

let $n \gt 1$ be an integer, and consider n people; $P_1,P_2,...,P_n$ let $A_n$ be the number of ways these $n$ people can be divided into groups, such that each group have either one or two people ...
0
votes
2answers
72 views

Recursion: putting people into groups of 1 or 2

let $n \gt 1$ be an integer, and consider n people; $P_1,P_2,...,P_n$ let $A_n$ be the number of ways these $n$ people can be divided into groups, such that each group have either one or two people ...
2
votes
2answers
43 views

Proving a Recursion Using Induction

I am trying to prove the following recursion. $$a(n) = \left\{\begin{matrix} n(a(n-1)+1) & \text{if } n \geq 1\\ 0 & \text{if } n = 0 \end{matrix}\right.$$ is the series definition of ...
0
votes
1answer
22 views

Substitution method for solving recurrences piece wise function

I don't know how to use the substitution method for the following function: piece wise function: $T(n) = c$, if $n=0$ $T(n) = d$, if $n=1$ $T(n)=2T(n-1)-T(n-2)+1$, if $n > 1$
0
votes
1answer
65 views

How many combinations can I make?

let $n \gt 1$ be an integer, and consider $n$ people; $P_1, P_2,..., P_n$ let $A_n$ be the number of ways these $n$ people can be divided into groups, such that each group have either one or two ...
2
votes
3answers
123 views

Counting the number of different ways in which groups of one or two can be formed…

I'm having trouble proving that the number of ways n>3 people can be divided into groups of either one or two is equal to: $A_n = A_{n-1} + (n-1)⋅A_{n-2} $ I'm trying to prove this by counting but ...
1
vote
1answer
57 views

Does the existence of a recursive sequence that involves an arbitrary choice at every step require the axiom of choice?

Say I want to define a sequence $(x_n)$ recursively, and at each step I make an arbitrary selection for $x_{n+1}$ out of some nonempty pool of acceptable candidates dependent on $x_n$. Does the ...
0
votes
1answer
128 views

Recursive Sequence Ratio Convergences

I would like to propose a conjecture (I haven't found any ressources covering my hypothesis): Let $X$ be a recursive sequence of the form \begin{equation*} X_n = \sum_{i=n-a}^{n-1} X_i ...
1
vote
2answers
45 views

Are there real extensions of the operations of addition, multiplication, exponentiation, etc in the other direction?

We have $\underbrace{a+a+a...+a}_{n\:times}$ which equals $a \times n$, and also $\underbrace{b \times b \times b.... \times b}_{p\: times}$ is $b^p$, so I was wondering if the generalization would ...
2
votes
1answer
86 views

Strong induction on a summation of recursive functions (Catalan numbers)

I've been stuck on how to proceed with this problem. All that's left is to prove this with strong induction: $$\forall n \in \mathbb{N}, S(n) = \sum_{i=0}^{n-1} S(i)*S(n - 1 - i)$$ Some cases: S(0) ...
2
votes
2answers
65 views

Recurrence Relation from Old Exam

I see this challenging recurrence relation that has a solution of $T^2(n)=\theta (n^2)$. anyone could solve it for me? how get it? $$T(n) = \begin{cases} n,\quad &\text{ if n=1 or n=0 ...
3
votes
0answers
39 views

When do Leibniz-like rules lead to unique linear operators

Background Usually one defines differentiation in terms of limits, and then shows that differentiation satisfies the Leibniz (product) rule, $$\frac{d}{dx}(f \cdot g) = f\frac{dg}{dx} + g ...
0
votes
1answer
44 views

Definition of factorial function for sets

Why is the factorial function expressed in terms of $(n+1)$ for sets? $0! = 1$ $(n+1)! = (n+1) \times n! $ for all $n$ $\in\mathbb{N}$ Instead of the more "common" $0! = 1$ $n! = n \times (n-1)!$ ...
0
votes
1answer
39 views

Sinewave riding on sinewave help

Consider this image Top one is Cos(t), I know that. What is the equation for the second one? (sinewave within sinewave) And how would I get to the third one and then on n-amount of recursion? Mind ...
1
vote
2answers
63 views

Natural numbers object via initial morphism

I assume that a natural number object (or see nLab) can be defined as an initial morphisms. (edit: as in the title, I ment initial morphism, not objects) $\hspace{1cm}$ Thoughts: Probably $X:=1$, ...
0
votes
5answers
65 views

Recursive formula - alternating addition and suntraction

So i got this formula that basically does this: $$f(n) = n^2-(n-1)^2+(n-2)^2...$$ until it gets to $f(1)$ which is $1$. The recursive form is: $$f(n)=n^2-f(n-1)$$ So is there a way to get to the ...
1
vote
2answers
66 views

Converting Recursive Function into Closed/Explicit Form

so I have this recursive function here: $\forall n>1,f(n) = 2(f(n-1)) + n-1$, (where it is $0$ when $n$ is less than $1$) So I have tried to use iteration for this but it just gets more ...
0
votes
1answer
45 views

A question about numbers with a certain property

Find (if exists) a subset of the non negative integers $X$ such that for every non negative integer $n \in \mathbb{N}\cup\{0\}$ there is exactly one solution of the form $a+2b=n$ with $a,b \in X$ I ...
1
vote
2answers
40 views

Recurrence problem with a game of probability [duplicate]

Fair coin flipping (50% on both sides) $P_1$ and $P_2$ plays a few games of fair coin flipping. Assume player $A$ starts with $x$ coins and player $B$ with $y$ coins. Let $P_n$ denote the ...
2
votes
5answers
31 views

Solve recursion with constant added

I have the following problem: Define a sequence $(a_n)$ where $a_1 = 4$ and $a_n = 4a_{n-1} - 4$. Find a closed form for $a_n$. So basically I usually know how to deal with recursions like $a_n = ...
0
votes
3answers
41 views

Finding a recursive formula for a number

I am trying to find a recursive formula for a given number in order to solve a problem I am working on. For every $n \in \mathbb{N} \setminus \lbrace 0,1 \rbrace$ we define the number ...
3
votes
3answers
171 views

Fixed point combinator and functions with no fixed point

In lambda calculus the fixed point combinator is defined as: It is very easy to see how $Yg =g(Yg)$ for any $g$ by using $\beta$-reduction. At the same time I wonder what is the meaning of ...