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
3answers
43 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
10 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
32 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
33 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 ...
2
votes
2answers
41 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
42 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
117 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
33 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
72 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
72 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
18 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) = ...
0
votes
0answers
18 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
39 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
27 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
59 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
49 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
28 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
53 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
25 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 ...
0
votes
0answers
16 views

Show T(n)=T(n/5)+T(4n/5)+n/2 is $\Omega (n log n)$

I'm tasked with showing T(n)=T(n/5)+T(4n/5)+n/2 is Big-Omega n log n by drawing a recursion tree. The tree shows a lower bound with the following terms: n/2 ... n/10 ... n/50 ... etc. When I solve ...
4
votes
1answer
143 views

Complicated Multivariate Recurrence Relations For Generating Polynomials

I have the following multivariate recurrence relations all from the same system: First, suppose that $0\le k\le j\le m$, and let $N$ be an independent integer. Then we have for expressions $a(k,~ m,~ ...
0
votes
1answer
38 views
0
votes
1answer
22 views

Find closed form of recursion

I know how to get the equation of the form $x^2 = Ax + B$ and then from there get $a_k = C * x_1^k + D * x_2^k$ but doesn't the original $b_k$ equation have to be of the form $7b_{k-1} - 10b_{k-2}$ ...
2
votes
1answer
32 views

Recursive equation with limit

Find $\alpha, \beta, \gamma$ for recursive equation: $$ \alpha a_{n+3}-3a_{n+1}+\beta a_n = 18n$$ $$a_0=0,a_1=\gamma, a_2=3 $$ $$\lim_{n\rightarrow\infty}\frac{3a_n+(-2)^{n}}{n^3}=3$$ Hey guys, ...
0
votes
1answer
59 views

Maximize profit with dynamic programming

I have 3 tables… $$\begin{array}{rrr} \text{quantity} & \text{expense} & \text{profit}\\ \hline 0 & 0 & 0 \\ 1 & 100 & 200 \\ 2 & 200 & 450 \\ 3 & 300 & 700 ...
1
vote
2answers
22 views

a sequence of functions defined by induction

Given a sequence of functions $\{f_k\}$, suppose for any $k\geq 4$, $$ f_k=f_1f_{k-1}+\frac{1}{2}(f_2-f_1^2)f_{k-2}+(\frac{1}{6}f_1^3-\frac{1}{2}f_1f_2+\frac{1}{3}f_3)f_{k-3}. $$ I want to obtain ...
0
votes
0answers
128 views

Some feedback on the sequence $ a_n=a_{n-1}+4\phi_n $

This sequence is present at OEIS A171503. There, Jacob Siehler explains how this sequence correspond to the number of matrices with determinant one and how this number grows as we allow to vary in ...
3
votes
2answers
42 views

Is there a way to rewrite this recursive function so that it can be calculated in linear time?

I have this recursive function: $$ f(0)=f(1)=1 \\ f(x)=\sum_{i=0}^{x} f(i)×f(x-1-i) $$ The sequence turns out to be $1,1,2,5,14,42, \dotsc$ I want to be able to calculate the nth element ...
3
votes
1answer
60 views

Infine Sequence ${1, 3, 2, 3, 1}$

I have an infine sequence where at the end of which the ones are written. Then till infinity we shall do the next procedure: for each segment with ends a and b (inside which the numbers are absent) we ...
0
votes
1answer
294 views

Primitive Recursive on Some Functions?

We took an entrance exam on Set and Complexity Course, The question says: if $g$ be a primitive recursive, $1)$ $f_1(0)=c_1, f_1(1)=c_2, ...
1
vote
0answers
66 views

generating function and one recurrence sequence? [duplicate]

what is the generating function for sequence {$a_n$}$_{n \geq 0} $ which defined by $a_0=0$ and $a_n=\frac{1 \times 5 \times ... \times (4n-3)}{1 \times 2 \times ... \times n}$ $(n \geq 1)$. This ...
11
votes
3answers
1k views

Is there a slowest divergent function?

So I've been playing around with some functions for a while, and started wondering about a slowest divergent function(as in $\lim_{x\to\infty} f(x)\to\infty$) and so I searched around for an answer. ...
1
vote
1answer
21 views

Sequence of elements $x_i \in \bar{Q}$

I am reading about applications of Galois theory to polynomials, but when using it for a degree 5 polynomial I got confused by the following: I need to show that any sequence of elements $x_i \in ...
1
vote
3answers
87 views

writing a recursion relation to a matrix

I have a recursion relation in the form of the following two equations: $X_{t+1} = X_t + V_{t+1} \\ V_{t+1} = wV_t + cy(g-X_t)$ I want to write these two equations into a matrix form so that I can ...
0
votes
2answers
43 views

Given that fib(n)=fib(n-1)+fib(n-2) for n>1 and given that fib(0)=a, fib(1)=b (some a, b >0)

Given that fib(n)=fib(n-1)+fib(n-2) for n>1 and given that fib(0)=a, fib(1)=b (some a, b >0) which of the following is true? fib(n) is : Select one or more: a. O(n) b. O(n^2) c. O(2^n) d. ...
1
vote
3answers
40 views

Given that $f(n)=3f(n-1)-2f(n-2)$ for $n>1$ and given that $f(0)=0$, $f(1)=1$, what is $f(10)$?

I understand how to work out this question using brute force (manually substituting the numbers in) was just wondering if there was a faster and less tedious way of doing this question.
-2
votes
1answer
77 views

2010 local contest questions on recurrence relation?

How we can solve this recurrence relation: $T(n)= 2^{log_{2}3} T(n/2)+ n \sqrt {n} $ anyone could help me this difficult question, that mentioned in 2010 local contest?