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
30 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
67 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
36 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
30 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 ...
5
votes
1answer
166 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
27 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
34 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
100 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
24 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
143 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
45 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
62 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
298 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
67 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
96 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
50 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
84 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.
0
votes
2answers
62 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
56 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
20 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
49 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 ...
1
vote
2answers
44 views

Recursion, Truncation, and “coding.”

The example is "left to the reader", but I am having trouble approaching this problem. There is a primitive recursive function $tr$ such that if $s$ codes a sequence $(a_{0},...,a_{n-1})$, and $m\le ...
0
votes
2answers
82 views

How to prove what amounts of postage can be formed with normal mathematical induction?

This is similar to my other question Strong induction but it addresses standard mathematical induction. Problem: a) Determine which amounts of postage can be formed using just 4 cent stamps and 11 ...
3
votes
1answer
89 views

Does every positive rational number appear once and exactly once in the sequence $\{f^n(0)\}$ , where $f(x):=\frac1{2 \lfloor x \rfloor -x+1} $

Consider the map $f:\mathbb Q^+ \to \mathbb Q^+$ defined as $f(x):=\dfrac1{2 \lfloor x \rfloor -x+1} , \forall x \in \mathbb Q^+$ ; then is the function $g:\mathbb Z^+ \to \mathbb Q^+$ defined as ...
0
votes
0answers
13 views

Closed form of chained Stationary Functions

Consider the following operator $$D_{(a-1)x,x}\left[ f \right] = \frac{f(ax) - f(x)}{(a-1)x} $$ It's pretty easy to see that a nontrival function $g(x)$ such that $$D_{(a-1)x,x}[g] = g$$ Is given ...
1
vote
0answers
178 views

Proving a recursive algorithm as correct using induction

My objective is to give a recursive algorithm for finding the maximum of a finite set of integers, "making use of the fact that the maximum of n integers is the larger of the last integer in the list ...
1
vote
2answers
128 views

How to determine which amounts of postage can be formed by using just 4 cent and 11 cent stamps?

Problem: a) Determine which amounts of postage can be formed using just 4 cent stamps and 11 cent stamps. b) Prove your answers to a using strong induction. My work: (I am only working on part a for ...
1
vote
1answer
51 views

Showing that a set is primitive recursive.

I've been having a lot of difficulty even beginning this problem. I believe that I would have to use the min and max functions, but I'm not entirely sure how to actually write this down rigorously, or ...
2
votes
3answers
52 views

Turn iterative function into polynomial.

So, I have an iterative function that looks something like this. $$f(x_n) = (x_n + 0.08) \cdot 0.98$$ e.g. So if $n = 2$ and $x$ started at $0$, then the equation would be equal to $(((0 + 0.8) ...
1
vote
0answers
102 views

Probability of rolling n dice to match another set of dice, d, given r rolls (like yahtzee)

(Note: I will eventually code this, but i'm primarily interested in the math behind it) I'm trying to create a function in Java to calculate the probability of getting a desired outcome from n rolled ...
1
vote
0answers
40 views

Need clarification on recursive functions.

Given any function $f: \mathbb{N}_0 \rightarrow \mathbb{N}_0$ and a recursive $h:\mathbb{N}_0 \rightarrow \mathbb{N}_0$ , I know that to prove $h\circ f$ is recursive I only need to prove that $f$ is ...
0
votes
0answers
34 views

Derive the recursion relation

Consider the nonhomogeneous linear equation $y' = 2y/(1-x) + f(x)$. It is singular at $x=1$, of course, but it is regular at $x=0$ if (the known function) $f(x)$ is analytic there. Assume $y(x) = ...
-2
votes
2answers
35 views

Solve this recursion [duplicate]

\begin{cases} T(1) = 1 \\ T(n) = 2T(n-1)-4 \end{cases} Solve this recursion using summation factor method or iterative method. Could someone solve for me this recursion and explain all steps?
0
votes
1answer
39 views

Iterative Logarithm in Recurrence Relation?

Anyone Could describe me How we can solve this recurrence relation? $T(n) = T(\log n) + O(1)$ $T(1) = 1$ a) $O(\log n)$ b) $ O (\log^* n) $ c) $ O (\log^2 n) $ d) $ O (n / \log n) $ Our TA ...
1
vote
1answer
27 views

