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

5
votes
4answers
5k views

What is the solution to the following recurrence relation with square root: $T(n)=T (\sqrt{n}) + 1$?

This looks like a question asked earlier, but it isn't. $$T(n)=\begin{cases} T (\sqrt{n}) + 1 \quad & \text{ if } n>1 \\ 1 & \text{ if }n=1\end{cases}$$ My professor gave this to me in ...
1
vote
1answer
298 views

Establishing formula from recurrence

Can anyone tell me how do we establish a formula from a given recurrence relation? Take the example of $f(n) = 2f(n-1) + 1$, $n \in \mathbb{Z^+}$, $f(1) = 1$ When I write out the first few values, it ...
0
votes
2answers
278 views

solve $T(n)=T(n-1)+T(\frac{n}{2})+n$

Using the recursion tree i tried solving this: $T(n)=T(n-1)+T(\frac{n}{2})+n$; the tree has two parts (branches) one that of $T(n-1)$ and other branch is of $T(\frac{n}{2})$. But as the term T(n-1) ...
10
votes
3answers
834 views

Recursive Integration over Piecewise Polynomials: Closed form?

Is there a closed form to the following recursive integration? $$ f_0(x) = \begin{cases} 1/2 & |x|<1 \\ 0 & |x|\geq1 \end{cases} \\ f_n(x) = ...
1
vote
2answers
75 views

Recursively defining sets of strings discrete math

So here are the two problems: Recursively define the set of bit strings K that do not have 00 as its substring. How many bit strings of length 10 are included in the above set K? Can someone ...
0
votes
1answer
279 views

$n$ Lines in the Plane

How am I to "[u]se induction to show that $n$ straight lines in the plane divide the plane into $\frac{n^2+n+2}{2}$ regions"? It is assumed here that no two lines are parallel and that no three lines ...
2
votes
2answers
185 views

Proving a recurrence relation for strings of characters containing an even number of $a$'s

We consider strings of $n$ characters, each character being $a$, $b$, $c$, or $d$, that contain an even number of $a$'s. (Recall that $0$ is even.) Let $E_n$ be the number of such strings. ...
1
vote
1answer
74 views

Recursive Function - $f(n)=f(an)+f(bn)+n$

I've got this recursive function $f(n)=f(an)+f(bn)+n$, and I need to find $θ$ on $f(n)$, as $a+b>1$. Using a recursive tree, I managed to bound it by $n\log(n)$ from the bottom and by $n^2$ from ...
1
vote
3answers
104 views

Proof by induction that recursive function $\text{take}$ satisfies $\text{take}(n) = 100 - 2n$

I'm sick and tired off posting threads about induction... I just can't seem to get it, I need someone to give me a detailed explanation and treat me like a 5 year old, literally. I'm wasting a lot of ...
0
votes
2answers
74 views

Possible distinct binary tree structures at depth d

I'm trying to figure out a recursive formula for the number of possible distinct binary trees at any depth d. I haven't been able to find any sort of sources on this. basically, at depth 0, the only ...
0
votes
1answer
50 views

Matlab Recursion Loop

I need to create a loop to answer part c of the following linear algebra question. I'm new to Matlab so this is extremely confusing. I'm not sure how to make a loop that "counts" from 0-25 in order to ...
0
votes
1answer
65 views

How many combinations can I make?

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 ...
0
votes
1answer
232 views

Simultaneous recursion

I have no idea how to even start proving the following theorem: If $f_0, f_1: \mathbb{N}^r \rightarrow \mathbb{N}$ and $g_0, g_1: \mathbb{N}^{r+3} \rightarrow \mathbb{N}$ are primitive recursive, ...
0
votes
2answers
792 views

Asymptotic bounds of $T(n) = T(n/2) + T(n/4) + T(n/8) + n$

This problem is given in "Introduction to Algorithms", by Thomas H. Cormen. I have the answer to it, but I don't understand it. The answer is, $T(n) = \Theta(n)$. It would be really good if you ...
11
votes
3answers
1k views

Is there a slowest divergent function?

So I've been playing around with some functions for a while, and started wondering about a slowest divergent function(as in $\lim_{x\to\infty} f(x)\to\infty$) and so I searched around for an answer. ...
18
votes
1answer
435 views

The problem of the most visited point.

Represents the set $R_{n\times n}=\{1,2,\ldots, n\}\times\{1,2,\ldots, n\} $ as a rectangle of $n$ by $n$ as points in the figures below for exemple. How to calculate the number of circuits that visit ...
10
votes
1answer
105 views

Is there a name for the recursive incenter of the contact triangle?

Recently, I became aware that there are many more triangle centers than the four I learned about in school. This reminded me of a thought I had when I first learned about the incenter: what point ...
7
votes
1answer
587 views

Bell numbers, recursions, bijections

