Tagged Questions

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 ...

1answer
36 views
+50

A question about many-one reducibility of two sets

We want to show that $\big\{x:W_{x}$ is finite }$=Fin \leq _m Cof=\big\{x : W_{x}$ is cofinite}. But I really have not any idea. Would be grateful for your help.
1answer
40 views

I need a common term for a recursive sequence

Some days ago, I made a question here about a common term for recursive sequence. I gained very good solutions. Thanks again. Today, I was thinking of a general case which is given below. Assume $p$ ...
2answers
271 views

2answers
252 views

The largest root of a recursively defined polynomial

Suppose that for all $x \in \mathbb{R}$, $f_1(x)=x^2$ and for all $k \in \mathbb{N}$, $$f_{k+1}(x) = f_k(x) - f_k'(x) x (1-x).$$ Let $\underline{x}_k$ denote the largest root of $f_k(x)=0$. I ...
1answer
20 views

Does the recursion theorem give practical means of constructing the indices mentioned in it?

I'm going through a textbook and the recursion theorem was introduced. The proof is a bit all over the place and kind of hard to follow so I thought I'd ask my question here. The theorem, as stated in ...
4answers
787 views

How to find explicit formula for two recursions?

I have to find explicit solution for two intertwining recursions \begin{align} f(n)&=f(n-2)+2g(n-1) \\ g(n)&=g(n-2)+f(n-1) \end{align} for $f(0)=1, f(1)=0, g(0)=0 ,g(1)=1$. What ...
1answer
35 views

Recursive Definition of Bitstrings exam help

I have an exam and my instructor told me to know how to solve this type of question could anyone help? not sure what to do. "A bit-string is a finite sequence of zeros and ones. For this question, ...
0answers
16 views

1answer
18 views

the set of extendable p.c. functions is not N

Show that the set $Ext:= \big\{x\in N : \varphi_{x}$ is extendable to a total recursive function $\big\}$ is not equal to the set of non negative integers $N$. Would be grateful for your help.
1answer
20 views

Modeling the maximum number of moves in Tower of Hanoi problem

What would be the recursive algorithm for solving the Tower of Hanoi problem (with n disks and 3 pegs) in maximal number of moves (i.e. going through all possible disks/pegs combinations).
1answer
38 views

0answers
14 views

Nature of state - recursion?

I always wondered how mathematicians define state (or rather: where it comes from?). This is tricky, because I always thought that in math there is only one "thing" - a pure, stateless function. Few ...
1answer
59 views

How to generate (recursively?) all non-isomorphic trees with 2 types of vertex labels with degree restrictions?

I am not sure if the title makes a whole lot of sense, but what I am trying to do is generate all non-isomorphic trees that obey the following: 1) Each vertex (including leaves) has one of two labels ...
1answer
20 views

How to find the function that is computed from a recursive algorithm? [closed]

The following is a recursive algorithm : Procedure unknown(n belongs to N) If n=0 then return 0 else return unknown (n-1)+5 The function that is computed from ...
2answers
161 views

Understanding the step-hop problem mathematically

I am working on a problem where one is given n number of steps. They can take either one, two, or three steps. How many number different possible ways are there to climb the n steps? I can solve this ...
2answers
250 views

Solving the Recurrence Relation/Series fn = 1 + fn-1*(M) where M is a constant

So I'm trying to solve this week's FiveThirtyEight Riddler. In a building’s lobby, some number (N) of people get on an elevator that goes to some number (M) of floors. There may be more people ...