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
1answer
37 views

Recursive Definitions

I have two recursive definitions that I need to determine if they are correct. The first one is: The set S of all positive integer multipliers of 5 can be described by the following recursive ...
3
votes
0answers
33 views

Is math recursive or iterative?

Is the process of solving a mathematical problem (algebraic equations, limits, derivatives, integrals, EDOs, trigonometric identities proof) recursive or iterative? For example, for solving $x=1+2+3$ ...
0
votes
1answer
16 views

Iterated Function System for Cosine

So, if we let $f_1(x) = 2x^2-1$ and say $f_{n+1}(x) = f(f_{n}(x))$ then some graphing and experimenting seems to indicate that $\lim_{n\to\infty} f_n(2^{-n}x) = \cos(x)$. They converge pretty quickly ...
0
votes
1answer
33 views

How to define a set of trees recursively?

In particular, consider the set of integer-labelled binary trees (T). How could this set be defined in a recursive way from $\mathbb Z$ and T itself? Examples: $(-2, 1, (3, 1, 0)) \in T$ $(-1, (7, 2, ...
1
vote
1answer
22 views

Troubleshooting Textbook: Using Generating Functions for Non-Homogenous Recurrence

I am learning about Generating Functions to solve non-homogenous linear recurrences, and I can't seem to get the right solution, no matter what I do. Also, the example I have to work off of in the ...
0
votes
1answer
25 views

Need help finding general formula for an iterative equation.

If we have a iterative equation defined as for $i=1:n$ $$a=a(4-a),$$ I need help finding the general formula for this in terms of n. I know some obvious ones like, $$n=1\quad\quad a=4a-a^2$$ $$n=2 ...
0
votes
2answers
43 views

Prove a Recursive Formula by Induction?

So I have a bonus question on a homework assignment I am working on that literally just asks "How would you prove a recursive formula by induction?" There are no numbers, or sequences given. I ...
0
votes
1answer
26 views

Do I have these recursive and closed forms correct?

For the sequence: $0,1,5,12,22,35,51,70,92,117,145,176$ I have the closed form (dashes indicate subtext): $$a_n=\frac{n(3n-1)}{2}$$ For recursive: $$a_{n+1}=\frac{a_n+3n^2+5n+2}{2}$$ If they are ...
0
votes
1answer
13 views

given an integer i and a range r of real numbers, i divides ranges exactly in half sequentially, where does i split the next r? (without recursion)

Say I have a range r from a - b, $a\in \mathbb{R}$ and $b\in \mathbb{R} $. Then, I have an integer i. Now, if I were to break the range in half, decrease i, then continue breaking the remaining ...
1
vote
1answer
52 views

Material with half-life that is being added to periodically

I am having trouble calculating this problem: $X$ amount of material with $Y$ half-life is administered on a patient. When an interval of time $=A$ elapses, ( as a given fraction of half-life) an ...
8
votes
2answers
155 views

Find Nth formula of recursive formula $a_n=a_{n-1}+n(n-1)a_{n-2}$

$$a_n=a_{n-1}+n(n-1)a_{n-2}$$ $$a_0=1, a_1=-\frac{1}{2}$$ Is it possible to find explicit formula for $a_n$ just by using $a_0$ and $a_1$? I know how to solve this problem if $a_n=Aa_{n-1}+Ba_{n-2}$ ...
1
vote
2answers
28 views

How can I solve this linear recursion?

Let be $a_{0}=1,a_{1}=1,a_{n}=4a_{n-1}-2a_{n-2}$ if($n\ge 2)$ Should I first find the generating function of the recursion and after that? I solved it with Wolfram Alpha and after it the result is ...
0
votes
2answers
16 views

Recursion If $a_0=1$, $a_1=3$, $a_2=9$ and $a_{n+3}=a_{n+2}+4a_{n+1}+5a_n$, show $a_n\le 3^n$

If $a_0=1$, $a_1=3$, $a_2=9$ and $a_{n+3}=a_{n+2}+4a_{n+1}+5a_n$, show $a_n\le 3^n$. I don't know how to type it in right format. $n+3$ and such things in the parentheses are small and in the lower ...
6
votes
2answers
651 views

Is there a recursive formula for Euler's Totient function

I have been looking for a recursive formula for Euler's totient function or Möbius' mu function to use these relations and try to create a generating function for these arithmetic functions.
0
votes
0answers
23 views

equivalent definitions of recursively enumerable sets

In some textbooks, a n-ary set R is defined as r.e iff there's it is a domain of a recursive function. In others, definition is restricted to case n=1 and a set is called r.e. if it is a range of ...
377
votes
6answers
26k views

Why is $1 - \frac{1}{1 - \frac{1}{1 - \ldots}}$ not real?

So we all know that the continued fraction containing all $1$s... $$ x = 1 + \frac{1}{1 + \frac{1}{1 + \ldots}} $$ yields the golden ratio $x = \phi$, which can easily be proven by rewriting it as ...
4
votes
4answers
184 views

find $O$ and $\Omega$ bounds as tight as possible for $T(n)=n+T(\frac n 2)+T(\frac n 4)+T(\frac n 8)+…+T(\frac n {2^k})$

Find $O$ and $\Omega$ bounds as tight as possible for $T(n)=n+T(\frac n 2)+T(\frac n 4)+T(\frac n 8)+...+T(\frac n {2^k})$ while k is some constant and for any $n\leq3$, $\ T(n)=c$. I didn't manage ...
0
votes
2answers
65 views

Define algorithm using divide and conquer paradigm [closed]

Q:Describe a Θ(n lg n)-time algorithm that, given a set S of n integers, determines which two elements in S have the smallest difference. (From what i understand, we first apply merge sort to our ...
1
vote
1answer
26 views

Characterization of $\Delta^0_0$ (rudimentary) functions

A $\Delta^0_0$, or rudimentary, functions $\Bbb N^k \rightarrow \Bbb N$ is a function whose graph is definable by a bounded formula. Can this class of functions characterized by means of closure ...
0
votes
0answers
15 views

recurrence algorithm unfolding with answer, need explanation

SO the question is to prove $O(n\log n)$ hence figure out $f(n)$ correct? why does $n = 2^{2^k}$ what is so special about $2^{2^k}$ can i use another number? this answer is using substitution? I ...
2
votes
0answers
45 views

Derivation of tetration by iteration

I was screwing around a bit differentiating tetrations and was trying to write some rules for them. I came up with this recursive definition: $$ \frac{d\ ^nt}{dt} =\ ^nt \cdot log(t)\frac{d\ ...
4
votes
7answers
197 views

Convergence of $a_{n+1}=\sqrt{2-a_n}$

I'm attempting to prove the convergence (or divergence, though I strongly suspect it converges) of a sequence defined as $a_{n+1}=\sqrt{2-a_n}$ with $a_1=\sqrt{2}$. I cannot use the monotonic ...
1
vote
1answer
52 views

Recursion Tree method for solving Recurrences

I'm trying to find the tight upper and lower bounds for the following recurrence: T(n) = 2T(n/2) + 6T(n/3) + n^2, if n >= 3 = 1 if n <= 2 Drawing the ...
0
votes
1answer
32 views

Recursive Equations: Satisfiability and Defineability

I'm reading a functional programming book that comes from a very heavy mathematical perspective and I got stuck on trying to understand and expand a statement about recursive equations. It states: ...
-1
votes
1answer
96 views

Recurrence for number of tile sequences of length n

We are placing tiles of colors red,blue and green in a row. Find a recurrence for number of tile sequences of length n (assuming unlimited supply is given) if a) No further conditions b) red tiles ...
7
votes
1answer
126 views

Primitive recursion and $\Delta^0_0$

Until recently I assumed that primitive recursive relations are exactly $\Delta^0_0$ (i.e. bounded) ones, but I learned they're different (the former is a proper superclass of the latter). I have ...
0
votes
1answer
37 views

Recursive formula for a visual pattern

I was looking at some of the examples at visualpatterns.org and coming up with explicit and recursive formulas for various aspects of the patterns. Consider the pattern below and the number of cubes ...
0
votes
1answer
83 views

Example of a recursive set $S$ and a total recursive function $f$ such that $f(S)$ is not recursive?

Browsing wikipedia, I stumbled on the following: "The image of a computable set under a total computable bijection is computable." Given the form of the theorem, there must be some example of a ...
2
votes
1answer
62 views

Problems understanding proof of s-m-n Theorem using Church-Turing thesis

I am reading Barry Cooper's Computability Theory and he states the following as the s-m-n theorem: Let $f:\mathbb{N}^2\mapsto\mathbb{N}$ be a (partial) recursive function. Then there exists a ...
0
votes
1answer
40 views

recursive parsing parenthesis with explanation

I came across an explanation where (()())() gives you the sequence 0,1,2,1,2,1,0,1,0 using recursive parsing. Can someone give ...
2
votes
2answers
395 views

Pi's Recursiveness [duplicate]

I don't know if this will make sense, but: If $\pi$ is infinite and contains all strings of numbers including those of infinite length, then it must contain $\sqrt2$, and if $\sqrt2$ is infinite and ...
2
votes
1answer
65 views

Recursion Tower of Hanoi [closed]

Consider the standard recursive solution to the Towers of Hanoi problem. In the traditional problem, all moves cost the same. Now, suppose the cost of a move is the size of the disk, with $1$ being ...
1
vote
1answer
23 views

Is there any procedure saying “this function is not obtainable without using recursion at least n times”?

It is known that $sum(x,y)=x+y$ is not obtainable from any compositions of basic functions $z,s,id^n_i$(zero, successor, projections) without using at least one recursion. also, $\times(x,y)=x\cdot y$ ...
1
vote
1answer
43 views

Solving a recurrence with 2 recurrences

I am trying to solve the following recurrence: $$T(n) = T\Big(\frac{n}{3}\Big) + T\Big(\frac{2n}{3}\Big) + O(n)$$ I do not want to use the Akra-Bazzi method nor draw out a recurrence tree. I do know ...
1
vote
1answer
33 views

recursive function: non-recursive form possible?

Can the following recursive function be converted to a non-recursive form? $$f(x,c,\ell)=\frac{c-c^\ell}{1-c}+(c-2)\sum \limits_{k=1}^{\ell-1}f(x,c,k)$$ $$f(x,c,1)=c$$ $$c= \text{constant}$$ ...
0
votes
0answers
44 views

Four people $(B,W,R,Y)$ are playing a game.

$4$ people, designated Black, White, Red, and Yellow, are playing a game. Each of them has unlimited number of balls, all of that person’s designated color. They work together to build a line of ...
0
votes
0answers
40 views

How to solve recurrence $T(n) = T(n/3) + T(2n/3) +n$ using Master Theorem

I'm trying to solve the following recurrence using Master Theorem, but I'm not used to seeing recurrences with to terms ( i.e. T(n)) for the cost of operations. I'm pretty sure that a should be 1 and ...
3
votes
3answers
465 views

Need to find the recurrence equation for coloring a 1 by n chessboard

So the question asks me to find the number of ways H[n] to color a 1 by n chessboard with 3 colors - red, blue and white such that the number of red squares is even and number of blue squares is at ...
0
votes
2answers
18 views

Recursion involving Piecewise

Student $C$ tries to define a function $G$: $Z^{+}\rightarrow Z$ by the rule $G$($n$) = \begin{cases} \ 1, & \text{if $n$ is 1}\\ \ G(\frac{n}{2}), & \text{if $n$ is even} \\[2ex] G(3n-2), ...
0
votes
1answer
21 views

In recursion theory, is $\Sigma_{i=0}^y f(x,i,z)$ primitive recursive?

It is known that given ternary primitive recursive function $f$, the function $g$ defined as $g(x,y,z)=\Sigma_{i=0}^z f(x,y,i)$ is primitive recursive. I wonder if this formulation can be modified; ...
0
votes
0answers
39 views

Proving that $x_{n+1} = ax_{n}(1-x_{n})$ converges when $1<a<3$.

I need some guidance for proving $x_{n+1} = ax_{n}(1-x_{n})$ converges when $1<a<3$. What are some tips you guys could give me to help prove this point, without telling me how to do it? I'm ...
0
votes
1answer
29 views

Induction and Recursion Proof using Catalan Numbers

Note that a product may be parenthesized in two different ways: and . Similarly, there are several different ways to parenthesize . Two such ways are and . Let be the number of different ways to ...
3
votes
1answer
36 views

Triangular Inequality using Induction

The triangle inequality for absolute value that for all real numbers a and b, Use the recursive definition of summation, the triangle inequality, the definition of absolute value, and mathematical ...
1
vote
0answers
36 views

Searching for a generating function of a probability mass function

I am looking for a a family of probability mass functions $f_n$ with the following recurrence: $$ f_{n}(k)=qf_{n-1}(k)+p\sum_{i=1}^{k-1}f_{n-1}(i)f_{n-1}(k-i). $$ In addition, we have $q=1-p$ and $ ...
0
votes
2answers
62 views

In how many ways can we distribute $20$ cards among $20$ persons numbered from $1$ to $20$ such that no one get his own number?

In my opinion inclusion-exclusion formula could be used here,but I think there must be a better way so we can reach the final answer(in fewer terms). Do you have any idea?
0
votes
0answers
20 views

Diagonalizing a family of primitive recursive functions

Say I've defined a family $\{h_i\}_{i \in N}$ of primitive recursive functions. I want to "diagonalize" and take: $g(n) = h_n(n)$ Is this $g$ also primitive recursive?
1
vote
0answers
29 views

Multivariate Clenshaw Chebyshev Algorithm (downward recursion)

I have recently written a code where I use Clenshaw's summation formula with Chebyshev polynomials $S(x)=\sum_{k=0}^nc_kT_k(x)=b_0+xb_1$ $T_{k+1}(x)=2xT_k(x)-T_{k-1}(x)$ $T_0(x)=1~~~ T_1(x)=x$ ...
0
votes
0answers
7 views

Is there a primitive recursive real number which can not have a primitive recursive expansion?

A primitive recursive function which is primitive recursively convergent is called a primitive recursive real number. If $\{s_n\}$ is a (primitive) recursive real number and if $a_n$ is a (primitive) ...
0
votes
2answers
119 views

Recursion: putting people into groups of 1 or 2

let $n \gt 1$ be an integer, and consider n people; $P_1,P_2,...,P_n$ let $A_n$ be the number of ways these $n$ people can be divided into groups, such that each group have either one or two people ...
0
votes
0answers
23 views

Recursive formula for mathematical expression

Assume that $\alpha , n,\lambda \in \mathbb{N}$,and $f$,$g$ two real valued functions defined on $\mathbb{N}$. Function $W$ is given by the following formula. \begin{equation} W(n) = \max_{1 \leq ...