The recursion tag has no wiki summary.
1
vote
3answers
41 views
Solve recurrence equation
Could you Show me how to solve this equation:
$$x_n = \sqrt2x_{n-1} + \sqrt3$$
for $n \ge 1$ with $x_0 = 1$.
3
votes
1answer
72 views
Are hyperoperators primitive recursive?
I apologize if this question is too basic. I have read that the Ackerman function is the first example of a computable but NOT primitive recursive function. Hyperoperators seem to be closely related ...
1
vote
1answer
53 views
Solving Recursions like this
How can i solve this equation? I am really stuck
$T(n) = T(n + 1) + T(n + 2) + 3n + 1$
$T(0)=2$
$T(1)=3$
3
votes
0answers
37 views
Order of Recursion?
Define an extended algebraic function f(a) as a function on a that utilizes any combination of recursive extensions and inversions of sequentiation. Example:
a + 1 = sequentiation. a + a = addition ...
1
vote
0answers
30 views
Reasoning about a recursive function
First of all, I am a computer science student, not a maths student. So maybe this is a trivial question, I just would like to understand it :)
Suppose I have the following (pointless) recursive ...
0
votes
1answer
21 views
Recursive Definitions with Converse
I think I know how to solve i. and ii., but not iii:
Base Case: $(0,0) \in S$
Recursive Step: If $(a,b)\in S$, then $(a+1,b+2)\in S$ and $(a+2, b+1)\in S$.
(For i and ii): Prove that if $(a,b) \in ...
1
vote
2answers
27 views
Recursive formulae involving a linear operator
Given a basis $e_{1}$, $e_{2}$ in the plane, define the linear operator $F$ as $F(e_{1})=3e_{1}+e_{2}$ and $F(e_{2})=e_{2}$. Furthermore, define the sequence $u_{1},u_{2},\dots$ of vectors in the ...
1
vote
2answers
21 views
Simple recursive equation sub-solution.
I have tried to solve a very simple recursive equation:))), but I don't know what's wrong with my brain but I got other solution when I partially solve the equation.
Equation: $$T(n) = (n+2) + ...
1
vote
2answers
30 views
help in solving a recursion
EDIT: Turns out that the given solution has an error in it.
I have the following recursion question and following that is my answer. The problem is it doesn't seem to agree with the marking scheme. ...
2
votes
0answers
14 views
Repertoire method for solving recursions
I am trying to solve this four parameter recurrence from exercise 1.16 in Concrete Mathematics:
$g(1) = \alpha;$
$g(2n+j) = 3g(n) + γn + β_j$ : j = 0,1 and n >= 1
I have assumed the closed form to ...
0
votes
2answers
37 views
Equation of a curve whose difference in ordinate values form an arithmetic sequence
I have the following recurrence equation that I have obtained while trying to solve a problem:-
$$T(0) = 1$$
$$T(n) = T(n-1) + 9n - 8: n \ge 1$$
The values of $T(n)$ for $n = 0,1,2,... $ are as ...
3
votes
1answer
153 views
Recursively Solving a Bellman Equation
Problem Overview
I am to figure out $v_\pi$ of a certain Markov state.
Given Information
A set of actions, $a$ containing ${up, down, left, right}$
$v_\pi(12), v_\pi(13), v_\pi(14)$ (I am given ...
1
vote
1answer
42 views
Recursive algorithm correctness: problem.
Considering that to prove a recursive algorithm we should refer to mathematical induction. Given the following algorithm (which sort an Array of size r) I found that base cases are for array size of 0 ...
2
votes
4answers
41 views
Iterative recurrence.. Iteration method
Here is the Equation and how far I got into solving this problem using the iteration method:
$$T(1) = 8 \\
T(n) = 3T(n-1) - 15$$
Iterations:
$i=1, $
$$T(n) = 3(3T(n-2) - 15) -15$$
$i=2, $
$$ ...
6
votes
1answer
91 views
Primitive recursive function which isn't $\Delta_0$
What is the simplest/cutest example (and/or example with the most student-friendly proof that it is an example) of a primitive recursive function which isn't representable by a $\Delta_0$ wff?
9
votes
5answers
367 views
Evaluating tetration to infinite heights (e.g., $2^{2^{2^{2^{.^{.^.}}}}}$)
The Problem
How can you evaluate (i.e., get a value for) Tetration (i.e., iterated exponentiation) to infinite heights?
For example, what would be the value of this expression?
$$ ...
0
votes
2answers
44 views
How to derive a closed form of a simple recursion?
Consider: $$T(n) = 2 T(n-1) + 1$$ with $T(1)$ a positive integer constant $a$.
I just stuck in finding a closed form for this simple recursion function. I would appreciate it, if someone gives me a ...
1
vote
2answers
42 views
How to find an explicit formula for $d _ k$
Consider sequence $ d _ 1, d _2, d_3 $
$$d_k= \frac {d_{k-1}} {k + 1} $$ for all integers $k \ge 2 $ with the initial condition that $ d_1 = 1$.
Find an explicit formula for $d_k$ for the $k^{th}$ ...
5
votes
0answers
81 views
undecidability of the structure $(\omega,+,2^n)$
Is the structure $(\omega,+,2^n)$ undecidable? There is no easy way to define multiplication using a formula.
0
votes
1answer
43 views
Recursion questions
Let $M$ be a set, $e\in M$, and $F:M\rightarrow M$. Define $r$ on $\mathbb{N}$ by $r(0)=e$, and, for all $k$, $k\in \mathbb{N}$, $r(s(k))=F(r(k))$.
Assume that $F$ maps $M$ $1\text{-}1$ and onto ...
0
votes
0answers
36 views
a problem in understanding the proof of recursion theorem ?
there is some problem in understanding the proof of recursion theorem in the text , mathematical introduction to logic by enderton page 44 ,
we have a set U and a subset B of U and C is the subset ...
0
votes
3answers
108 views
Proof by induction for a recursive function $F(n) = F(n–1)+F(n–2)$
I'm having a lot of trouble with the following homework question:
Consider the following recursive function:
Base Case: $F(0) = 0,F(1) = 1$.
Recursive Step: $F(n)=F(n−1)+F(n−2)$ for all ...
0
votes
0answers
50 views
How do I apply floor( ) and ceiling( ) to a log(x) correctly?
I am attempting to work out, by using a manual method, how to apply the floor() and ceiling() functions to log2(2096) (2096 is used as an example).
My understanding is this (and I am very much a ...
1
vote
1answer
59 views
Establishing formula from recurrence
Can anyone tell me how do we establish a formula from a given recurrence relation?
Take the example of $f(n) = 2f(n-1) + 1$, $n \in \mathbb{Z^+}$, $f(1) = 1$
When I write out the first few values, it ...
0
votes
1answer
50 views
Combinatorial Recursion
Define a recursion that gives the number of sequences that include the numbers $0,1,2,3$ with an even number of $1$'s and an even number of $0$'s.
So far I got $$a(n) = 2a(n-1) + 2a(n-2)$$ which ...
0
votes
0answers
41 views
Combinatorial Recursion 2
Define a recursion $a(n,k)$ that gives the number of ways to choose $n$ items out of $k$ types of items, with the condition that we must choose $2, 4$, or $6$ items of each type.
So $2p+4q+6r = n$ ...
3
votes
3answers
53 views
How to get from $1 + (-1)^{n+1}$ to $1 + [((−1)^{n }) − 1] (−1)$
I need some help with the algebra here.
I have the following explanation, and I really can't follow the algebra. Could you also maybe give me some tips on how to think about such problems.
$a_n = 1 ...
0
votes
1answer
39 views
Bounded recursive sequence
I would like to know if there are known bounded recursive sequence (non monotonic):
It shouldn't be a constant, neither a convergent sequence, nor a periodic one.
(I am not asking for a true random ...
2
votes
3answers
58 views
Closed form for $T(n) = n(T\left(\tfrac {n}{2}\right))^2$
I am trying to find a closed form for the following: $$T(n) = n(T\left(\tfrac {n}{2}\right))^2$$, with $T(1)=1/3$.
I set $T(n)=T(2^m)=S(m)$ and then transformed the range of $S(m)$ to set ...
4
votes
3answers
58 views
How to solve infinitely nested logarithms
I have an iterative process that starts with
$$x_1 = \log_{10}(a)$$
Following iterations are as follows:
$$x_2 = \log_{10}(a-b\cdot x_1)$$
$$x_3 = \log_{10}(a-b\cdot x_2)$$
$$x_4 = ...
0
votes
2answers
65 views
Give a recursive definition with initial condition…how did they get the answer?
The function $f (n) = 5n + 2, n = 1, 2, 3, \ldots $
Im sure its a simple problem, but im really confused...how did they get the answer ? could someone explain
$f (n) = f (n - 1) + 5, f (1) = 7$
...
2
votes
2answers
40 views
Asymptotic bound $T(n)=T(n/3+\lg n)+1$
How would I go about finding the upper and lower bounds of $T(n)=T(n/3+\lg(n))+1$?
4
votes
2answers
115 views
A Recurrence Relation Involving a Square Root
Consider the recurrence relation:
$a_{n+1} = \sqrt{a_n^2 -k},$
where $k>0$, $n\in\{0,1,n:a_n^2\geq k\}$, and $a_0>0$ is known.
Is it possible to obtain an expression for $a_n$ in terms of ...
0
votes
1answer
113 views
completeness and creative
I'm trying to show that any complete $\Sigma_1^0$ set is creative.
The definition of creative I understand is: if there is a total recurvise function f s.t. f(e) is an element of A iff f(e) is an ...
1
vote
1answer
109 views
Derive recursion formula for an integral
Im having trouble understanding questions involving deriving a recursion formula.
I need to derive the recursion formula for $I_n$ where $n>=2$ $$I_n = \int(x^2-1)^n dx$$
The other questions ive ...
0
votes
1answer
65 views
Computing functions from generating functions
I am new to generating functions but understand how to derive them from given discrete numeric functions. Is there a simple way to derive the discrete numeric function given a generating function. For ...
0
votes
1answer
53 views
Rolling 5, 6 sided dice where top 3 equal 15. How many rolls? How in Recursion?
Let's say that I have 5 (n), 6-sided (d) normal dice. How would I figure out how many possible rolls there are, where the top 3 (k) numbers rolled, equal 15 (t)? How would I do this using recursion ...
2
votes
1answer
54 views
Are the brackets in formal box notation of recursive functions omittable?
So we know all recursive functions can be expressed as a finite sequence of symbols for the basic functions and processes composition, primitive recursion, and minimization. What I'm wondering is if ...
3
votes
1answer
57 views
Give a combinatorial proof of the recurrence relation
Let $F_n$ be the number of forests on the vertex set $V = \{1,2,\ldots,n\}$(Thus we are counting labelled forests). Give a combinatorial proof of the recurrence relation
$$F_n = \sum_{i=1} ...
4
votes
1answer
95 views
Issue while applying Master Theorem
I've read about the master theorem for solving recurrences in Introduction to Algorithms, but have a problem (probably, due to misunderstanding) while applying it in some cases. For example, having ...
1
vote
2answers
58 views
Guidelines for Obtaining Recursive Equations?
I'm trying to teach myself some combinatorics, and at the moment, I'm having a hard time coming up with recursive equations. It seems to come naturally to some people, and I'm hoping that my skills ...
1
vote
2answers
78 views
Recursive relation using successor function
What is the recursive relation for $$H(m)=2^{(m^2)}$$ using successor function recursive relation for multiplication: $$mult(x,0)=0; mult(x,S(y))=add(x,mult(x,y))$$ recursive relation for addition: ...
0
votes
0answers
195 views
Recursive definition for $S = \left\{{(a,b) \mid a \in \mathbb{Z}^+, b \in\mathbb{Z}^+ \text{ and } a + b \text{ is odd}}\right\}$
Give a recursive definition of each of these sets of ordered pairs of positive integers. [Hint: Plot the points in the set in the plane and look for lines containing points in the set.
$S = ...
1
vote
1answer
51 views
Solve recurrences by obtaining a θ bound for T(N) given that T(1) = θ(1)
$T(N) = N + T(N-3)$
This is what I got so far
$$\begin{align}&= T(N-6) + (N-3)+N\\
&= T(N-9) + (N-6) + (N-3)+N \\
&= T(N-12) + (N-9) + (N-6) + (N-3)+ N\end{align}$$
I think I should use ...
3
votes
7answers
257 views
Find the nth term of a recursive sequence
I have a the following sequence:
$$\begin{gather}
a_1 = 3 \\
a_{n + 1} = 1 + \frac{a_n}{2}
\end{gather}
$$
How can I find the $a_n$ term?
0
votes
0answers
22 views
Using the substitution method prove that T(n) = T(n - 1) + Theta(n) is Theta(n^2) [duplicate]
Possible Duplicate:
I need to prove the following by using the substitution method -> $T(n) = T(n - 1) + \Theta(n)$ is $\Theta(n^2)$
The title is pretty much self explanatory. How can I ...
0
votes
3answers
262 views
Find a formula for a sequence of number
A sequence starts at $n=1$: $\{1, 4, 13, 40, 121, 364... \}$.
Find an explicit formula that generates these numbers.
Thanks a lot!
1
vote
1answer
102 views
Representing Recursion and Primitive Recursion diagrammatically
I'm interested in how Recursion, and Primitive Recursion, could be represented diagrammatically. It occurred to me that this would be a good way of seeing the difference. Also, I'm interested in how ...
3
votes
3answers
59 views
Explanation of the recursion for number of surjections
I have a question about the recursion of the number of surjections from $\{1,\ldots,n\}$ to $\{1,\ldots,k\}$: $$\mathrm{Sur}(n,k) = k \cdot \mathrm{Sur}(n-1,k-1) + k \cdot \mathrm{Sur}(n-1,k).$$
My ...
4
votes
1answer
93 views