Growth Rates of F(n) vs. F(n) + F(n-1) + … F(1)

I am trying to understand growth rates between a function and its sum recursively. For example I understand that if: $F(n) = n$ Then the sum $n + (n - 1) + ... 2 + 1 = \frac{n(n-1)}{2}$ which is ...
1
vote
1answer
51 views

What does Gödel mean by “constant” relating godel definition of recursion to the modern def.

In "On formally undecidable propositions..." he writes a function is recursive if "... it is a constant or the successor function" is he referring to the constant function c(x)=k, and if so, is this ...
0
votes
1answer
37 views

recursion relations, pattern finding

I have the following recursive relations: $$ \left \{ \begin{array}{ccc} x_{t+1} &=& x_t \cdot (1-2c) + 0.5 v_t\\ v_{t+1}&=& 0.5v_t - 2c\cdot x_t \end{array} \right. $$ $c$ is just ...
1
vote
1answer
109 views

Nested recursion theorem (problem 5.21, “Notes on set theory”, Y. Moschovakis)

I found this problem in the book "Notes on set theory" by Yiannis Moschovakis; it's the x5.21 from the fifth chapter. You have to prove the following theorem: for any three functions g: ...
0
votes
1answer
41 views

Motion of a particle; direction of motion depends on location

I'm wrestling with a problem involving motion of a particle. The direction of the particle's motion is defined everywhere by a function $\mathbf G(\mathbf X)$. I keep coming down to a recursive ...
0
votes
1answer
24 views

Proofs related to counting the nodes of a recursive tree

Define Fibonacci numbers by $\text {Fib(n)} = \begin{cases} 0 & \text{if $n = 0$} \\[2ex] 1 & \text{if $n = 1$} \\[2ex] \text {Fib(n - 1) + Fib(n - 2)} & \text {otherwise} \end{cases}$ ...
0
votes
2answers
88 views

Finding the formula for nth term of a sequence

I have the following recursive sequence an i want to find the general formula for the nth term of a sequence: $$a_{n+2}=4a_{n+1}+4a_n,a_1=1,a_2=2$$ I have the following characteristic equation: ...
0
votes
2answers
29 views

Recursive sequences general term

Find general term for nth term of the sequence $$a_{n+2}=a_{n+1}+a_n+n^2, a_1=1, a_2=2$$ How to approach this type of questions? I am looking for a specific answer but also more general insight about ...
1
vote
3answers
35 views

Recursive relationships for ternary strings

If one were to have a ternary string with no repetition of consecutive $0$'s or $1$'s how would you define the recursive relation? The first way I tried to solve was to assume $2$ was the last digit ...
1
vote
1answer
65 views

Define recursive function prefix.

I need to define a recursive function, over strings, prefix in that way $\mathrm{prefix}(x,y) = \mathrm{true}$ if $x$ is prefix of $y$. This is my approach so far: $\mathrm{prefix}([ ],y) = ...
1
vote
2answers
58 views

Help proving a recursive formula involving planes and lines

Suppose that $n$ lines are drawn on a plane in such a way that no lines are parallel and no three of them intersect at a point. Let $r_n$ be the number of regions in the plane is divided into after ...
1
vote
1answer
73 views

Counting Regions when cutting a circle (recursion)

Let m≥1 and n≥1 be integers. Consider m horizontal lines and n non-horizontal lines such that no two of the non-horizontal lines are parallel, no three of the m+n lines intersect in one single point. ...
3
votes
2answers
99 views

$ T(n)= T(\log n)+ \mathcal O(1) $ Recurrence Relation

what is the solution of following recurrence relation? $$\begin{align} T(1) &= 1\\ T(n) &= T(\log n) + \mathcal O(1) \end{align}$$ a) $O(log n)$ b) $ O (log^* n) $ c) $ O (log^2 n) $ d) $ ...