Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [recursion]

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 a function for some inputs in terms of the values of the same function on other inputs. Please use the tag 'computability' instead for questions about "recursive functions" in computability theory

0
votes
3answers
18 views

How to get a general rule from the recursive definition

Assume we have an arithmetic sequence $f_n$ that has a non-recursive definition as follows: $$f_n=2n+1$$ This sequence can also be defined recursively: $$f_n=2+f_{n-1}$$ $$f_0=1$$ The same can be done ...
3
votes
2answers
30 views

convergence of a recursive sequence with parameter a

How can you determine if the following recursive sequence converges: $$x_{n+1}=\frac{1}{2}(a+x_n^2)$$ where $0\le a \le 1$ and $x_1=0$ I know that the limit x (if it exists) satisfies the following ...
0
votes
1answer
36 views

Power series representation for f''(x)-xf(x)=x

Given is $\sum\limits_{k=0}^\infty a_kx^k$ and $f''(x)-xf(x)=x$, $f'(0)=0$, $f(0)=0$. \newline I need to find a series representation of the upper sum, through determining an expression for $a_k$ ...
0
votes
1answer
30 views

How does convergence of $z_{n+1} = \frac{1}{2} \left( z_n+\frac{1}{z_n} \right)$ relate to $z_{n+1} = \frac{1}{2} \left( z_n+\frac{a}{z_n} \right) $

