The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
3answers
37 views

Finding a recursive formula for a number

I am trying to find a recursive formula for a given number in order to solve a problem I am working on. For every $n \in \mathbb{N} \setminus \lbrace 0,1 \rbrace$ we define the number ...
2
votes
2answers
53 views

Fixed point combinator and functions with no fixed point

In lambda calculus the fixed point combinator is defined as: It is very easy to see how $Yg =g(Yg)$ for any $g$ by using $\beta$-reduction. At the same time I wonder what is the meaning of ...
1
vote
0answers
37 views
+50

Recurrence vs Recursive

Say team 1 is studying the recursive characteristics of a function. Team 2 is studying the recurrent characteristics of the same function. Are the 2 teams studying the same thing? I have found for ...
0
votes
0answers
10 views

How to model equation system involving recursion?

It is trivial to solve for the "chocolate wrapper" problem using a computer, and a loop: Little Bob loves chocolates, and goes to a store with \$N in his pocket. The price of each chocolate is ...
0
votes
0answers
11 views

Recursion, Induction, and Vinogradov Notation

I have a recursion relation $$ S(x, p_{n+1}, k) = S(x, p_n, k) - c(p_n) S\bigg(\frac{x}{p_n}, p_n, k p_n\bigg) + S\bigg(\frac{x}{p_n^2}, p_n, k p_n^2\bigg) \quad $$ where $c(l)$ are constants such ...
1
vote
2answers
45 views

Structural Induction help

Give a recursive definition of the set of bit strings that contain twice as many 0s as 1s. please any guidance would be appreciated this is a hw problem.
2
votes
1answer
20 views

prove a recursive function by induction

I have a homework assignment that requires me to prove a recursive function through induction. It seems like that I am stuck on simple algebraic properties and I can't figure it out... If you can, ...
1
vote
0answers
14 views

Recursive relation-Theta notation

Consider the recursive relation: $$T(n)=T(an)+T((1-a)n)+cn$$ where $0<a<1$ and $c>0$ are constants(independent of $n$).Show that $T(n)=\Theta(n \lg n)$ That's what I have tried: We ...
0
votes
1answer
38 views

Find Recurrence Relation of Code

Suppose A(n) be the number of stars that wrote with the following example. for n>=3, i want calculate the recurrence relation for this code. any idea or solution? ...
4
votes
0answers
41 views

One Simple Code and Problem on Running [closed]

My Stackexchange friends, would you please show the following code how manipulate the n-elements array A?
1
vote
1answer
21 views

Time Complexity of one Challenging Example

Anyone would help me to calculate the order (time complexity) of this example ?
1
vote
1answer
39 views

Number of strings of size $k$ that do not have 'ab'

Consider $\Sigma = \{a,b,c\}$ and the language $L$, the set of all strings that do not contain 'ab' Find strings, of size $k$ is in $L$ ($L_k$) Consider $A_k$ (strings of size $k$ that end in $a$) ...
0
votes
0answers
42 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}$ ...
5
votes
2answers
166 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
36 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
46 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
42 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
37 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
58 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
8 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
43 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
31 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
70 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, ...
1
vote
2answers
55 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
52 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
70 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
39 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
40 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
93 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
33 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
44 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
51 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
92 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
22 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
55 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
32 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
40 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
31 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
33 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
17 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
20 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
59 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
14 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
33 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
28 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 ...
2
votes
3answers
195 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 ...