The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
1answer
57 views

On the size of a set of functions such that $f(i)\ne f(i+1)$ for every $i$ (and similar conditions)

For a finite set $A$,let $|A|$ denote the number of elements in the set $A$. (a) Let $F$ be the set of all functions $$f: \{1,2,\ldots,n \} \to \{1,2,\ldots,k\}~~~~~~~~~~ (n\ge 3,k\ge 2)$$satisfying ...
3
votes
1answer
56 views

Structure of partial recursive function over recursively enumerable guard

I read that the function $$ f(n) = \left\{ \begin{array}{l l} g(n) & \quad \text{if $n \in A$}\\ \text{undefined} & \quad \text{otherwise} \end{array} \right. $$ is recursive if ...
0
votes
1answer
29 views

computer recursion same question but omitting defdef

Given the alphabet {a,b}, give a recursive definition for the language whose words don't contain the string aa. My solution is i) b ∈ L1 ii) if w ∈ L1, then so is wba, abw My question is should i ...
1
vote
1answer
46 views

Another recursive math question

Given the alphabet {def ghi}, give a recursive definition for the language whose words contain the string defdef. My solution is: i) def ∈ L and ghi ∈ L ii) if u = def and w ∈ L*, then so is uu, ...
0
votes
1answer
44 views

recursive definition of strings

I have been unable to find any examples that resemble this problem and I am having issues with recursion. Here is the problem: Give a recursive definition for the set of strings of letters a, b, c, ...
0
votes
2answers
57 views

Recursive definition attempt.

I have the following question: $\text{b) }$Give a recursive definition for the function $f:\Bbb N\to\Bbb N$ which calculates the following sum for any $x\in\mathbb N$: ...
1
vote
1answer
48 views

computer theory recursion

I am having a bit of trouble understanding recursion and would like a bit of guidance. Consider the recursively defined language, L1: i) x ∈ L1 and y ∈ L1 ii) if w ∈ L1, then so is wxw ∈ L1 I have ...
2
votes
3answers
53 views

Recursion definition

Give a recursive defintion of the following set: $\{ 5^m 7^n \mid m, n \in N \}$ I don't have the slightest idea how to approach this question, id be really grateful if someone could provide me with ...
-2
votes
1answer
38 views

Proof by induction help

I don't know the full process of induction, as it's one of the harder questions on my upcoming test papers I thought i'd attempt to get a basic understanding; in order to get a 1/2 marks out of the ...
0
votes
2answers
52 views

proof by induction question

I decided to try proof by induction without any help = ) so if someone could check it out, pretty sure it's unfinished or, well i'm not sure. Also, if possible, could you take a logical guess for how ...
0
votes
1answer
54 views

function proving with induction [closed]

I'm having trouble with the following past paper question : Consider the function $take: \Bbb N \to \Bbb N$ defined recursively as follows: Base case: $take(0) = 100$ Recursive case: ...
0
votes
2answers
29 views

Recursion function question again

http://vvcap.net/db/3RxO1KX2d4LxgD714Tyh.htp mult(x,y)= mult(x-1,y)+4 mult(0,4)=0 mult(1,4)=mult(0,4)+4 mult(2,4)=mult(1,4)+4 mult(3,4)=mult(2,4)+4 I'm not sure whether this is correct, but i think ...
0
votes
0answers
30 views

Closed form for a special recursion?

Does the recurrence relation $$ a(n+1) = a(n)^2 + 1,\quad a(1)=1, $$ have a closed form solution? I have tried hard to find it, but failed. Any ideas ? I am particular interested in prime ...
14
votes
1answer
252 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 ...
2
votes
1answer
104 views

Generalization of the Tower of Hanoi?

What is the least possible number of steps for the Tower of Hanoi with $n$ discs and an arbitrary number $k$ of towers? For example, Tower of Hanoi with $4$ towers, $5$ towers, etc.
0
votes
1answer
41 views

Recurrence relation that skips $n-1$?

A difficult question I'm having problems with regarding recurrence relations and recurrence equations. The question is as follows: In how many different ways can I cover a 3xn checkberboard with 2x1 ...
0
votes
3answers
167 views

Difficult recursion problem

