Recursion is the process of repeating items in a self-similar way. A recursive definition (or inductive definition) in mathematical logic and computer science is used to define an object in terms of itself. A recursive definition of a function defines values of the functions for some inputs in ...

learn more… | top users | synonyms

0
votes
5answers
55 views

Recursive formula - alternating addition and suntraction

So i got this formula that basically does this: $$f(n) = n^2-(n-1)^2+(n-2)^2...$$ until it gets to $f(1)$ which is $1$. The recursive form is: $$f(n)=n^2-f(n-1)$$ So is there a way to get to the ...
1
vote
2answers
53 views

Converting Recursive Function into Closed/Explicit Form

so I have this recursive function here: $\forall n>1,f(n) = 2(f(n-1)) + n-1$, (where it is $0$ when $n$ is less than $1$) So I have tried to use iteration for this but it just gets more ...
0
votes
1answer
43 views

A question about numbers with a certain property

Find (if exists) a subset of the non negative integers $X$ such that for every non negative integer $n \in \mathbb{N}\cup\{0\}$ there is exactly one solution of the form $a+2b=n$ with $a,b \in X$ I ...
1
vote
2answers
32 views

Recurrence problem with a game of probability [duplicate]

Fair coin flipping (50% on both sides) $P_1$ and $P_2$ plays a few games of fair coin flipping. Assume player $A$ starts with $x$ coins and player $B$ with $y$ coins. Let $P_n$ denote the ...
2
votes
5answers
29 views

Solve recursion with constant added

I have the following problem: Define a sequence $(a_n)$ where $a_1 = 4$ and $a_n = 4a_{n-1} - 4$. Find a closed form for $a_n$. So basically I usually know how to deal with recursions like $a_n = ...
0
votes
3answers
41 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 ...
3
votes
3answers
144 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 ...
3
votes
1answer
173 views

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
59 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
16 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
59 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
59 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
17 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 ...
-1
votes
1answer
72 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? ...
0
votes
1answer
31 views

Time Complexity of one Challenging Example

Anyone would help me to calculate the order (time complexity) of this example ?
1
vote
1answer
43 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
50 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
213 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
38 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
58 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
50 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
47 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
68 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
16 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
49 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 ...
0
votes
1answer
69 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: ...
0
votes
4answers
102 views

How do I prove convergence of the recursive sequence $c_n = c_{n-1} + \frac{0.01}{n}$?

I have this sequence: $c_n = c_{n-1} + \frac{0.01}{n}, \ \ c_1 = 0.01$ How do I prove the convergence of this, and what is the limit? Context I was trying to solve the problem of a snail crawling ...
8
votes
1answer
80 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
votes
2answers
180 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 ...
0
votes
1answer
63 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 ...
-1
votes
1answer
91 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 ...
1
vote
1answer
48 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
154 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
37 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
50 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
44 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 ...
3
votes
2answers
97 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
31 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
24 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
74 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
39 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
1answer
54 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. ...
1
vote
1answer
38 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
43 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
23 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
29 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
69 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
36 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
17 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
35 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.