The $n$th Bell number, named after Eric Temple Bell (although he was far from the first to think about them), is the number of partitions of a set of cardinality $n$. If they are written in the top ...
10
votes
5answers
630 views

Evaluating tetration to infinite heights (e.g., $2^{2^{2^{2^{.^{.^.}}}}}$)

The Problem How can you evaluate (i.e., get a value for) Tetration (i.e., iterated exponentiation) to infinite heights? For example, what would be the value of this expression? $$ ...
5
votes
0answers
113 views

Recursive and Primitive recursive functions

According to the book that I'm reading, we can define the $\mu-$recursive functions inductively, as follows: The constant, projection, and successor functions are all $\mu-$recursive. If $g_1, ...
7
votes
1answer
216 views

Primitive recursive function which isn't $\Delta_0$

What is the simplest/cutest example (and/or example with the most student-friendly proof that it is an example) of a primitive recursive function which isn't representable by a $\Delta_0$ wff?
5
votes
2answers
92 views

Prove function is Fibonacci sequence

Stuck on how to finish a question I'm working on. Have to find the number of bitstrings of length n with no odd length maximal runs of ones. For example, when n=3 there are three such bitsrings: 011, ...
5
votes
1answer
84 views

Eigenvalues appear when the dimension of the Prime Index Matrix is a prime-th prime. Why?

I had a look at the eigenvalues of the matrix, I called it Prime Index Matrix (is there a better name?), constructed like the following: $$ P_{k,p_k}=P_{p_k,k}=1, $$ where $p_k$ is the $k$th prime. ...
2
votes
1answer
77 views

Solve a recursion using generating functions?

Given the recursive equation : $$F_n+F_{n-1}+⋯+F_0=3^n , n\geq0$$ A fast solution that I can think of is placing $n-1$ instead of $n$ , and then we'll get : $$F_{n-1}+F_{n-2}+⋯+F_0=3^{n-1} $$ ...
5
votes
0answers
166 views

General overview about Recursion (free online texts)

I'm looking for free online texts about recursion. What I'm looking for formal definitions* of "all" (most of) the different types of recursion and from different points of views like Category ...
5
votes
2answers
379 views

A Recurrence Relation Involving a Square Root

Consider the recurrence relation: $a_{n+1} = \sqrt{a_n^2 -k},$ where $k>0$, $n\in\{0,1,n:a_n^2\geq k\}$, and $a_0>0$ is known. Is it possible to obtain an expression for $a_n$ in terms of ...
4
votes
1answer
164 views

Are hyperoperators primitive recursive?

I apologize if this question is too basic. I have read that the Ackerman function is the first example of a computable but NOT primitive recursive function. Hyperoperators seem to be closely related ...
3
votes
4answers
246 views

Proving convergence of a sequence

Let the following recursively defined sequence: $a_{n+1}=\frac{1}{2} a_n +2,$ $a_1=\dfrac{1}{2}$. Prove that $a_n$ converges to 4 by subtracting 4 from both sides. When I do that, I get: ...
3
votes
1answer
92 views

An effective coding of $\mathbb N^*$

Problem: Assume $\Pi:\mathbb N^2\to\mathbb N\setminus\{0\}$ is a primitive recursive coding of the pairs of numbers, that is also a bijection and $(\forall (x,y)\in\mathbb N^2)(\Pi(x,y)>max(x,y))$. ...
3
votes
1answer
98 views

Recursively Defined Entities

So I am having some trouble understanding how one is to come up with the recursive definition to the following problem... We are given a rectangle of width $2$ and length $n$. Suppose we have ...
3
votes
1answer
99 views

Help with generating functions.

Background. Let $P_0(y)=2y-3$ and define recursively $$P_{n+1}(y)=4y\cdot P_n'(y)+(5-4y)\cdot P_n(y).$$ I would like to know as many properties of $P_n$ as I can. For example, it can be shown that ...
3
votes
1answer
203 views

Do we really need the recursion theorem if we deal only with specific recursively defined functions?

How is it possible to define in a totally rigorous (i.e. from the axioms) was the functions $$h:\mathbb{N}\rightarrow \mathbb{N}, \ n\mapsto 1\cdot\ldots \cdot n$$ or $$ g:\mathbb{N}\rightarrow ...
2
votes
3answers
129 views

Counting the number of different ways in which groups of one or two can be formed…

I'm having trouble proving that the number of ways n>3 people can be divided into groups of either one or two is equal to: $A_n = A_{n-1} + (n-1)⋅A_{n-2} $ I'm trying to prove this by counting but ...
2
votes
0answers
68 views

Find the sum of exponentails of squares $\sum_{r=1}^n e^{-\alpha r^2}$

