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

0
votes
0answers
6 views

Runtime Complexity | Recursive calculation using Master's Theorem

So I've encountered a case where I have 2 recursive calls - rather than one. I do know how to solve for one recursive call, but in this case I'm not sure whether I'm right or wrong. I have the ...
-1
votes
0answers
13 views

Prove by induciton that the Merge(A,B) algorithm is correct [on hold]

I am asked to prove the correctness of the Merge(A,B) algorithm that merges two arrays A and B into an array C. This is the precursor to the MergeSort(X) algorithm. Can anybody help with an ...
0
votes
1answer
16 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
24 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
10 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 ...
0
votes
1answer
15 views

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

Let J be the equation: \begin{equation*} J(x,y)= \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 the ...
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
28 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
19 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
0answers
15 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 ...
1
vote
0answers
27 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
22 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
30 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
57 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
15 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
37 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 ...
2
votes
1answer
35 views

How to show that recurrence $T(n) \in \Omega(n^{0.5})$ using proof by induction?

This is recurrence $T(n)$ $ T(n) = \begin{cases} c, & \text{if $n$ is 1} \\ 2T(\lfloor(n/4)\rfloor) + 16, & \text{if $n$ is > 1} \end{cases}$ This is my attempt to show that $T(n) \in ...
0
votes
2answers
21 views

Does this recurrence relation run in $ \Theta(n) $?

