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
44 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
34 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
20 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
47 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
15 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
55 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
163 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 ...
0
votes
2answers
66 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 ...
0
votes
0answers
17 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 don'...
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 ...
1
vote
1answer
27 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 ...
2
votes
0answers
47 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\ ^{n-1}t}{...
0
votes
1answer
46 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
87 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 ...
1
vote
1answer
55 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
46 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
400 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 ...
390
votes
6answers
27k 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 $...
-1
votes
1answer
111 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 ...
2
votes
1answer
86 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 ...
2
votes
1answer
82 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
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}$$ $$\...
1
vote
1answer
46 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 ...
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 balls....
0
votes
0answers
66 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 ...
0
votes
2answers
23 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
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: ...
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
40 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 $ p,...
0
votes
2answers
68 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
21 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
34 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$ $b_{...
0
votes
0answers
8 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
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 \...
1
vote
0answers
121 views

Solving a polynomial for cyclic roots

For any complex value of c, the following polynomial has 6 complex root values of p: $$1+c+2 c^2+c^3+p+2 c p+c^2 p+p^2+3 c p^2+3 c^2 p^2+p^3+2 c p^3+p^4+3 c p^4+p^5+p^6$$ For a general 6th order ...
0
votes
4answers
98 views

Explicit formula for $e_k = 4e_{k-1} + 5$

The sequence looks like this: $e_0 = 2$ $e_1 = 4(e_{1-1}) + 5 = 13$ $e_2 = 4(e_{2-1}) + 5 = 57$ $e_3 = 4(e_{3-1}) + 5 = 233$ $e_4 = 4(e_{4-1}) + 5 = 937$ How would I go about finding the ...
0
votes
0answers
23 views

Finding the Primitive Recursive Function for the Rem Function

When trying to show the remainder function is a primitive recursive function as defined to be as below (Copied from Proof Wiki): $\operatorname{rem} \left({n, m}\right) = \begin{cases} 0 & : \...
1
vote
1answer
42 views

Give a recursion for the number h(n) of strings in S of length n.

Let S be the set of strings on the alphabet {0,1,2,3} that do not contain 12 or 20 as a substring. Solving this I got: $$ h(n) = 4h(n-1) - 2h(n-2)$$ with $h(0) = 1, h(1) = 4,h(2) = 14 $. When I did ...
1
vote
2answers
105 views

Find the recursive definition for the number of strings on 0, 1, 2 avoiding the substring 012?

This is the question $a(n)$ the number of strings on $0, 1, 2$ avoiding the substring $012$ and the answer is $$a(n)=3a(n−1)−a(n−3)$$ with $$a(0)=1,a(1)=3,a(2)=9$$ My question is how to you get this ...
0
votes
0answers
14 views

Gaussian weighted intergal of Product of Gaussians

I'm trying to find a solution to the following function, My understanding is that the resultant function should still be a Gaussian, however I would like to define it as a linear function the ...