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

Find recursive formula for number of sequences that meet criteria

I am given such a problem: Find the number $a_n$ of n-element ternary sequences (composed only of 0s, 1s and 2s), where: a) There are no repetitions of 1 (two 1s cannot stand next to each other) b) ...
0
votes
0answers
12 views

Recurrence Relation jumping forward and backwards between bounds of 0 and m

Question What I have gotten so far is as follows: $$q_{m,k} = q_{m,k-1}a_{n-1}$$ for $2|k$, otherwise it is $$q_{m,k} = q_{m,k-1} (m - a_{k-1})$$ Is there any way to make this into one recurrence ...
1
vote
0answers
22 views

Stair structure recursive solution

The question at the photo... I dont know if there someone saw this question before and understand what i want
1
vote
3answers
45 views

How many length-$k$ ternary strings have evenly many of a given symbol?

I write down a string of $k$ letters, where each letter is $X, Y, \text{or } Z.$ The letter $X$ appears an even number of times. How many different sequences of letters could I have written down? I ...
0
votes
4answers
27 views

Solving recursive formula including a sum

I have the following formula $$T(1) = 1 $$ $$T(n) = \sum_{i=1}^{n-1}T(i) + n^2$$ And I have to find an iterative form of any $T(n)$ for $n>1$ One thing I have managed to accomplish so far is ...
-7
votes
0answers
27 views

Need fast help pleease [closed]

Five people are passing a ball amongst themselves. The ball starts with Alonzo. Each person who has the ball passes it onto someone else. After the eighth pass, the ball returns to Alonzo. Find the ...
1
vote
1answer
42 views

Lucas n-Step Starting Numbers?

I am very interested in n-Step Lucas numbers. Trying to find, the "true starting" values seem to be contentious? I would assume $(1,1), (1,1,1), (1,1,1,1)$; like Fibonacci. However, 2-Step Lucas is $(...
0
votes
1answer
14 views

Amount of money earned only from interest - recursion POV.

I have a bank account with $0€$. At the beginning of every month I put an additional $250€$ into my account and at the end of the month I get a $0.5\%$ interest on my money. Based only on this ...
0
votes
0answers
10 views

Transform two recursively defined polynomial sequences to eqach other by transforming depending variable

Lets define the two recursive polynomial sequences by \begin{align} A_0(x) &= 1 \\ A_n(x) &= x \sum\limits_{k=1}^{n} k \cdot A_{n-k}(x) \end{align} and \begin{align} B_0(y) &= 1 \\ B_n(...
0
votes
1answer
17 views

Transformation of recursive defined polynomial to reverse coefficient order?

Lets define a recursive polynomial sequence by \begin{align} A_0(x) &= 1 \\ A_n(x) &= x \sum\limits_{k=1}^{n} k \cdot A_{n-k}(x) = \sum\limits_{k=1}^n a_k x^k \end{align} Is there a way to ...
0
votes
1answer
21 views

Solving a non-linear recurrence relation with binomial coefficient

I'm trying to solve a recurrence relation $\displaystyle \sum_{i=0}^{n}\binom{n}{i}\frac{A_i}{(n-i+1)}=0$, where $A_0=1$ first few terms are $A_1=-\frac{1}{2}$, $A_2=\frac{1}{6}$, $A_3=0$, $A_4=-\...
0
votes
0answers
24 views

Recursive bounds

Let's start the question with a prototype recursion of the numbers $a_g(d)$ we are interested in. These numbers satisfy the following recursion where $g\geq 0, d\geq 1$ all the numbers are otherwise ...
2
votes
0answers
47 views

Does the existence of Gödel universal functions make the S-m-n theorem unnecessary?

The problem of deciding, for any $x$, whether $\phi_x$ is a constant function, is undecidable. I came across the following proof of this fact in Rogers' book: To me, it looks too bulky and ...
2
votes
2answers
62 views

recursion number of possible paths

There is a terraced structure with N floors (here, for example 4 floors). Each floor has 4 cells. Write the recursive function that describes the number of all the possible paths from the left bottom ...
1
vote
0answers
30 views

On the proof of the unsolvability of the word problem in semigroups

I'm trying to understand the following proof of the unsolvability of the word problem in semigroups. I tried to reproduce the proof from some kind of personal communication, so I'm not sure everything ...
4
votes
1answer
105 views

Any advantages of using Gödel universal functions in proving unsolvability?

Let $U$ be a universal function for the class of computable functions of one variable. This means that $U:N\times N\to N$ is a computable (partial) function and for every computable (partial) function ...
7
votes
3answers
106 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
27 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
62 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
75 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
27 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
37 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
17 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
111 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
40 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
33 views

Converting this recursive formula to a function (if possible)

Anyone know how to convert this to a function? $a(n)=a(n-2)*(n/(n-1))$ $a(1)=1$ I understand maybe this can’t be converted to a function because it can’t return anything for even values of n, but ...
1
vote
1answer
49 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
25 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 $$
-2
votes
0answers
17 views

Time complexity recursion equation

So I made an algorithm and I am interested in the average time complexity which I calculated to be: $$T(n) = n + 1 + \frac{1}{n}\sum_{i=0}^{n-1}T(n-1-i)$$ I am bewildered on how to solve this. If ...
0
votes
1answer
36 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
32 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
29 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
39 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
60 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
48 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
21 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
24 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
54 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 ...

1
2 3 4 5
41