A student can do the things bellow: a. Do his homework in 2 days b. Write a poem in 2 days c. Go on a trip for 2 days d. Study for exams for 1 day e. Play pc games for 1 day A schedule of n days ...
0
votes
1answer
31 views

Defining substitution by structural recursion

For a term u, let $u{x\atop t}$ be the expression obtained from $u$ by replacing the variable $x$ by the term $t$. Define $u{x\atop t}$ by recursion on $u$. Not really sure how to start this one. ...
2
votes
1answer
70 views

Question about chebyshev polynomial

chebyshev polynomials are defined as such: $T_n(x)=cos(n*arccos(x))$ I'm asked to show that $deg(T_j(x))=j$ and that $T_0,T_1,T_2,...,T_n$ are an orthogonal basis of $\mathbb R_n[x]$. I think I can ...
0
votes
1answer
62 views

A setting in which Rice's theorem is not true

In my class we call a set of computable functions $A$ recursive if its indexing set $I_A=\{e\in\mathbb N:\phi_e\in A \}$ is recursive, where $\phi$ is some known Gödel numbering of the computable ...
1
vote
0answers
45 views

Is undecidability of arithmetic a corollary of Tarski undefinability theorem?

Arithmetic is undecidable, in other words the set of Godel numbers of theorems of arithmetic is not recursive, and so there is no algorithm/ recursive function to decide if a statement is provable or ...
0
votes
1answer
87 views

how I prove a valid recursion?

Determine whether is this a valid recursive definition of a function f from the set of nonnegative integers to the set of integers. If f is well defined (valid recursion), find a formula for f(n) when ...
1
vote
1answer
70 views

Recursive Square Root Futility Closet

This post on Futility Closet the other day: http://www.futilitycloset.com/2013/12/05/emptied-nest/ asked for the solution to this equation: \begin{equation}\sqrt{x+\sqrt{x+\sqrt{x...}}} = ...
0
votes
2answers
97 views

An effective enumeration of recursive sets in increasing order

Definition: We call a set recursive if its characteristic function is recursive. Claim: If the set $A\subset\mathbb N$ is recursive then $A=Range(f)$ for some recursive and increasing function. ...
1
vote
1answer
157 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
60 views

Let $x$ be a real number. To prove…

Let $x$ be a real number. Define the sequence $(x_n)_{n\ge1}$ recursively by $x_1=1$ and $x_{n+1}=x^n+nx_n$ for $n\ge1$. Prove that, $$\prod_{n=1}^\infty \bigg(1-\dfrac{x^n}{x_{n+1}}\bigg)=e^{-x}$$ ...
2
votes
1answer
70 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} ...
0
votes
1answer
41 views

Combinatorics recursion question. [closed]

How many binary vectors of length n do not contain a sequence '001' ? Solve by recursion and explain your solution.
1
vote
1answer
47 views

Prove that for any $m, n \in\omega$ that (i) $m + 0 = m$, (ii) $m + n^+ = (m + n)^+$

I am getting repeatedly lost trying to approach this question: Prove that for any $m, n \in\omega$ that (i) $m + 0 = m$, (ii) $m + n^+ = (m + n)^+$ I can fairly well grasp the idea that the ...
0
votes
1answer
31 views

A question on combinatorics

Bob and Laura have bought an apartment, and are going to carpet the floor in the kitchen. The kitchen has size $2 \times n$, where $n$ is a positive integer. In how many ways can Bob and Laura ...
3
votes
0answers
65 views

Induction on Primitive Recursive Function

The set $F_{n}$ of primitive recursive function symbols of arity $n$ can be defined inductively as: \begin{align} & Z, \text{Succ} \in F_{1} & \\ &\pi_{j}^{n} \in F_{n} \quad \text{for ...
1
vote
1answer
40 views

Two indexes $c$ and $b$, such that $Dom(\varphi_a)=\{b\}$ and $Dom(\varphi_b)=\{c\}$

Problem: Assume $\{\varphi_i\}_{i=1}^\infty$ is an effective enumeration of the computable functions. Find two indexes $c$ and $b$, such that $Dom(\varphi_c)=\{b\}$ and $Dom(\varphi_b)=\{c\}$. ...
1
vote
2answers
59 views

Discrete Mathematics - Recursion

Given the following question by my professor: Recursively define the set of natural numbers divisible by 3. My answer: ...
4
votes
3answers
73 views

Recursion, multiplication and exponential

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} ...
3
votes
2answers
99 views

