The recursion tag has no wiki summary.
1
vote
2answers
21 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 ...
2
votes
0answers
11 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
36 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 ...
1
vote
1answer
39 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
31 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
71 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
353 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?
$$ ...
3
votes
1answer
206 views
Sets $f_n\in A_f$ where $f_{n+1}=f_n \circ S \circ f^{\circ (-1)}_n$ and operator $\alpha(f_n)=f_{n+1}$
Let's start with a function on the Reals (in this case for $x=0$ is not defined): for example $f(x)=b/x$, $x \in \mathbb R$
I define:
$$f_0:=f$$
$$f_{n+1}:=f_n \circ S \circ f^{\circ ...
0
votes
2answers
40 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
37 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
75 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
42 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
34 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
91 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
38 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 ...