This is the recurrence relation I am trying to solve: \begin{align} T(n) & = 2 \cdot T \left( \frac{n}{4} \right) + 16, \\ T(1) & = c. \end{align} I broke this down (i.e., solved this ...
3
votes
2answers
49 views

Chaos theory and fractal geometry: Constructing from data

I understand that fractal geometry represents behaviour of 'chaotic' system, if I am not wrong. And also, fractals are generated by a recursive function. But, lets say I have random data lying with ...
0
votes
1answer
40 views

Discrete Mathematics Fibonacci Sequence

I am studying for the final exam in my Discrete Mathematics class and came upon the following problem on the study guide we were given. Given the following algorithm: If $n = 0$, then $f(n) = 0$ ...
1
vote
1answer
44 views

Proof of Newton Girard formula symmetric polynomials

Newton Girard formula states that for $k>2$: \begin{equation} p_k=p_{k-1}e_1-p_{k-2}e_2+\cdots +(-1)^{k}p_1e_{k-1}+(-1)^{k+1}ke_{k} \end{equation} where $e_i$ are elementary symmetric functions and ...
0
votes
1answer
35 views

uncountable repetitions

I have a question (or two) about recursive naming conventions. Consider the following recursive naming sequence: Base step: Let S be any nonempty set. Let x be any arbitrary element of S. Let S* be ...
6
votes
0answers
120 views

Asymptotic behavior a recursion involving min/max

Usually when I face solving recursions I use generating functions but I'm not aware of any "tools" to use when min/max expressions are involved. For example, I have the following recursive term: ...
1
vote
4answers
88 views

Explicit formula for recursive geometric/arithmatic series

In my Algebra 2 class, we have come upon a question that the class could not solve, and that the teacher has neglected to remove from the given packet for several years because of this. The problem is ...
0
votes
1answer
45 views

Mini Tetris Winning Configuration

So here's the problem: A winning configuration in the game of Mini-Tetris is a complete tiling of a 2 x n board using only the three shapes shown in Figure 1. By allowing rotations, there can be ...
0
votes
1answer
34 views

functions and recursions

The sequence s(k) where k=1,2,3.... satisfies the recursion s(n)=s(n−2)+s(n−3) for n≥4. If s(n) is rewritten in the form s(n)=s(n−1)+S(n0,n1,…) where S(n0,n1,…) is some linear combination of terms ...
0
votes
0answers
25 views

Finding an explicit formula for An in terms of n.

Let $A_{1}= 5, A_{2} = 7,$ $A_{n+1} = A_{n} + 6A_{n-1}$. Find an explicit formula for $A_n$ in terms of $n$. Suppose $p_{n}$ is a sequence defined by $p_{1} = 0, p_{2} = 1$ & $\forall n$, ...
1
vote
2answers
73 views

Recursively defining sets of strings discrete math

So here are the two problems: Recursively define the set of bit strings K that do not have 00 as its substring. How many bit strings of length 10 are included in the above set K? Can someone ...
-2
votes
0answers
23 views

Recursively defining sets of strings [duplicate]

So here are the two problems: Recursively define the set of bit strings K that do not have 00 as its substring. How many bit strings of length 10 are included in the above set $K$? For (1) I got ...
-1
votes
1answer
47 views

Binary strings and recurrence relations [closed]

So the problem is: How many binary strings of length n contains 111? Give a recurrence relation Tn, where Tn is the number of binary strings of length n that contains 111. How could we possibly ...
0
votes
0answers
11 views

How does one know T(a) is the base case in T(n) = T(n-a) + T(a) + cn

T(n) = T(n-a) + T(a) + cn Solve by drawing recursion tree. Typically when solving other recursion tree problems, I've calculated the height of the tree in terms of when the subproblems reach T(1). ...
0
votes
0answers
28 views

Is every natural recursive relation necessarily holomorphic?

Define the set of algebraic primitive recursive relations as the set of functions defined by: $$ F(n,a,k) = F(n-1,F(n-1,F(n-1,a,a),a)...,a)_{\text{nested to depth k}}$$ $$ F(0,a,k) = a + k $$ Along ...
3
votes
1answer
73 views

The Ackermann's function “grows faster” than any primitive recursive function

I am looking at the proof that the Ackermann's function is not primitive recursive. At the part: "We will prove that Ackermann's function is not primitive recursive by showing that it "grows ...
1
vote
0answers
20 views

Runtime of recursive algorithm - Master's Theorem

I wrote a computer program that solves a question, and I am interested in knowing what is the runtime. My aim is for $O(\log n)$, and I'd like someone more experienced (and smarter?) to review my ...
0
votes
3answers
27 views

Working out recursive functions

I know that a function is defined recursively when it calls itself to progressively converge on a solution based on an initial condition. For example if we consider the function defined by $$Sq(1) = ...
1
vote
0answers
20 views

function with a recurrence relation

I have this recursive equation: $$\begin{align*} F(m,n)&=F(m,n-1)+F(m-1,n)-F(m-1,n-1-m)\\\\ F(m,0)&=F\left(m,\frac12m(m+1)\right)=1\\ F(m,i)&=0\text{ if }i<0\text{ or ...
0
votes
1answer
41 views

Expressing a function's value using finite differences

Let $f : \mathbb{R} \rightarrow \mathbb{R}$ and let $x = (x_0, x_1, x_2, \dots)$ be a sequence of pairwise distinct real numbers. For every $n \in \{1, 2, \dots\}$ and every ordered $(n+1)$-tuple ...
1
vote
0answers
20 views

Stability with 2 dimensional recursion functions.

First of all, hello. I'm having trouble determining whether fixed points are stable or unstable. I have a recursion function: \begin{align*} f_{\alpha,\gamma} \left( \begin{array}{c} t\\ v ...
0
votes
1answer
28 views

Evaluating integral $\displaystyle \int_0^\infty x^n e^\frac{-x}{n} dx$ with Gamma-function?

Consider the following integral: $\int_0^\infty x^n e^\frac{-x}{n} dx $. One can find a recursion formula for $R_k = \int_0^\infty x^k e^\frac{-x}{n} dx $: $R_k = n k R_{k-1}$. This yields $R_n ...
2
votes
5answers
60 views

Computing $\lim_{n\to\infty}\sqrt{\frac{2n}{n+1}}$

We are asked to find the limit of the recursively defined sequence, and to assume that the sequence converges. $a_1$=0 and $a_{n+1}$= $\sqrt{8+2a_n}$ I then solved for $a_n$ using algebra. ...
1
vote
0answers
21 views

Recursive definition of sequences inverse/equivalency.

So here's the problem: "Give a recursive definition of the sequence ($a_n$), $n = 1, 2, 3, ...$ if $a_n = 4n - 2$." Here's my answer:$$t_1 = 2; t_n = t_{n-1} + 4$$ However, I know this could also ...
2
votes
1answer
50 views

Why can you place in the recursive definition to find the limit?

When required to find limits of recursive sequences, i.e. $$x_{n+1}=\frac{1}{4-x_n}\qquad x_0=3$$ The steps are usually pretty consistent. First you prove it's monotonous and bounded, and therefore ...
0
votes
1answer
29 views

Node Game Recursion Problem

http://i.imgur.com/LwNr4rn.png I'm trying to figure out part a. However, I'm not sure if the set of simultaneous equations I've found is correct. Or at least, I can't solve the set. Any help would be ...
1
vote
1answer
54 views

Which way is best to solve: $T(n)=5T(n/5) + n\;?$

I'm not sure which way is best to solve $$T(n)=5T(n/5) + n$$ (recursion tree/master method/recurrence?) I would like some assistance, which way is easier and how can I be sure I got the right answer ...
2
votes
0answers
27 views

Recursion asymptotic growth function proof of complexity

I have the following recursive function(an example from a textbook): $$ T(n)=\begin{cases}1&n=1\\T(\lfloor\tfrac n2\rfloor)+T(\lceil\tfrac n2\rceil)+1&n>1\end{cases} $$ A recursion is ...