Argument over an induction proof

My friend gave me a problem. Define a sequence $<a_n>$ by the recurrence relation :$$ a_{n+2} - 6a_{n+1} + 8a_n = 0 $$ and $a_1 = 4, a_2 = 8 $. Find the general term $a_n$ in closed form. ...
0
votes
1answer
49 views

Recursive function

Having difficulty with a question, was hoping someone could take a look and explain (if) where i'm going wrong. Consider the following recursive definition of a function $f:N\to N$ Base case: For ...
0
votes
0answers
63 views

Concatenation, reversal and sum are primitive recursive

Let $\mathbb N^*$ be the language of finite words with alphabet $\mathbb N$. Assume $k:\mathbb N^*\to\mathbb N$ is an effective coding. That is $k$ is a bijection whose length and member functions are ...
3
votes
1answer
86 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))$. ...
2
votes
4answers
121 views

find $O$ and $\Omega$ bounds as tight as possible for $T(n)=n+T(\frac n 2)+T(\frac n 4)+T(\frac n 8)+…+T(\frac n {2^k})$

find $O$ and $\Omega$ bounds as tight as possible for $T(n)=n+T(\frac n 2)+T(\frac n 4)+T(\frac n 8)+...+T(\frac n {2^k})$ while k is some constant and for any $n\leq3$ $\ T(n)=c$ for k=1 ...
1
vote
1answer
94 views

Number of ways to arrange different poker chips. (Recursion)

Assume there are poker chips in four different colors and one of the colors is blue. In how many ways can n amount of chips be piled on top of each other without two blue ones being next to one ...
1
vote
1answer
171 views

Closed form for general recursive function

Does a closed form exists for general recursive functions? my guess is not, but what types can be solved or what are the constraints on a recursive function so it has a closed form, what are some ...
1
vote
0answers
67 views

An informal version of the recursion theorem

In T. Taos Analysis 1 book, on page 26, we have a proposition that tells us that recursive definitions are actually well-defined. Proposition 2.1.16: Suppose for each naturla number $n$, wh have ...
1
vote
1answer
83 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 ...
0
votes
1answer
52 views

What will be the closed formula for the following recursive function?

What will be the closed formula for the following recursive function? F(n) = F(n/2) +1 if n is even F(n) = F(n-1) + 1 if n is odd F(1) = 0 How do we generate closed formula for such ...
0
votes
1answer
49 views

factoring cubic polynomail equation using Krammer's rule.

1) I have question about factoring cubic polynomials. In my note it says "Any polynomial equation with positive powers whose coefficients add to 0 will have a root of 1. Another, if sum of the ...
0
votes
0answers
37 views

How many number of ways are there for getting a special prime?

Definition of special prime : Any integer (+ve, -ve or 0) that is divisible by at least one of the single digit primes (2, 3, 5, 7) is a special prime. Thus -21, -30, 0, 5, 14 etc are special ...
1
vote
1answer
157 views

Survival Probability of a Population

A population starts with one amoeba. In each generation, each amoeba divides in two with probability $\frac{1}{2}$, or dies, with probability $\frac{1}{2}$. Let $p_n$ be the probability that the ...
0
votes
1answer
146 views

Prove that set is countable? [duplicate]

Show that the set N* of finite sequences of nonnegative integers is countable. Where do I start? I think I have to prove that there is a bijection between N* and N (set of natural numbers), but how ...
0
votes
0answers
64 views

Repeated function composition

I have a recursive function repeat, that composes n calls to f with a start value ...
0
votes
1answer
25 views

Analyse recursion $N_{t+1}=rN_t/(1+bN_t^2)$ [closed]

Given $$N_{t+1}=\frac{rN_t}{1+bN_t^2}$$ for $r>0$ and $b>0$ I need to: $1$. Find the limit of the recursion. $2$. Prove that: $$\frac{2r^2}{(4+r^2)\sqrt{b}}\le N_t \le \frac{r}{2\sqrt{b}}$$ ...