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
7
votes
3answers
114 views

$x_{n+13}=x_{n+4}+2x_{n}$, $x_{143}=…$

Given $x_1=x_2=\dotsc=x_{12}=0$, $x_{13}=2$, and $x_{n+13}=x_{n+4}+2x_{n}$ for every natural number $n$. Find $x_{143}$. I tried to find some pattern for some of the first term but did not notice any ...
2
votes
1answer
117 views

Help to inductively define finite trees

In my assignment, I have an in-depth question regarding finite trees. We are presented with the trees in list form, and an empty list is symbolized as $\emptyset$. Example: A symmetrical tree with ...
0
votes
1answer
46 views

Prove big O for a recursive function

Let $t(n):=\begin{cases} \frac{2+\text{log}n}{1+\text{log}n}t(\lfloor\frac{n}{2}\rfloor) + log ((n!)^{\text{log} n}) \hspace{1cm} \text{if}\hspace{0.5cm} n>1 \\ 1 \hspace{0.5cm} \text{if}\...
1
vote
2answers
35 views

How to find a recursive formula for the number of combinations of {1, …, 9} of length n, such that there are no uneven digits next to each other?

I can't figure out how to formulate this in a single expression as the number of options for each additional digit depends on the previous last digit's value, but each previous step represents the ...
0
votes
1answer
30 views

Find the $n$th term of sequence in the form of $a_{n+2}=ba_{n+1}+ca_n+d$ [duplicate]

$a_1=1$, $a_2=3$, $a_{n+2}=a_{n+1}-2a_n-1$ How do you solve this? I only solve the sequence in the form $a_{n+2}=ba_{n+1}+ca_n$ before by writing it in $x^2-bx-c=0$ but for this I don't know how to. ...
0
votes
0answers
11 views

Continuity of a recursive piece-wise function.

I'm a student studying math, and I'm going through some old exam problems and I have come across a set of questions that ask me to decide where a given piece-wise function is continuous. The function ...
1
vote
1answer
63 views

The halting problem at zero

Consider the set $\{p:U(p,0)\text{ is defined}\}$ where $U$ is a universal function. I'm trying to understand the following sketch of proof of the fact that this set is not solvable. The first claim ...
1
vote
1answer
77 views

Confusion about definitions of a universal function

I've seen these two definitions of a universal partial function for partial computable functions of one variable: It is a (partial computable, I suppose, though it does not appear in the source) ...
0
votes
1answer
31 views

probability of finishing at r^th game by m people

so, the question is as follows: players $P_1,P_2...P_m$ of equal skill , play a game consecutively in pairs as $$ P_1P_2 , P_2P_3,...P_(m-1)P_m,P_mP_1,...$$ and any player who wins two consecutive ...
0
votes
1answer
39 views

Show that maximal set is not recursive

Define set $M$ such that its complement is infinite and for any computable set the intersection $M^C\cap R$ and $M^C\cap R^C$ are not both infinite. How to show that $M$ is NOT recursive, given we ...
0
votes
0answers
18 views

Find solutions of recursive equations - transform back into sum

Continuing excercise : Find solutions of recursive equations $$ x_{n} = 14x_{n-1} - 49x_{n-2} + (n-2)7^{n-2}, n\ge 2\\ a_{n} = 14a_{n-1} - 49a_{n-2} + (n-2)7^{n-2}\\ F(x) = \sum_{n=0}a_nx^n = 1 + \...
1
vote
2answers
120 views

Using backtracking to convert from recursive to explicit formula

How do I use backtracking to convert $a_n=a_{n-1}+a_{n-2}$ into an explicit formula? I am stuck. Please guide me through the correct method. Thank you for any comments/answers ~
1
vote
0answers
47 views

Simplifying Ramanujan's limited infinite root

Background I was playing around with Ramanujan's infinite root : $$\sqrt{1+2\sqrt{1+3\sqrt{1+4\sqrt{\cdots}}}}$$ You can write any number as this sequence by limiting the number of square roots in ...
0
votes
1answer
38 views

Converting this recursive formula to a function (if possible)

Anyone know how to convert this to a function? $\begin{align} a(n)&=a(n-2)(\frac{n}{n-1}) \\ a(1)&=1 \end{align}$ I understand maybe this can’t be converted to a function because it can’t ...
1
vote
1answer
52 views

Find solutions of recursive equations

Stuck... Find solutions of recursive equations using generating functions. $$ x_{n+2} = 14x_{n+1} - 49x_n + n7^n, n\ge 0\\ x_0 = 1\\ x_1=14 $$ What I tried: $$ x_{n} = 14x_{n-1} - 49x_{n-2} + (n-2)7^...
0
votes
1answer
16 views

Changing the index variable in a recursion relation

Can I change $$ x_{n+2} = 14x_{n+1} - 49x_n + n7^n\\ n>=0\\ x_0 = 1\\ x_2=14 $$ to $$ x_{n} = 14x_{n-1} - 49x_{n-2} + n7^n\\ n>=2\\ x_0 = 1\\ x_2=14 $$ And it's same? I need to find solutions ...
-1
votes
2answers
33 views

