Tagged Questions

The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
0answers
47 views

Arithmetic Turing machines

Consider the family $T_{1}$ of Turing machines with two tape symbols $b,1$ ($b$ the blank symbol). The family $T_{1}$ is Turing complete. Identify the tape with $\mathbb{Z}$ and let $0\in \mathbb{Z}$ ...
6
votes
2answers
188 views

Does anyone recognise this recursion sastisfied by the Bell numbers?

I derived a recursion $$B_n=\frac{1}{n}B_0+\frac{1}{n}\sum_{k=1}^{n-1}\left[\binom{n}{k}-(-1)^{n-k}\binom{n}{k-1}\right]B_k\tag{$*$}$$ which I know should be satisfied by the moments of the unit ...
3
votes
2answers
37 views

Number of $1$s in the binary representation of $n$

Trying to define the function $b(n)$ which counts the number of $1$s in the binary representation of $n$ arithmetically I came up with the following definition: $$b(n)=m :\equiv (\exists k_1\dots ...
1
vote
1answer
51 views

Problematic Initial Condition of a Recurrence Relation

I encountered this equation, and tried to solve it: $T(n) = T(\sqrt{n})+log(n)$ Under the initial condition T(1)=1. Can someone tell me why is this initial condition helpful? I mean, of course ...
0
votes
1answer
43 views

Use the recursive definition, $f(k) + k² + 2k -3$, to prove that, for any $n ∈ \Bbb N,\ f(n) = n² - 4$.

Here's what I have so far: Let $f: \mathbb{N} - \{1\} \to \mathbb{N}$, such that $f(x) = (x+2)(x-2)$. Formulate a recursive definition for $f$ including both the base case $f(2) = 0$ and a ...
0
votes
1answer
44 views

Hanoi Algorithm With Different Nodes

http://en.wikipedia.org/wiki/Tower_of_Hanoi I need help developing a Hanoi algorithm which follows the same rules as the standard game, however the nodes that are transversed is different. In this ...
0
votes
4answers
61 views

Formulating a recursive definition

Let Σ(k) = 1 + 3 + 5 + ... + (2k+1) be the sum of all odd natural numbers from 1 up to and including (2k+1). Formulate a recursive definition for Σ including both the base case Σ(0) = 1 and a (k+1)th ...
0
votes
0answers
13 views

What is an extragradient method?

I've searched Google, but it seems that only research journal papers appear in search results, where some new, improved, or specialized extragradient method is discussed. I've also searched Wikipedia ...
2
votes
3answers
44 views

How to solve this recursive equation?

I've got this recursive equation: $$ T(n) = \begin{cases} 2, & \text{if $n = 2$} \\ 2T(n/2) + n, & \text{if $n = 2^k$ where k > 1, $k \in \mathbb{N} $} \\ \end{cases} $$ I know I should ...
2
votes
1answer
45 views

Recurrence relation from code

My Friends, Hi, I see an old book in mathematics for computer science. everyone could help me, for example how we calculate the order (Time complexity) of following code: ...
8
votes
1answer
75 views

Prove that $a_n$ is a perfect square if $n$ is even without generating functions or Taylor series.

Let $a_n$ be the number of positive integers whose digits are all $1$, $3$, or $4$, and add up to $n$. For example, $a_5 = 6$, since there are six integers with the desired property: $41, 14, 311, ...
2
votes
2answers
133 views

Solving a recurrence relation with square root

I ran into a bad recurrence relation. Anyone would calculate T(n) or add some hint? $$T(n) = \begin{cases} n,\quad &\text{ if n=1 or n=0 }\\ \sqrt{1/2[T^2(n-1)+T^2(n-2)]+}n ,\quad ...
2
votes
1answer
60 views

Height of Recursion Tree for $T(n, k) = T(n/2, k) + T(n, k/4) + kn$

If we use a recursion tree for solving $$\begin{cases} T(*,1)=T(1,*)=a \\ T(n,k)=T(n/2,k)+T(n,k/4)+kn \end{cases}$$ What is the height of the recursion tree? Any idea or solution highly ...
0
votes
1answer
84 views

Solving the recurrence relation $T(n)=4T\left(\frac{\sqrt{n}}{3}\right)+ \log^2n$

How we calculate the answer of following recurrence? $$T(n)=4T\left(\frac{\sqrt{n}}{3}\right)+ \log^2n.$$ Any nice solution would be highly appreciated. My solution is: $n=3^m \to ...
3
votes
0answers
42 views

Solving the recurrence $T(n)=4T(\frac{\sqrt{n}}{3})+ \log^2n$ [closed]

How we calculate the answer of following recurrence? $$T(n)=4T\left(\frac{\sqrt{n}}{3}\right)+ \log^2n.$$ Any nice solution would be highly appreciated.
1
vote
1answer
43 views

Recursive definitions of $n<m$, $n\mid m$, and $n \bmod m$

Without referring to the apparatus of (primitive) recursive functions one can introduce addition into the language of successor arithmetic by two additional axioms which naturally reflect the essence ...
3
votes
2answers
117 views

If a recursive sequence converges, must its inverse be divergent?

Suppose I have a recursive sequence $\displaystyle a_{n+1} = \frac{a_{n}}{2}$. Clearly, the sequence converges towards zero. Now, suppose I define an "inverse" sequence $\displaystyle b_{n+1} = ...
1
vote
1answer
35 views

find formula to count of string

I have to find pattern of count of series. Lenght of series is $2n$. It is neccessary to use exaclty double times every number in range $[1...n]$ and all of neighboring numbers are different. Look at ...
0
votes
1answer
46 views

Calculating the chance of something happening over and over again

I'm trying to calculate the probability, and potential cost on society, of people returning to homelessness after going through the system one, two, or several more times. Let's say that someone who ...
2
votes
2answers
37 views

Solving a Recursive equation, wrong options? [closed]

This is a very simple recursive formula. Are the options provided wrong? $$ T(n) = T\left(\frac{n}2\right) + 2 $$ with $T(1) = 1$. What's the solution when $n=2^k$ ($n$ is a power of $2$)? The ...
0
votes
3answers
59 views

Recursion Problem [closed]

a) Ten people are sitting in a row of ten chairs, chewing gum. Each person spits out his or her gum and places it either under his or her own chair or under an immediately adjacent chair. How many ...
3
votes
2answers
95 views

