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

Filter by
Sorted by
Tagged with
-3
votes
0answers
23 views

T(n)=3tn-1+ 4tn-2 -1 recurrence [closed]

how do i solve the recurrence expression ? T(n)=? O(n)=? I've been struggling for hours. I have used all theorems but no result. Can you give me the T(n)= General rule and O(n)= Big O notation ...
0
votes
0answers
46 views

Greatest integer not exceeds the sum of recursive sequence

The question is from Pui Ching Invitational Mathematics Competition (2019) My attempt: $x_{n+1} = \frac{5}{\sqrt{x_{n}+8}+\sqrt{x_{n}+3}} $ if $x_{n}> 1$,$x_{n+1}< 1$ if $x_{n}< 1$,$x_{n+1}&...
1
vote
0answers
14 views

Growth rate / bounds for a recursive function of two-variables.

I was playing around with an area of graph theory and was able to recursively define the number of graphs $N$ that fit a specific condition dependent on two variables, $d,v\in\mathbb{N_0}$, where $$N(...
1
vote
1answer
41 views

Proof by Induction on a recursive function

its been a while since I have done proofs and am struggling on a question: Let $T(n)$ be defined recursively as follows: $T(1)=c$ and $T(n)=3T(n/3)+c, \forall n\geqslant 3$, where $c$ is some ...
1
vote
1answer
47 views

How do I get to this formula for this recursive sum and is my reasoning in proving this correct?

I have the following sequence: $n=1$ $$1$$ $n=2$ $$2+3+4$$ $n=3$ $$5+6+7+8+9$$ $n=4$ $$10+11+12+13+14+15+16$$ $$...$$ So abstracting these sums, we can write: $n_1+(n_1+1)+...+(n_2-1)+n_2$ , where $...
1
vote
0answers
29 views

$f(x)=z; x,z∈ℂ$ ⇒Be there an algorithm to determine arbitrary $k$th-iteration (forwe&back-) of $f^k(x)$, as a function $g(k_x)$ 1var-expressed in $x$?

For a few small values of $k\:∈ℤ$, function $f^k(x):=y\:\:|\:\:f:X→Y$ follows $f^{-2}(x)=f^{-1}[f^{-1}(x)]$ $f^{-1}(x)=\text{inv}[f(x)]$ $f^0(x)=:\text{id}_X(x) = x$ $f^1(x)=:f(x) \:\:$($:=z$ in this ...
-1
votes
0answers
27 views

How to solve a geometric recursive formula that uses the previous two terms? [closed]

How would I go about solving this problem explicitly? f(n)=5f(n − 1) − 6f(n − 2) for n ≥ 2; f(0) = 1, f(1) = 0 I got the the first few terms (-6, -35, -135) but I don't see a pattern that would help ...
0
votes
0answers
45 views

Recursive function in a signature

A first order language on real numbers has a symbol of binary function $g: R \times R \rightarrow R$. The theory over this language needs to have a function $q$ which is interpreted as $q = \sum g(...
0
votes
0answers
61 views

Convergence of $x_{n+1} = x_n^2 - 6x_n + 10$

Let $x_{n+1} = x_n^2 - 6x_n + 10$. For what values of $x_0$ is $\{x_n\}$ convergent, and how does the value of the limit depend on $x_0$? I know that if this recursion does converge, then it must ...
0
votes
1answer
48 views

About a construction by recursion in order to prove that $|X|\leq 2^{c(X)\chi(X)}$ for $X$ Hausdorff.

I'm studying general topology and, more exactly, an introduction to cardinal functions. I'm following the Chapter I, called Cardinal Functions I, of the Handbook of Set-Theoretic Topology by Kenneth ...
1
vote
2answers
75 views

How to solve $T(n) = 5T(n-1)+6T(n-2)$ iterative solution

$n≥2 , T(0)=1, T(1)=4$ $T(n) = 5T(n-1)+6T(n-2)$ $T(n)$= General rule and $O(n)$ = Big $O$ notation $T(n)=?$ $O(n)=?$ I tried to use the information provided. $T(2) = 5.4 + 6.1=26$ $T(3) = 5.26 + 6.4 =...
2
votes
2answers
57 views

The sequence $(u_n)$: $u_1=1, u_2=a>1$ and $u_{n+2}=(1+u_{n+1}^2)/u_n.$

The sequence $(u_n)$ is defined by the formula: $$\left\{\begin{array}{cc} u_1=1, u_2=a>1\\ u_{n+2}=\frac{1+u_{n+1}^2}{u_n}\end{array} \right.$$ Find a so that $u_n$ is integers for all $n \in \...
1
vote
2answers
76 views

How to calculate the result of a recursive equation?

I'm looking for a tool (like Wolfram Alpha) that can calculate the result of $ B(P,N) $ Where $B(P,N)$ is a recursive function defined as follows: $ \left\{\begin{matrix} B(P,N)=\frac{-(-1)^{\frac{N}...
5
votes
3answers
163 views

Hitting a target with a die: finding a better closed form of the recursive formula

Roll a k-sided die over and over and sum the results. What's the probability that the result will eventually hit exactly n? The recursive formula is: $$ p_{k,n}= \begin{cases} \begin{array}{cc} 0 &...
2
votes
1answer
87 views

Recursive definition of hyperbolic functions

I have a question about the recursive definition of functions, given as the following. Two sequences of functions, $\{C_k\}, \{S_k\}$ satisfies the following. $$S_k(x)=\int_0^x C_k(t)dt$$ $$C_{k+1}(...
0
votes
1answer
49 views

Existence of a sequence of vectors in recurrence relations

For each integer $i \geq 1$, let a fixed real matrix $A_i$ of size $n_i\times n_{i+1}$ be given such that it does not have a row filled entirely with zeros. The family of matrices $\{A_i:i\in\mathbb{...
0
votes
1answer
23 views

Recursive functions and conditionals

I was thinking about the way to write a function f(x) which results in the xth number of the fibonacci sequence. i.e. f(1) = 1, <...
2
votes
0answers
49 views

Is there a closed form for the recursively defined function $f_{n+1}(x) := f_n(x)^{f_n(x)}$.

Is there a closed form$^*$ for the following recursive function: \begin{align} f_0(x) &:= x\\ f_{n+1}(x) &:= f_n(x)^{f_n(x)} \end{align} Assuming that $x$ is an element of a semi-ring$^\dagger$...
1
vote
1answer
42 views

Find a closed formula for the generating function given the recursion equation.

Suppose we have the recursion equation $b_{n+2}=5b_{n+1}-2b_n$. where $b_0=1, b_1 = 2$. I'm trying to find a closed formula for the generating function. I tried to find the characteristic equation and ...
1
vote
1answer
116 views

How to find the limit of a recursive sequence involving multiple recursions?

Given $f(1)=1$, what is the limit of the following recursive function as $x$ approaches $\infty$? $$f(x)=\left(\sum_{n=0}^\infty {1\over{2^{xn}}}\right)\left(\sum_{i=1}^{x-1} {(^x_i)\over2^x}\cdot f(i)...
0
votes
0answers
63 views

I can't find the dp formula for counting the number of connected components that contains all value from $1$ to $k$.

We are given a connected graph with $n$ vertices and $n-1$ edges, and a parameter $k$. Each vertex $i$ has a value $c_i \in \{1, 2, \dots, n\}$; these values may repeat. Count the number of connected ...
2
votes
1answer
105 views

What is the limit of this sequence? $x_n=\frac 13(x_{n-1} + \frac{6}{x_{n-1}})$, $x_0=2$

$x_n=\frac 13(x_{n-1} + \frac{6}{x_{n-1}})$ Where $x_0 = 2$ I've calculated enough values to see that the limit of $x_n$ for $n$ to infinity is $\sqrt 3.$ But how do I prove this beside observation?
0
votes
0answers
53 views

Understanding the definitions for Godel numbering and Prime and bounded minimalizations for primitive recursion.

I'm having trouble understanding the prime and bounded minimalization which can be used to construct a primitive recursive function pn that enumerates the primes. (Copied from the textbook "...
7
votes
1answer
98 views

Determining convergence of sequence $a_n=a_{n-1}^{-1}+a_{n-2}^{-1}$ [duplicate]

I'm trying to prove convergence for the sequence $$a_n=\frac{1}{a_{n-1}}+\frac{1}{a_{n-2}}$$ with $a_0=a_1=1$. If it does converge then it converges to $\sqrt{2}$, which agrees with numerical tests. $$...
1
vote
1answer
82 views

Understanding the proof of Definition by Recursion

I’m currently reading Logic and Structure by Dirk van Dalen and I am having struggles proving Theorem $2.1.6$ (Definition by Recursion) on page $10$. Warning Before someone flags this question as a ...
0
votes
0answers
23 views

Issue with finding general solution to recurrence relation

I need to find the general solution to the recurrence relation: $a_n = 4a_{n-1} - 4a_{n-2} + 6 \cdot 2^n$ for all $n \geq 2$, given the intial conditons $a_0 = 9$ and $a_1=36$ I know that this is a ...
0
votes
0answers
38 views

A complex recurrence relation

I wanted to find a recurrence formula for $(1, 1497), (2, 1585), (3, 1587), (4, 1675), (5, 1677), (6, 1765), (7, 1767), (8, 1855), (9, 1857), (10, 1945), (11, 1947), (12, 1997), (13, 2494), (14, ...
1
vote
1answer
61 views

How do I solve this recurrence equation using the characteristics method?

Solve the following recurrence equation using the characteristics equation where n is a power of 2: $$T(n) = 7T\left(\frac{n}{2}\right) + 18\left(\frac{n}{2}\right)^2, T(1) = 0, n>1$$ I thought ...
0
votes
1answer
76 views

Rigorous Definition of Sigma Notation for Sums

I'm trying to come up with a rigorous way to define sums using sigma notation. Obviously$^{1}$, the sum $\sum \limits_{i=1}^{n}a_{i}$ needs to be defined on a set $X$ on which we have previously ...
1
vote
1answer
53 views

The possibility of convolution in recursion

We have a sequence $$a(n)=(1+s(n))\cdot a(t(n)), a(0)=1$$ where $s(n)$ is A033264 and $t(n)$ is A053645. After a short inspection, we note the following: $$a(2n+1)=a(n), a(4n)=a(2n), a(4n+2)=2b(n), a(...
0
votes
1answer
43 views

Solve two term recurrence relation

I want transform this recurrence relation into the closed formula, but i am stuck in some place, please provide some hints or steps to help me. The recurrence relation are $$ C_{n} = C_{n-1} + (\frac{...
2
votes
0answers
24 views

Calculating criteria for Recursion Operators

I am working through Peter Olver's book Application of Lie groups to Differential Equations and I came across this example on page 311 dealing with the criteria for Recursion Operators, now the ...
10
votes
2answers
282 views

Recursive formula for a tree problem

Question: A binary is defined as a tree in which 1 vertex is the root, and any other vertex has 2 or 0 children. A vertex with 0 children is called a node, and a vertex with 2 children is called an ...
1
vote
1answer
74 views

simplify $\sum_{k=2}^{n-1} k\log k$ with the hint that is to split the summation into two parts

Show that $$\sum_{k=2}^{n-1} k\operatorname{lg} k\leq \frac12n^2\operatorname{lg} n-\frac18n^2$$ Hint: Split the summation into two parts, one for $k=2,3,\dots,\lceil n/2\rceil-1,$ and one for $k=\...
2
votes
0answers
44 views

Recursive formula for a combinatorial problem

Question: Let $\Sigma =\{1,2,3,4\}$. For $n\ge 1,$ let $S_n$ be the set of all words above $\Sigma$ in which each adjacent chars are different and the last char isn't the same as the first char. E.g.:...
0
votes
0answers
32 views

A rigorous proof that the universal primitive recursive function is (Turing) computable

Since there are countably many primitive recursive functions, one can enumerate then by $\varphi_e$, where $e \in \mathbb{N}$. The universal function, usually denotes as $U(e,x)$ is an (apparently ...
1
vote
1answer
68 views

Find a recursion formula for combinatorial problem

Let $C_n$ be the number of sequences with a length of n, which their elements belong to $\{0,1,2\}$, and they don't contain the following sequences: $11,21$. Find a recursion formula with starting ...
1
vote
1answer
53 views

permutations and combinations cricket bat manufacturer problem

There are 4 Cricketers who have contacted Mr. Ski and each of them has different requirements. A cricketer will only be interested in a bat with a weight greater than his requirment and he can spend ...
0
votes
1answer
75 views

Proving Recursion Theorem

I've been learning Set Theory from both Danel Cunningham and Herbert Enderton's books and I can't wrap my head around how they prove the Recursion theorem on $\omega$: Let $A$ be a set and $a \in$ A. ...
0
votes
1answer
100 views

Use a recursion tree to determine a good asymptotic upper bound on the recurrence T(n) =T(n/2) +n^2. [closed]

I am quite confused on this one, found this while going through a book. The book also says that it can be verified using substitution. I have no idea how to approach this one since I am quite new to ...
2
votes
1answer
74 views

Does this summation formula for $\pi(x)$ work out? (Answer: no)

Let $p_i$ be the $i$th prime number. For $x \in \Bbb{R}, x \gt 0$, define: $$ \Delta(x) =\left \{\prod_{i=1}^r q_i : \{q_1, \dots, q_r \}\subset \{p_1, p_2, \dots, p_{\pi(x)}\}\right\} $$ Let $\omega$...
1
vote
0answers
35 views

Extending a variable assignment function to a formula assignment function formally using the recursion principle

I am reading Derek Goldrei's "Propositional and Predicate Calculus". Let $P$ be the set of all propositional variables and $S=\{ \neg, \land, \lor, \rightarrow, \leftrightarrow \}$ be the ...
1
vote
1answer
93 views

Encoding arbitrary algebraic data types in set theory?

Natural numbers are often defined recursively as an algebraic data type: type Nat := | Zero | Succ of Nat In set theory/ZFC, we can define the natural numbers ...
1
vote
1answer
45 views

Definition by generalized recursion, Peter Hinman's Foundations of mathematical logic

I'm reading the Foundations of mathematical logic by Peter Hinman, and something is unclear to me in his applications of theorem 1.2.14. Here's the theorem: Let $\mathcal{X}=(X,X_0, \mathcal{H})$ be ...
1
vote
0answers
19 views

Reference request for recurrence relation of the complete Bell polynomials $B_n$

On this wikipedia page there is the following recurrence relation for the complete Bell polynomials $B_n$: $$B_{n+1}(x_1,...,x_{n+1})=\sum_{i=0}^n\binom{n}{i}B_{n-i}(x_1,...,x_{n-i})x_{i+1}$$ with $...
1
vote
0answers
40 views

Integrating a recursive equation

Consider the ordinary differential equation $$dX_t = (a+bX_{t-1}) dt,$$ which is a recursive equation. How can I integrate such an equation? Should I treat $X_{t-1}$ as $X_t$? Is the solution of this ...
1
vote
1answer
38 views

count of the strictly increasing sub sequences of ${{1,2, ...n-1}}$ where each member of the subsequence serves the condition $x_i +i $ is even

count of the strictly increasing sub sequences of ${{1,2, ...,n-1,n}}$ of size k where each member of the subsequence serves the condition $x_i +i $ is even and $ 1<= i<= k$ and $k<=n$ There ...
2
votes
1answer
31 views

Developing recursive formulas in the theory of probability

I am solving problems from the book Introduction to probability by Dimitri P. Bertsekas and John N. Tsitsiklis and there came a series of problems in which you have to develop recursive formulas for ...
2
votes
1answer
81 views

Prove or disprove by induction that $a_n = b_n $ [closed]

I have this task that gives me really a hard time: For $$ n \in \mathbb{N_0} $$ $a_n$ is defined as $$ a_n= (-1)^{(n+1)}+ 1 + -3n + 2n^2 $$ and $b_n$ as: $$ b_n =\begin{cases} a_n \quad &...
1
vote
0answers
18 views

Recursive formula for variance with weights and decays

I have weighted observations (via importance sampling) with decay and would like to calculate (iteratively) the running variance. Both this question and this blog post focus on unweighted, non-...

1
2 3 4 5
49