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

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
16 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
46 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
45 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
85 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
54 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
44 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
397 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 ...
386
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
110 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
76 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
78 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
57 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
37 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
86 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
22 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
103 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 ...
1
vote
1answer
42 views

Number of ways to choose $k$ subsets such that $ B_1 \cap B_2 \cap \cdot \cdot \cdot \cap B_k = \emptyset$.

Let $ \space n,k \in \mathbb Z \space $ such that $1 \le k \le n \space$. Let $\space A=\{1,2,...,n\}$. Find the number of ways to choose $k$ subsets $\space B_1,B_2,...,B_k\space $ of $A$ such that $ ...
0
votes
2answers
37 views

Recursive formula to 3x3 matrix

I was given a recursive formula and I need to convert it into a $3\times3$ matrix. What is a general formula to do this? My recursion is in the form: $$R_{n+2} = 4R_{n+1} + 5R_n + 2R_{n-1}$$ Just ...
4
votes
7answers
202 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 ...
0
votes
2answers
57 views

solve recursion $T(n) = T(\alpha n)+T(\beta n)+\gamma n$

I need solve this recursion: $$T(n) = T(\alpha n)+T(\beta n)+\gamma n$$ I know that for $\alpha +\beta< 1$ solution is $O(n)$ How is for $\alpha + \beta = 1$ and $\alpha + \beta > 1$?
0
votes
0answers
21 views

Recursion $T(m) = c_0 m + \sum\limits_{i=0}^{k}T(\lceil c_i m \rceil)$,$\sum\limits_{i=1}^{k}c_i < 1$ is linear

Let $L: \mathbb N_0 \to \mathbb N_0$ satisfy the recursion $T(m) = c_0 m + \sum\limits_{i=0}^{k}T(\lceil c_i m \rceil)$ with $c_i \geq 0$ for $i=0,\ldots, k$ and $\sum\limits_{i=1}^{k}c_i < 1$. ...
0
votes
0answers
30 views

Master Theorem for common recurrence

I have the following recurrence: $$T(n) = T\bigg(\frac{n}{2}\bigg) + O(n)$$ And I am trying to find the time complexity using the master theorem. So I have: $a = 1, b = 2$ $f(n) = O(n) = c(n)$ ...
0
votes
1answer
62 views

Find the order of elimination in Josephus Problem

Josephus Problem (or Josephus permutation) is a theoretical problem related to a certain counting-out game. People are standing in a circle waiting to be executed. Counting begins at the first ...
0
votes
2answers
26 views

Recurrence relations with multiplication

I have a recurrence relation and I am not quite sure if I am solving it correctly. The relation is this: $$t_n = 2n~t_{n-1}$$ where $t_0 = 1$ Here is how I went about solving this: First step is to ...
2
votes
1answer
57 views

Recursive formula for word problem.

I'm having problems with this recursion problem: Ann wants to buy along several weeks one dressing item which can be of two kinds: small ones -- hats and scarfs, and big ones -- dresses, suits, gowns ...
2
votes
1answer
53 views

How do you go about solving this recurrence?

How do you make an estimation for the substitution method, when the recursion tree did not help so much? I have a recurrence $$T(n) = 5\cdot T(n/3) + n (\log n)^2$$ And upon doing the recurrence ...
1
vote
1answer
59 views

Recursive definitions in formal logic

A binary tree $T$ is either A single vertex, or A graph formed by taking two binary trees, adding a vertex, and adding an edge directed from the new vertex to the root of each binary tree. Suppose ...