How to solve recursion?

I have tried to solve some recursion: $$f_n = \frac{2n-1}{n}f_{n-1} - \frac{n-1}{n} f_{n-2} + 1, \quad f_0 = 0, f_1 = 1$$ I would like to use a generating function: $$F(x) = ...
0
votes
0answers
26 views

Writing convergence acceleration algorithm as a recursion type formula

Cohen et al. describes an algorithm for speeding up the convergence of an alternating series as follows: Initialize: $$d=\left(3+ \sqrt{8}\right)^n; \quad d=\frac{1}{2} \left(d+ \frac{1}{d}\right)$$ ...
0
votes
2answers
23 views

given a total width and a given number of decreasing widths to fit that width, what is the % decrease

Hailing from the programming world here, maths has never been my strongest area. I have a width (TW), and that width must be divided by a given number(N) of smaller widths which decrease ...
0
votes
3answers
66 views

Finding general formula for a recursion function

If we have a recursion relation defined as $a_n = 3a_{n-1}+1$ with $a_1=1$ then find the general formula for $a_n$ in terms of $n$ with a(1) = 1. So far I have: $a_n = 3a_{n-2}+1+1 = 3a_{n-3}+1+1+1 ...
1
vote
1answer
34 views

How to simplify recursive eq?

I know how to programatically calculate this, but im not sure how it can be simplified for documentation. Can someone help? $R = (X\cdot 1) + (X\cdot 2) + (X\cdot 3) + (X\cdot 4) + (X\cdot 5) + ...
0
votes
0answers
140 views

range of one increasing computation function?

We know that that the range of any recursive partial function is recursively enumerable. Also we know the fact: Set A is recursive if and only if it is range of some increasing section partial ...
0
votes
1answer
42 views

Problems On Many-one Reducible [closed]

In computability theory and computational complexity theory, a many-one reduction is a reduction which converts instances of one decision problem into instances of a second decision problem. ...
0
votes
1answer
32 views

Closure Question in Enderton's 'Elements of Set Theory'

I am currently working on a follow-up question to the one I did here: Closure question from Enderton's 'Elements of Set-theory' I am unsure though whether I am on the right track with the ...
0
votes
2answers
38 views

Relations on set A and conditions of existence of descending chains

I am reading through the Elements of Set theory by Herbert Enderton and even though I have passed this exercise long ago,the more I look at my solution the less I believe it. Problem goes like this: ...
2
votes
1answer
19 views

Uniqueness in transfinite recursion.