In class we looked at the following exercise: Let $a \ne 0$ be a complex number and let the sequence $(z_n)_n$ be recursively defined as $$z_{n+1} = \frac{1}{2} \left( z_n+\frac{a}{z_n} \...
0
votes
0answers
5 views

How do you incorporate a third dimension into an L-system?

I don't know hardly anything about L systems, I just came across them. But, I am interest in using them within a 3D environment. Looking here http://www.kevs3d.co.uk/dev/lsystems/ you can see that ...
6
votes
0answers
57 views

What is the minimum value of $f_\infty=\frac{x}{\sqrt{x-\sqrt[3]{x-\sqrt[4]{x-\cdots}}}}$?

In a similar vein to What is the maximum value of this nested radical?, I'd like to share a similar nested radical, but this time with changing fractional powers. What is the minimum value of $$f_\...
0
votes
0answers
25 views

Nonlinear Recursion Solution Process for $x_{n+1}=\Sigma_{i=1}^{n} x_{i}x_{n-i}$ (Known Solution)

I want to solve the equation $x_{n+1}=\Sigma_{i=1}^{n} x_{i}x_{n-i}$. Plugging the equation into Mathematica gives me $x_n=(-1)^{n}2^{2n+1} Binomial(1/2, n+1)x_0^{n+1}$. How might I derive this?
1
vote
1answer
20 views

How to find the closed form of the recursive equation, if 2 of the 3 roots of the characteristic equation are imaginary and only 1 root is real?

The given recursive equation is $$f(n) = f(n-1) + 3f(n-3) + 2n$$ The characteristic equation for $$f(n) = f(n-1) - 3f(n-3)$$ is $r^3 - r^2 - 3 = 0$, which has $2$ imaginary roots and $1$ real root ...
2
votes
0answers
20 views

Determinant definition from recursion

I know this definition of Principle of Recursive Definition from Munkres Topology, Ch 1: Principle of Recursive Definition: Let $A$ be a set; let $a_0$ be an element of $A$. Suppose $\rho$ is a ...
1
vote
0answers
41 views
+50

Markov chain converges to Normal Distribution. How to increase standard deviation

I am creating an MC (using the following recursive function). It is about a game that each side has different probs of scoring 1 point, 2 points, 3 points or no score (scoreDifference is the score ...
0
votes
0answers
30 views

Hill climber expected number of steps

Let's say you're trying to climb a hill with $k$ steps and you have $\frac{1}{2}$ chance of climbing one step and $\frac{1}{2}$ chance of falling back to the beginning of the hill. I am trying to find ...
0
votes
0answers
28 views

Mathematical induction proof of recursive dependences

I have such function: $$T(1) = 0$$ $$T(n) = 2T(n/2) + 1$$ and recursive dependence of that function: $$T(n)=n-1$$ It works but I don't know how to prove it with Mathematical induction.
0
votes
1answer
18 views

Resolve recursive dependences using substitution method

Resolve recursive dependences using substitution method and prove it with mathematical induction: ...
3
votes
1answer
55 views

Why is $\{\#F\mid\mathcal{N}\models F \text{ and $F$ is an $\exists$-formula} \}$ a recursive set?

Let $\mathcal{N}=(\mathbb{N},+,\cdot,0,1)$. I want to show that $\{\#F\mid\mathcal{N}\models F \text{ and $F$ is an $\exists$-formula} \}$ is a recursive set. Here $\#F$ is the Gödel number of $F$ and ...
0
votes
1answer
27 views

Find all integers a so that the sequence (Xn) satisfies the condition

Let ($x_n$) be a sequence integers defined as such: For all $n>1$ $x_{n+2} =2x_{n+1}x_{n} - x_{n+1} - x_n +1$ , $x_0=a$ , $x_1=2$ Find all integers a such that for all $n>1$ the number $2x_{3n} ...
1
vote
1answer
24 views

Logarithmic recursive functions

I've got the following recursive equation: $$T(n)=T\biggl(\frac{n}{3}\biggr)+2\log(n)$$ Given that: $T(1)=1.$ What i already tried: Going step by step back to the base case: $$T(n)=T\biggl(\frac{...
0
votes
1answer
27 views

Concrete Mathematics: Sums and Recurrences

In the book Concrete Mathematics(Graham, Knuth and Patashnik) section 2.2 Sums and Recurrences, is given: \begin{align} S_0=a_0 \\S_n = S_{n-1}+a_n, \end{align} General Form(2.7): \begin{align} ...
0
votes
0answers
42 views

Prove $F(n+2) - 1 = 1 + n(h-1) + n(h-2)$ by mathematical induction

$F(0)= 0$ and $F(1) = 1$ are predefined; $F(n)$ references the $n^{th}$ Fibonacci number. $n(h)$ is the minimal number of nodes needed to construct a AVL binary tree of height $h$. The theory shouldn'...
0
votes
0answers
59 views

Recursive sequences: $S_0 = 1, S_n = (S_{n−1})^{2} + (S_{n−2})^{2} + · · · + (S_0)^{2}$ for all integers $n ⩾ 1$

The question is- Write down the first five values of each of the following recursive sequences. $S_0 = 1, S_n = (S_{n−1})^{2} + (S_{n−2})^{2} + · · · + (S_0)^{2}$ for all integers $n ⩾ 1$ I'm not ...
1
vote
1answer
61 views

Prove that there is a $\Delta_1$-set $E$ which satisfies $S_0 \setminus S_1 \subset E \subset S_0$

I'd appreciate some help for the following exercise. $\Sigma_1, \Pi_1$ and $\Delta_1$ are defined here: https://en.wikipedia.org/wiki/Arithmetical_hierarchy I think I can prove 2. when I have 1. - can ...
27
votes
1answer
815 views

What is the maximum value of this nested radical?

I was experimenting on Desmos (as usual), in particular infinite recursions and series. Here is one that was of interest: What is the maximum value of $$F_\infty=\sqrt{\frac{x}{x+\sqrt{\frac{x^2}{x-...
0
votes
2answers
36 views

Recursion relation: Number of series length n made of (0,1,2)

Recursion relation: Number of series length $n$ made of {$0,1,2$} so that in each series there are no two consecutive numbers that are the same, and there isn't $0$ in the middle (for an odd number ...
0
votes
3answers
35 views

sequence that adds its previous results

Let $x = 0.3$. The first number of the sequence is $x$. The second number is the first number + $(0.3\cdot 0.3)$. The third number is the second number + $(0.3\cdot 0.3\cdot 0.3)$. This is a ...
0
votes
0answers
23 views

Taking seats on a plane (Revisited)

Most of you would be familiar with the plane seating problem. See this if not I was trying to solve a similar problem. What is the probability that the $i^{th}$ chair is not occupied, after $k$ ...
-1
votes
3answers
39 views

Trouble solving recursive function [closed]

I have trouble solving a (what looks like very easy) recursive function $a_0 = 0 \\ a_n = 2a_{n-1}+3$ Hints/Techniques for how to solve this would be highly appreciated! Thanks :)
0
votes
0answers
26 views

Using recursion tree to find time complexity of $T(n)=T(n/7)+T(3n/4)+cn$, where $c$ is a constant

After drawing the recursion tree,the longest path can be found,which is $1\to 3n/4\to\cdots\to(3n/4)^k$. So the length is $\log_{4/3} n+1$. Thus $T(n)\le cn[1+25/28+...+(25/28)^{\log_{4/3} n+1}]$. ...
1
vote
0answers
64 views

Proof that specific function is primitive recursive

For all $(n_1, \cdots, n_k) \in \mathbb{N}^k$ let's define $<n_1, \dots, n_k>:=p_1^{n_1+1} \dotsc p_k^{n_k+1}$, whereby $(p_1, p_2, p_3, \cdots)=(2,3,5,7,\cdots)$ are the prime numbers. For ...
0
votes
0answers
14 views

What is a good bound on this recursion?

$\alpha\in[0,1]$ with $T(N)=2(\log N)^\alpha N^{1/k}T(N^{1-1/k})$ with $T(m)=1$ if $m<2$ and $N\in\mathbb R$. Is there good asymptotics on $T(N)$?
0
votes
0answers
15 views

Derive 3-term recursion of polynomials from some recursion OR are my polynomials orthogonal

considering a sequence of polynomials $(Q_n)$ on $\mathbb{R}$ given by $$(q_1 - x)Q_0 + p_1 Q_1 =0$$ and for $n\geq 2$ by $$(q_n-x)Q_{n} +p_n Q_{n+1}+\sum_{i=0}^{n-1} c_{n,i} Q_i =0$$ where all ...
0
votes
1answer
41 views

Painting Fence - Stuck to find out generalized version

Problem Statement: There is a fence with n posts, each post can be painted with one of the k colors. You have to paint all the posts such that no more than two adjacent fence posts have the same color....
3
votes
1answer
70 views

Integral $\int \frac{\sin^n(x)}{\cos(x)}dx$

In one of my exercises about integration we had to solve the following integral: \begin{equation} \int \frac{\sin^n(x)}{\cos^m(x)}dx \end{equation} We had to do this via a recursive integral. I ...
0
votes
1answer
26 views

How to solve this product recursion?

The recursion is given by $$T(N)=2((\log N)T(N^{3/8})T(N^{1/4}))^2$$ $$T(N)=1\mbox{ if }M<1.$$ Is there a good upper bound?
1
vote
2answers
68 views

How to solve $T(n) = T(2n/3) + \lg^2 n$ by substitution?

My solution through substitution is as follows: $$T(n) = T(2n/3) + \lg^2 (n)$$ $$T(2n/3) = T(4n/9) + \lg^2 (2n/3)$$ $$T(4n/9) = T(8n/27) + \lg^2 (4n/9)$$ And so on... But my actual problem is how ...
0
votes
2answers
50 views

How to find limit of a second-order recursion

Suppose there is a sequence $$u_n = au_{n-1} - a^2u_{n-1}^2 + bu_{n-2} - b^2u_{n-2}^2$$ with the boundary condition, $u_0, u_1$ both are positive and less than $1$. How can I show that this ...
3
votes
1answer
56 views

Invent Binary Operator $*$ on Reals that Can Create $+$, $-$, $\times$, $\div$ [duplicate]

Exact Question: Invent a single binary operator $*$ such that for every real numbers $a$ and $b$, the operations $a + b$, $a - b$, $a \times b$, $a \div b$ can be created by applying $*$ (multiple ...
-1
votes
1answer
50 views

How many n-letter words are there, such that number of letters “a” is even? [closed]

How many n-letter words (made of letters from 25-letter english alphabet) are there, such that number of letters "a" is even? ("a" appears even number of times in a word). I'm trying to create ...
2
votes
1answer
21 views

Prove that function on naturals defined recursively is idempotent on odd numbers

Consider the function $f$ on natural numbers defined by the following recursion: $f(1)=1$ $f(3)=3$ $f(2n)=f(n)$ $f(4n+1)=2f(2n+1)-f(n)$ $f(4n+3)=3f(2n+1)-2f(n)$ Numerical evidence shows that for odd ...
1
vote
0answers
45 views

How to solve this nonlinear recurrence relations?

I know how to solve linear homogeneous and non-homogeneous recurrence relations. But today I found this problem. $$F_1=1$$ $$F_2=7$$ $$F_3=13$$ $$F_n = 3F_{n-1} + k(F_{n-2}F_{n-3})+10$$ Where $k$ is ...
1
vote
1answer
42 views

Find number of triangles with integral sides and side lengths ≤ 2n

Find number of triangles with integral sides and side lengths less than or equal to $2n$. I approached this method by recursion. Say $A_{2n}\ $is the number of triangles with integral sides and side ...
1
vote
2answers
39 views

proof that Ackermannfunction is uniquely defined and finding algorithm without recursions to calculate its values

my question is involving the Ackermannfunction. Let's call a function $a: \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$ "Ackermannfunktion", if for all $x,y \in \mathbb{N}$ the following ...
0
votes
1answer
20 views

Complicated linear recursion relations

Is it possible to obtain a solution for $a_n$ for the following recursion relation? $$a_n = -\frac{1}{\epsilon}(n+1)a_{n+1}+R\left(\frac{n+2}{n+1}\right)a_{n+2}+\frac{R}{\epsilon}\left(\frac{(n+3)(n+...
0
votes
0answers
31 views

proving statements involving primitive recursive functions and relations and (not) computable functions

I am learning about primitive recursive functions and primitive recursive relations (whereby a relation $R \subseteq \mathbb{N}^n$ is called primitive recursive if its characteristic function is ...
0
votes
0answers
19 views

Prove that an infinite recursively enumerable subset of natural numbers is the image of some injective recursive function

Let $X$ be an infinite recursively enumerable subset of natural numbers. I want to show that $X$ is the image of some injective recursive function. I was wondering how I can prove this question. Is ...
1
vote
0answers
43 views

Using Newton's method to find $M$, the unique positive zero of $x^2+x-1$

Using Newton's method to find $M$, the unique positive zero of $x^2+x-1$. Obtain a recursive formula for the error term $e_n$ use it to prove $a_n \rightarrow M$ Recursive formula for $a_n:\quad$ $...
4
votes
1answer
66 views

spaghetti hoops combinatorics variation

You may have heard about the classic spaghetti hoops combinatorics problem, which has been stated like this: "You have N pieces of rope in a bucket. You reach in and grab one end-piece, then reach in ...
0
votes
1answer
32 views

recursive inseparability of the two Gödelnumber-sets: theorems and 'anti-theorems' of EA

Here again one of my more or less basic proof-theoretic questions, working through Girards monograph from '87. This is about exercise 1.5.10. - "recursive inseparability", on page 80. It is this: ...
0
votes
0answers
14 views

A question related to induction and recursive sequences

I've been struggling with this problem for a long time now. It's Q2 part (b). Anyone have any ideas?Here it is
1
vote
0answers
14 views

Find non-identical matrices such that one cannot be converted into another by rearranging rows and then columns (Counting problem) [duplicate]

Given $N \times M$ binary matrices (matrix containing only $0$'s and $1$'s), two matrices are called identical if one can be converted into the other by first permuting the $N$ rows and then permuting ...
2
votes
1answer
27 views

Find the number of words recursively such that there is no palindromic suffix

Given a set of distinct characters $\{a_1, a_2, \cdots , a_S\}$ and a number $N$, find the number of words of length $N$ that can be formed using these letters (repetition allowed) such that there is ...
1
vote
1answer
40 views

Can you have indirect memory addressing in primitive recursive functions?

Douglas Hofstadter describes a programming language called BlooP in his book, "Gödel, Escher, Bach: An Eternal Golden Braid". I'm unclear whether cell variables require constant indices or whether ...