I would like to find $$a_n =\sum_{r=1}^n e^{-\alpha r^2},\qquad \alpha\in\mathbb{R}$$ I tried to solve the equivalent recursion $$a_n=a_{n-1}+e^{-\alpha n^2}\quad(n>0),\qquad a_0=0.$$ with an ...
2
votes
3answers
117 views

Can I use the master theorem for this?

this is a HW question so please don't just give me the answer right away. Basically, I'm working on solving the running time of this recurrence method: $$T(n) = 4T(n/3) + n \log \log n$$ I want to ...
2
votes
1answer
83 views

Primitive Recursion Functions (Programs)

The set $F_{n}$ of primitive recursive function symbols of arty $n$ can be defined inductively as \begin{array}[lr] & Z, \text{Succ} \in F_{1} & \\ \pi_{j}^{n} \in F_{n} \quad \text{for each} ...
2
votes
2answers
7k views

Proof by Induction for a recursive sequence and a formula

So I have a homework assignment that has brought me great strain over the past 2 days. No video or online example have been able to help me with this issue either and I don't know where to turn. I’m ...
2
votes
1answer
113 views

Identity involving a recursive product

Here is yet another problem related to plane partitions. Given the recursive formula $$ \begin{align*} F(0)&=1,\\ F(r)&=\prod_{i=1}^r\frac{i+2r-1}{2i+r-2}F(r-1). \end{align*} $$ How can we ...
2
votes
1answer
104 views

OEIS A000255 recursion.

I encountered the sequence A000255. $a(n)$ counts permutations of $[1,...,n+1]$ having no substring $[k,k+1]$ I am finding difficulty in proving it. Can you please give any clues or hints on how to ...
1
vote
2answers
112 views

How to determine which amounts of postage can be formed by using just 4 cent and 11 cent stamps?

Problem: a) Determine which amounts of postage can be formed using just 4 cent stamps and 11 cent stamps. b) Prove your answers to a using strong induction. My work: (I am only working on part a for ...
1
vote
2answers
42 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 ...
1
vote
4answers
111 views

finding explicit formula through substitution method

The question ask us to guess an explicit formula for the sequence $$t_k = t_{k-1} + 3k + 1 ,$$ for all integers $k$ greater than or equal to 1 and $t_0 = 0$ Can someone help me with this? Because I ...
1
vote
1answer
100 views

linear recursion $y_n=A \cdot y_{n-1}$

Let $a,b, \in \mathbb{R}$. Let $x_0=a, x_1=b$ and $x_n=\frac{x_{n-1}+x_{n-2}}{2}$ for $n \geq 2$ (i) Write the recursion in the form $y_n=A \cdot y_{n-1}$ where $A$ is a $2 \times 2$ matrix and ...
1
vote
2answers
1k views

Convergence and limit of a recursive sequence

Let $p>0$ and suppose that the sequence $\{x_n\}$ is defined recursive as $$ x_1 = \sqrt{p}, \quad x_{n+1} = \sqrt{p + x_n}, $$ for all $n \in \mathbb{N}$. How can I show that $x_n$ converges, ...
1
vote
1answer
225 views

All infinite recursive sets can be enumerated by an injective function

Definition: We call a set recursive if its characteristic function is recursive. Claim: If the recursive set $A\subset\mathbb N$ is infinite then $A=Range(f)$ for some primitive recursive injective ...
1
vote
1answer
155 views

Is definition by cases a primitive recursive function?

Primitive recursive functions can simulate every single step of a Turing machine. In order to prove this, one has to see that a function defined by state table is primitive recursive. Simply ...
1
vote
0answers
158 views

1s surpassing 0s in binary strings of odd length

Let $A(k)$ be the number of distinct binary strings of length $2k+1,$ for which the number of $1$s surpasses the number of $0$s for the first time at digit number $2k +1$, i.e., in the final digit in ...
0
votes
2answers
59 views

A series with the recursive formula.

A sequence $\lbrace a_{n}\rbrace_{n\geq 0}$ is constructed by choosing a value of $a_{n}$, and then the following elements are determined from the equation $a_{n}=2-\frac{1}{2}a_{n-1}$ for ...
0
votes
3answers
36 views

First order difference equation. Solve $u_{n+1}=3u_n+2$.

First order difference equation. Solve $u_{n+1}=3u_n+2$ with $u_0=0$ My notes are very sparse on this topic, so I need some help solving what should be an easy question. I would really appreciate ...
0
votes
3answers
58 views

Prove that $1 \cdot 1!+2 \cdot 2!+\cdots+n \cdot n!=(n+1)!-1$

Prove that $1 \cdot 1!+2 \cdot 2!+\cdots+n \cdot n!=(n+1)!-1$ whenever $n$ is a positive integer. Basis step: $P(1)$ is true because $1 \cdot 1!=(1+1)!-1$ evaluate to $1$ on both sides. Inductive ...