Theorem of transfinite recursion: Given a well-ordered set $A$ let $\varphi(g,y)$ be a ZF formula such that for every $a \in A$ and every function $g$ with domain $I_a$ (where $I_a$ is the initial ...
0
votes
1answer
24 views

Why characteristic function is primitive recursive

I'm studying recursive functions and right now I stucked in this: "Natural numbers subset is PR if and only if characteristic function is PR". Why is that? Becouse it has values 0 ant s(0) only? So ...
0
votes
0answers
64 views

Recursion Theorem question

I am trying to prove the following in Enderton's text 'Elements of Set Theory' (exercise 8 of chapter 4): Let $f$ be a one-to-one function from $A$ into $A$, and assume that $c \in A - ran \ f$. ...
0
votes
1answer
34 views

Iterated Functions - designing iterator to converge to constant value

I came across an interesting iterated function: $$ x_n = \frac{x_{n-1}}{x_{n-1} + b} $$ This is an extremely simple example and it converges to the constant $1-b$. Can someone provide some insight to ...
2
votes
1answer
16 views

Bounds on a recursively defined sequence

I have a sequence defined by $h_0=h_1=1$, $h_2=2$ and $h_{n+1}=(n+1)h_n + \frac{n(n-1)}{2}$. The paper I'm reading claims $n! \le h_n \le 2(n!)$. It is easy to show the first inequality by induction. ...
0
votes
0answers
34 views

How to solve this recursive integral?

$$f(p)= \int_a^\infty\frac{\exp(\iota k\dot p)}{k^2 + f(k)} dk$$ I thought of solving it like if I guess $f(k)$ equals a number then after solving the integral it should be itself.
1
vote
2answers
58 views

Discrete math and recursion problem.

I was recently reading up examples on recursion and how it relates to induction and there's this question I am not sure about. Q: Let $$b_1=3$$ $$b_n=n(n+2)$$ From that question I wanted to do the ...
5
votes
1answer
108 views

Killer Tree! (one of my old questions)

There is a problem that killed me! but I couldn't solve it: We have a tree graph witch its structure is what is on image. Proof that there is no reduplicative numbers in each line.
2
votes
3answers
232 views

finding explicit formula

The question ask us to guess an explicit formula for the sequence $$y_k = y_{k-1} + k^2 ,$$ for all integers $k$ greater than or equal to 2 and $y_1 = 1$ Can someone help me with this? so far what ...
1
vote
4answers
80 views

finding explicit formula through substitution method

The question ask us to guess an explicit formula for the sequence $$t_k = t_{k-1} + 3k + 1 ,$$ for all integers $k$ greater than or equal to 1 and $t_0 = 0$ Can someone help me with this? Because I ...
1
vote
2answers
89 views

Guess explicit formula using iteration

The question ask us to guess an explicit formula for the sequence $$s_k = s_{k-1} + 2k ,$$ for all integers $k$ greater than or equal to one and $s_0 = 3$ Can someone help me with this? Because I ...
1
vote
1answer
36 views

Solving a second level functional equation over all functions $g$

I am trying to find a closed form expression $f$ such that $$f(g(x+1) - g(x)) + f(g(x) - g(x-1)) = f(g(x))$$ For all functions $g$ I have concluded that for polynomials $$2^{n+1}f(0) = f(a_0 + ...
1
vote
2answers
65 views

If a uniquness for all functions exist shouldn't there be uniquness to recursion?

What I'm specifically saying is every function is definitely unique, as they may be nearly equivalent to another function, for example. Let's make a table of values for $^{x}2$ (0,1) (1,2) (2,4) ...
0
votes
1answer
23 views

Check these recursive definitions for me?

Looking for Give a recursive definition of A) the set of odd positive integers B) the set of positive integer powers of 3 C) the set of polynomials with integer coefficients I have a. Basis: ...
2
votes
1answer
75 views

Use principle of mathematical induction to show a function defined recursively is uniquely determined.

I'm having difficulty with the following taken from "Elementary Number Theory And Its Applications" by Rosen section 1.1 questions. "Use the Principal Of Mathematical Induction to show that the value ...
1
vote
1answer
32 views

Predicting eigenvalues of bigger matrices

Consider the following $(3 \times 3)$ matrix: $K_3 = \left( \begin{array}{ccc} a & -1 & 0 \\ -1 & a+1 & -1 \\ 0 & -1 & a \end{array} \right)$ The question has a quantum ...
1
vote
1answer
22 views

Resolve a recursive series

Consider the following recursive function: $f(n) = 1 + \sum_{i=0}^{n-1} f(i)$ with $f(0)=1$ I need to derive a non recursive form. By simply trying values, I have inferred that it must be ...
1
vote
0answers
36 views

Meaning of Biinterpretability.

I'm reading this paper: http://www.math.cornell.edu/~shore/papers/pdf/hyp9.pdf and I am struggling with the meaning of Biintereptability, to quote the paper A degree structure $D$ is ...
0
votes
0answers
9 views

A question concerning the domain of function that is recursively defined.

I have a problem concerning nested functions and whether they're well-defined. I have the following definition for all $t\in \mathbb{Z}$. A function $y_t:\mathbb{R}^3\rightarrow\mathbb{R}$ such that ...
1
vote
1answer
94 views

linear recursion $y_n=A \cdot y_{n-1}$

Let $a,b, \in \mathbb{R}$. Let $x_0=a, x_1=b$ and $x_n=\frac{x_{n-1}+x_{n-2}}{2}$ for $n \geq 2$ (i) Write the recursion in the form $y_n=A \cdot y_{n-1}$ where $A$ is a $2 \times 2$ matrix and ...