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
1answer
29 views

How to solve a recursively defined system

It has been a while since I have tackled a problem like this and could use a refresher. I have a recursive system of equations that looks a little like: Where the initial x & y values are ...
0
votes
1answer
31 views

All solutions of the recurrence relation

Find all solutions of the recurrence relation $$ a_n = 2a_{n-1}+15a_{n-2}-36a_{n-3}+2^n $$ Hint: Find both the homogeneous and particular solutions. You can leave the homogeneous solution with ...
-1
votes
0answers
17 views

How to prove $\exists f (x,y)$, $g(x,y)$ such that $W_{ f(x,y)} =W_x \cup W_y$ and $W_{g(x,y)}=W_x \cap W_y$

According to S-m-n Theorem there are primitive recursive functions $r(x,y)$, $s(x,y)$ such that $$W_{u(x,y)}=W_x\cup W_y,\\W_{i(x,y)}=W_x\cap W_y.$$ How to prove there exist $f (x,y)$, $g(x,y)$ ...
0
votes
1answer
14 views

Log property in proof of Master theorem

The family of recurrence considered is of the form $$ T(n) = aT(n/b) + n^c $$ $a,b,c$ are integers. One case of master theorem states: if $c< log_b a$, then $T(n) = \Theta(n^{log_b a}) $. I have ...
1
vote
2answers
23 views

Is there solution for equation which is recursive?

I have this following vector equation:$$\vec x = \vec x_0 + (1/2) * f(\vec x, t)t^2$$ where $\vec x$ has initial value when first fed into function $f$. All vectors are 3 dimensional and function $f$ ...
1
vote
0answers
40 views

Finding the convergent value

The sequence is defined as follows : Start : $(x_0,y_0)$ with $ 0 < x_0 < y_0 $ Step : $x_{n+1} = \frac {x_n+y_n} {2}$ , $y_{n+1}= \sqrt{x_{n+1}y_n} $ Find $\lim_{n\to \infty}(x_n,y_n)$ . ...
0
votes
1answer
37 views

Solution of recurrence

I need some explanations at the proof of the following theorem. Theorem: Let $a$, $b$ and $c$ be nonnegative constants. The solution to the recurrence $$T(n)=\left\{\begin{matrix} b & ,\text{ ...
2
votes
1answer
28 views

A general or simple method to solve this iterative/recursive problem?

I have the following iteration $$ y_n\mapsto n\sum_{m=1}^{n+1}y_m $$ starting with $y_1$ being a positive real number. Is there a standard method to find the coeffcients of all $y_n$ after ...
1
vote
1answer
15 views

Find a closed form equation of the following sequence: ${0,0,-2,0,4,0,-6,…}$

Find a closed form equation of the following sequence: ${{0,0,-2,0,4,0,-6,...}}$ I know $1+-1^n$ = 0 if n is odd and 1 if n is even. However finding alternating signs when plugging in only even ...
4
votes
1answer
62 views

Proving $V=V_{\sf On}$ in $\sf Z+Reg$

Define the function $$V_0=\emptyset,\qquad V_{\alpha+1}={\cal P}(V_\alpha),\qquad V_{\delta}=\bigcup_{\beta<\delta}V_\beta.$$ Since we are working in $\sf Z$ (i.e. $\sf ZF$ without the axiom of ...
5
votes
1answer
28 views

Conditional iterations constant.

Let $f(0)=2.$ Define for positive integers $n$ : $f(n+1) = \frac{3}{2} f(n)$ if $f(n)$ is even. $f(n+1) = \frac{3}{2}(f(n)+1)$ if $f(n)$ is odd. We now have $\lim_{n->\infty} \dfrac{4* (3/2)^{n} ...
0
votes
1answer
16 views

How can i find the complexity of this recurrence relation?

Basically i'm having this recurrence relation which i don't know how to get the complexity of it by using the iterative method $T(n) = \begin{cases} 0, & \text{if $n=0$} \\ 1, & \text{if ...
2
votes
2answers
114 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
40 views

Discrete maths - Recursion, formula and induction question

A sequence $S_{0},S_{1},\ldots$ is defined recursively as follows: $$ S_{0} = 3\,,\quad S_{k} = S_{k - 1} + 2k\quad\mbox{for}\quad k \geq 1 $$ Calculate a few terms of the sequence and conjecture a ...
-1
votes
1answer
25 views

Solution for $T(n) = 2T(\sqrt{n}) + log_2(n)$ [closed]

Solve for: $T(n) = 2T(\sqrt{n}) + log_2(n)$ with no base conditions.
0
votes
0answers
23 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
33 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
39 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
24 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 ...
1
vote
0answers
24 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
21 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)$) ...
0
votes
2answers
32 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
33 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
53 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 ...
1
vote
0answers
14 views

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

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 ...
1
vote
0answers
11 views

Recursion and Time Complexity Concept

I have been solving this question which appeared in one of the entrance exam. The question is as follows: ...
1
vote
2answers
32 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
9 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
27 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
46 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
33 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
22 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
21 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.
5
votes
2answers
43 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
44 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
36 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? ...
1
vote
0answers
47 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
32 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
65 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
49 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
62 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
13 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
28 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
69 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
35 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
18 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
62 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
113 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
53 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
114 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 ...