The recursion tag has no wiki summary.
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 ...
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$?
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 ...
3
votes
1answer
150 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 ...
3
votes
1answer
142 views
Is there any way to solve recurrence equations with variable coefficients?
So far I have done some problems that are best solved using generating functions. These mostly contain variable coefficients.
A simple one is $H(n) = (n+2)H(n-2)$. I have found solutions to these ...
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 ...
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 ...
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 ...
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 ...
5
votes
0answers
80 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.
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 ...
3
votes
0answers
171 views
Can every recursive formula be expressed explicitly?
I'm not sure if my wording is entirely correct, but I was just wondering if every recursive formula can be turned into an explicit formula.
I am asking this because various sources online gives me ...
2
votes
0answers
13 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 ...
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 ...
1
vote
0answers
48 views
Defining things in a non-recursive manner
In this question I asked, if it was possible to define certain functions without the use of the recursion theorem. The answer, among other things, indicated that it theoretically would be possible, ...
1
vote
0answers
38 views
Indeterminacy in second degree equations of Spencer-Brown's “Laws of Form”
I am trying to follow G. Spencer-Brown's argumentation regarding 'Equations of the Second Degree' in the Laws of Form.
He shows how infinitely growing self-referential forms can be created by using a ...
1
vote
0answers
101 views
1s surpassing 0s in binary strings of odd length
Let $A(k)$ be the number of distinct binary strings of length $2k+1,$ for which the number of $1$s surpasses the number of $0$s for the first time at digit number $2k +1$, i.e., in the final digit in ...
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
0answers
48 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 ...
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$ ...
0
votes
0answers
193 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 = ...
0
votes
0answers
95 views
Variation of Josephus problem.
This is a question spoj question.
http://www.spoj.com/problems/WTK/
Instead of a fixed jump(ex: 2), if I have it incrementing , 2,3,4,5.. then how can I calculate the required recursive formula?
0
votes
0answers
93 views
Probably easy recursion formula solving $x^x=a$
Let $a,x_0\in\mathbb{C}$ and set $$ x_{n+1}=\sqrt{x_n\cdot \sqrt[x_n]{a}}$$
For which $a$ and $x_0$ does $x=\lim\limits_{n\rightarrow\infty} x_n$ exist with $$x^x=a$$
Approximating it with a computer ...
