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
1answer
28 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 ...
1
vote
0answers
30 views

Solving 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: ...
2
votes
0answers
15 views

Enumerate k part of n (and keep the list) [on hold]

I'm starting to understand the problem and how it is resolve. I do understand the n-1 and k-1 part whereas ...
1
vote
4answers
86 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
42 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
16 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
70 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
41 views

Binary strings and recurrence relations [on hold]

How could we possibly figure this out if there are an infinite number of sequences that could be generated? Could someone please solve this problem and explain what is going on at each step? Thank you ...
0
votes
2answers
49 views

Complexity of given recurrence [on hold]

I need to find an upper bound for the function T defined by the following relations: $T(1) = 1$ $T(n) ≤ 34 · T(n/17) + 17n$ Answer need to be tight up to $O(1)$ factors. Please help to solve this ...
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
67 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 ...
-4
votes
0answers
35 views

Explicit formula from this recursive formula? [closed]

Is there an explicit function for the following recursive function? $a_n = a_{n-1}\cdot(n+1) + n!\cdot n$
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
25 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
17 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
26 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
58 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
52 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
23 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
139 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
37 views
0
votes
1answer
20 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
57 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
114 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
58 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
289 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
65 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 ...
10
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
86 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
42 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
38 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
75 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?
-1
votes
2answers
207 views

one recurrence relation with generating function

what is generating function for {$a_n$}$_{n \geq 0} $ sequence that 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)$. ...
0
votes
2answers
58 views

recurrence formula for number of decimal numbers with some restrictions

I ran into a Olympiad Question that so difficult, if $a_n$ be the number of decimal numbers with length $n$ that has no $0$ in the digits and also has not any combinations $11,12,21$, I want to find ...
0
votes
1answer
51 views

Proving Reversal of a Language in Recursive Way

We define the $reverse$ of a string as follows: $(x_1x_2...x_n)^R=x_nx_{n-1}...x_1$ where $x_1,x_2,...,x_n \in \Sigma$. We can also define the reverse of a language by $L^R= \lbrace s' | \exists s ...
0
votes
0answers
19 views

Is this recursive?

I came across this formula in a neuroscience journal: $x = [sigma(y - z)] - w$ where: $z = a + \max(x)$ My question is, can you solve for $x$ if $x$ is a constituent of $z$?
3
votes
0answers
46 views

Conway's Game OF Life maximum periods on a set x by x game board.

I have taken interest in Conway's Game of Life and want to know if you guys can help me with a mathematical problem :) That is what this website is for right? You need to be familiar with the rules ...