Solutions of recursive equations using generating functions

Can someone explain me how solve exercise like this? Find solutions of recursive equations using generating functions: $$ a_n = a_{n-1} + 2n - 1\\ a_0= 0\\ n\ge 1 $$
0
votes
1answer
37 views

Defining Partial Recursive Functions with their indices

I am working on learning recursion theory and I would like to know if there is any danger in defining a partial recursive function that uses its own enumeration. For example: $h(x) = \begin{cases}...
1
vote
0answers
35 views

Under what assumptions is this recursively defined function non-decreasing?

Let $\mathbb{N}^{+} = \mathbb{N}-\{0\}$ $a_{1}$, $a_{2} \in [0,+\infty)$ be such that $a = a_{1}+a_{2} > 0$ $b \in (1,+\infty)$ $f\colon\ \mathbb{N}^{+} \to (0,+\infty)$ $c_{1}$, $\dots$, $c_{\...
0
votes
3answers
17 views

Recursion Relation - Solution

Consider the relation $$p_x + p_{x-1}p_{x} = p_{x-1}$$ with $p_1$ given. The solution is written $$\frac{1}{p_x} = \frac{1}{p_1} + (x-1)$$ in my lecture notes as though trivial. I can't seem to ...
0
votes
0answers
18 views

How to efficiently take the logarithm of a sum of products?

I'm trying to compute the forward procedure on an HMM. While my code works just fine for small input sizes, a long chain leads to probabilities very close to 0 (as is to be expected.) However I later ...
0
votes
1answer
35 views

Is this a proper recursive ordinal notation for ordinals < $\omega^2$?

After making another question about ordinal notation I want to clear some confusion I have about the topic. Let consider ordinals less than $\omega^2$ (or in $\omega^2$) , any of such ordinals can be ...
1
vote
1answer
40 views

Recursive scheme for trapezoidal rule

I was supposed to derive the recursive scheme for the trapezoid rule. I know that this is the formula: $$ T_m (f;P) = \frac{1}{2} T_{m-1}(f;P) + \cdots$$ Initialization: $$ T_0 (f;P) = \frac{h}{2}(f(...
1
vote
2answers
62 views

Correctness with/without induction

I am a developer who tries to improve himself in algorithm design fields, and I got stuck in a problem. The mission is to prove the correctness of the following algorithm: For all integer constants c>...
-1
votes
1answer
21 views

How to add function to a recursive equation?

If I have the equations $f(x)=30c^x$ and $g(x)=g(x-1)+f(x)$, $g(0)=30$ why is $g(x)=30xc^x+30$ not the answer when something like $h(x)=h(x-1)+c$, $h(t)=d$ would make $h(x)=c(x-t)+d$? What I try to do ...
0
votes
0answers
29 views

Recurrence Relation : f(n) = f(1) + f(2) + f(3) + … + f(sqrt(n))

Recently I was solving a question and wondered what would be the time complexity. The function is as follows: ...
3
votes
0answers
50 views

Asymptotic of $a_n$ as thresholds of inverse power sums

Problem Let $a_{n> 0}$ be a monotonically increasing integer sequence. $a_1 = 1$, and the rest of $a_n$ is defined through the recursion relation \begin{equation} a_{n+1} = \text{argmax}_{A\in \...
0
votes
0answers
20 views

Recursion and bound

We have the following recursion $$ C_{g,n+1}= \left(n+1 C_{g-1,n+2}+\sum_{g_1 +g_2 = g\atop n_1+n_2 =n +1}^{\text{stable}}C_{g_1 , n_1 +1}C_{g_2 , n_2 +1} \right)\frac{(D_{g,n}+1)^{(D_{g,n}+1)}}{D_{...
3
votes
0answers
65 views

Prove in a typical equation method, that $f(n)=n-\sqrt{n}+1 $ is the result of $f(n)$

A function $f(n)$ is defined for $n=4^k$, $k\geq0$. $f(n)$ is given in a recursion format: $$ f(n)= \begin{cases} &3f(\frac{n}{4})-2f(\frac{n}{16})+\frac{3}{8}n,\quad n\geq160 \\ &1,\quad n=1 ...
0
votes
1answer
15 views

Recurrency procedure for carpet

I try defined recurrency procedure for this shape: I know that if n==0 then we need plot square. But clockwise? Next is plot smaller square, but I have a problem with a tour around the square. My ...
0
votes
1answer
23 views

Clarification on Defining Partial Recursive Functions

I've been working on learning about recursion theory, and I've been doing problems with partial recursive functions. I stopped myself when I wrote something like this: Let $g: \mathbb{N} \...
0
votes
1answer
25 views

Solving a recursion (probability related)

I want to solve the following: $$ \begin{align*} G_{T_t}(s) &= s\cdot G_X(G_{T_{t-1}}(s)) \\ G_{T_{t-1}}(s) &= s\cdot G_X(G_{T_{t-2}}(s)) \\ &\vdots \\ G_{T_0}(s) &= s \\ \...
4
votes
1answer
56 views

How to interpret this result from set theory?

I've been studying the recursion theorem in my introductory set theory course, and I've been given a homework about it. There was one exercise in particular that was, at first, kind of difficult to ...
0
votes
2answers
47 views

Is there any way I can make an explicit formula for the sequance $a_n=x+ya_{n-1}$?

Let $a_n$ be a sequence defined by recursion: $a_n=x+ya_{n-1}, a_1=k$. For example, if $(x,y)=(3,5)$, then the sequence would go $$a=\{k,\space 3+5k,\space 3+5(3+5k),\space ...\}$$ Is there an ...
1
vote
1answer
32 views

Proof of explicit formula for recursive sequence by induction

I am new to proof-writing and have just started working on Math for Computer Science on MIT OCW. I encountered the following problem on one of the assignments and would like feedback on my proof. ...
2
votes
0answers
110 views

A summation equation

How would you solve this equation? $$\frac{1^4}{2\sqrt{x} + 1} + \frac{2^4}{2\sqrt{x} + 3} + \frac{3^4}{2\sqrt{x} + 5} + \frac{4^4}{2\sqrt{x} + 7} = 50$$ I know the answer is $1/4$, and I know you ...
0
votes
1answer
19 views

Solving recursive relation

I am trying to solve the following recursive relation $$K_{2i-2}=\frac{a+K_{2i}}{1+aK_{2i}}\quad;\quad K_{2N}=0$$ and $i=1,\cdots,N$ I want to find the solution for $K_{2i}$. I believe that this ...
0
votes
1answer
13 views

The class of primitive recursive functions

Usually the scheme of primitive recursion is defined as follows: $$ h(x, 0)=f(x) \\ h(x, y+1)=g(x,y,h(x,y)) $$ I was wondering whether the class of primitive recursive functions would be smaller if we ...
0
votes
1answer
22 views

how to find a formula for recursive succession

I have to find a formula to calculate $a_n$ of this succession: $$ \begin{cases} a_{n+2}\equiv3a_{n+1}+10a_n\\ a_0 =2\\ a_1=3 \end{cases} $$ My question is: is there any technique for solving these ...
1
vote
1answer
39 views

Calculate the closed formula of a series

We have the following series: $$2, 1, 2, 1, 2, 1,...$$ and so on. Let $$x_0 = 2$$ Calculate the closed formula for $x_k$ The recursive formula for this series would be $$x_k = x_{k−1} + x_{k−2} − ...
1
vote
0answers
20 views

How to find Recurrence Relation of the Central Delannoy Numbers

I was working on finding the Recurrence Relation of a sequence with a definition Similar to the Central Delannoy Numbers and so i began to study them. CDN : https://en.wikipedia.org/wiki/...
0
votes
4answers
62 views

Functional equation $f(x+1)+f(x-1)=\sqrt{2}\cdot f(x)$

Can $ f: \mathbb{R}\rightarrow \mathbb{R}$ which satisfies functional equation $$f(x+1)+f(x-1)=\sqrt{2}\cdot f(x)$$ be periodic? No idea how to prove this - $f(x+T)=f(x-T)=f(x)...$
0
votes
0answers
30 views

How can I unfold this recurrence?

I am trying to solve this recurrence, but first I have to unfold it. T(1) = 5 T(n) = T(n / 3) + 5 for n ≥ 2 I would be grateful if anyone could help me.
2
votes
1answer
23 views

Recursive definition of sets

I'm having trouble understanding the following problem: I have three sets, the first one contains $$S=\{a,b,c\}$$ The second contains operators (plus, times, bullet) $$O=\{+, \times, \bullet\}$$ ...
1
vote
2answers
22 views

Help with recursive function

I need some help understanting how the following conclusion was made: We have the recursive function: $ε_n=-n \cdot ε_{n-1}$ How do we come to the conclusion that $ε_n=(-1)^{n-1}\cdot n!\cdot ε_1$
2
votes
5answers
114 views

Recurrence Relation: Hᵥ = 2ᵛ - Hᵥ₋₁

This problem has been giving me a headache for days. My teacher has taught us the plug-and-chug method of working these problems out and eventually finding a closed form. However the " - Hᵥ₋₁ " is ...
0
votes
0answers
19 views

Truncate infinite recursive series

I have the following recursion: $$f(x_n)=g(x_n)+f(x_{n+1}).$$ thus $$f(x_0)=\sum_{n=0}^{\infty}g(x_n)$$ My question is, if I only want a finite summation of $g(x_n)$, say for $n =1 ,\cdots,N$, can do ...
0
votes
0answers
22 views

Asymptotic running time for following recurrence function

What method should I use to find the running time of the recurrence function: $$T(n)=T(n/4)+T(3n/4)+\theta(n)$$ I've tried to solve this question by guess-and-check. I assumed that the total size of ...
0
votes
0answers
30 views

Definion of the binomial coefficients in the set theory. Reference request for recursion principles.

The definition of the binomial coefficients is here: $$\binom{n+1}{k+1}=\binom{n}{k}+\binom{n}{k+1}$$ $$\binom{0}{0}=\binom{n}{n}=1$$ My aim is to define it in set theory on natural numbers, not on ...

1
2
3 4 5
42