The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
1answer
24 views

Time complexity of indirect recursion

How to find the complexity of an the given algorithm: Algorithm f(int n) { if(n==1)return(1); else { f(n-1)+g(n-1); } } Algorithm g(int n) { ...
2
votes
1answer
69 views

Solve the recurrence relation:$T(n)=\sqrt{n}T\left(\sqrt{n}\right)+\sqrt{n}$ [closed]

I have doubt in solving the following questions: $T(n)=2T(\sqrt{n})+n$ $T(n)=\sqrt{n}T(\sqrt{n})+c$ $T(n)=\sqrt{n}T(\sqrt{n})+\sqrt{n}$ T(2)=1 for all the problems Atleast give the final answer.
0
votes
3answers
44 views

A multivariate function, computable for any fixed first argument, is computable

Claim: If $f:\mathbb N^{k+1}\to\mathbb N$ is a function such that for all $x_0\in\mathbb N$, $\lambda x_1,\dots,x_k.f(x_0,x_1,\dots x_k)$ is a partial recursive function then $f$ is also partial ...
1
vote
1answer
29 views

Function composition in computability

I have been reading Cutland's computability book, which is really good! However, I have found myself thinking way too much about one little passage in the the third section of the second chapter (the ...
0
votes
1answer
42 views

Recursive Definition Theorem

I found two versions of a theorem which guarantees that recursive defined functions do exist (or that recursive definitions do make sense). The first is: Given a function $f:X\to X$ and an element ...
0
votes
3answers
57 views

Strong Induction and Recursion

Consider the recursion given by \begin{equation}f(n) = 2f(n−1)− f(n−2)+6 \text{ for } n ≥ 2 \text{ with } f (0) = 2 \text{ and }f (1) = 4 \end{equation} Use mathematical induction to prove that ...
0
votes
1answer
13 views

xyplus recursive language

For {x, y, +}, the language XYPlus is shown recursively as: (1) x and y are in XYPlus . (2) So if a and b are words in XYPlus ...
0
votes
1answer
30 views

Mathematical Induction Recursion

Consider the recursion given by $f(n) = 2f(n−1)− f(n−2)+6$ for $n ≥ 2$ with $f (0) = 2$ and $f (1) = 4.$ Use mathematical induction to prove that $f (n) = 3n^2 −n+2$ for all integers $n ≥ 0.$
1
vote
2answers
58 views

Recursive formula for tiling checkerboard

The question asks to find a recursive formula for $t(n)$ where $t(n)$ denotes the number of tilings a $2\times n$ checkerboard using only $1\times 1$ tiles and $L$-tiles (formed by removing the upper ...
3
votes
1answer
60 views

How many arrangements of the digits 1,2,3, … ,9 have this property?

How many arrangements of the digits 1,2,3, ... ,9 have the property that every digit (except the first) is no more than 3 greater than the previous digit? (For example, the arrangement 214369578 has ...
0
votes
1answer
43 views

Master's theorem applicability.

I have to find out if the following recurrence can be solved with the master theorem: $$T(n) = 3T\left(\frac{n}{2}\right) + n^{\log\log n}$$ I have figured that, here, I have the third case because ...
2
votes
2answers
147 views

Proving a recurrence relation for strings of characters containing an even number of $a$'s

We consider strings of $n$ characters, each character being $a$, $b$, $c$, or $d$, that contain an even number of $a$'s. (Recall that $0$ is even.) Let $E_n$ be the number of such strings. ...
1
vote
1answer
61 views

Creating Recurrence

If I have an integer $n \geq1$, and I had to draw $n$ straight lines, so that no two of them are parallel as well as no three of them intersect in one single point. These lines divide the plane into ...
1
vote
1answer
52 views

How does my textbook come up with this statement? I don't believe it to be true.

My textbook (Introduction to Algorithms) states the following: When polynomially comparing $n^\epsilon$ and $lgn$, it states that $n^\epsilon$ is polynomially greater for any positive $\epsilon$. ...
2
votes
3answers
87 views

Can I use the master theorem for this?

this is a HW question so please don't just give me the answer right away. Basically, I'm working on solving the running time of this recurrence method: $$T(n) = 4T(n/3) + n \log \log n$$ I want to ...
0
votes
0answers
45 views

How can I find the distribution of a recursive relation with two parameters?

Suppose we have a recursive relation, e.g. $G(n,m) = G(n-1,m) + G(n, m-1)$, with some initial points where $n,m \in \mathbb{Z}^{+}$ and $F$ is a finite-field, e.g. $\mathbb{Z}_p$ for a prime $p$. Also ...
0
votes
0answers
45 views

Can the method of generating functions be applied to linear recursions of order $>4$?

I just got in touch with the method of solving recursions with generating functions. However, even if it is not mentioned anywhere, it seems to me, this approach is not applicable for recursions of ...
6
votes
2answers
622 views

Can every recursive formula be expressed explicitly?

I'm not sure if my wording is entirely correct, but I was just wondering if every recursive formula can be turned into an explicit formula. I am asking this because various sources online gives me ...
0
votes
1answer
21 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 ...
0
votes
1answer
34 views

Find a formula for a sequence of the following character strings

Given strings: 0, 020, 0208020, 0208020180208020, 0208020180208020320208020180208020, ... I have to write a C++ program that computes the nth string. My problem is ...
3
votes
1answer
29 views

Can you prove this recursive multiple $n$-sided dice throwing statement?

Let $W_{s,r,n}$ be the total number of ways that the sum $s$ can be displayed after throwing $r$ number of $n$-sided dice. Define $$W_{s,0,n} = \begin{cases} 1, & \text{if s = 0} \\ 0, & ...
2
votes
2answers
64 views

Can we find a formula defining a recursively enumerable set?

By Post's Theorem we know that a set $A\subseteq\mathbf{N}$ is recursively enumerable iff it is definable by a $\Sigma_1$-formula, i.e. there exists a $\Sigma_1$-formula $\varphi(x)$ with $x$ free ...
1
vote
1answer
33 views

Maths/Programming recursion question

I know this is a programming question but it seems to be more on the mathematical side ( recursion ) I was hoping someone would be able to explain it to me since it will probably be on my exam ...
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
4answers
84 views

Proving convergence of a sequence

Let the following recursively defined sequence: $a_{n+1}=\frac{1}{2} a_n +2,$ $a_1=\dfrac{1}{2}$. Prove that $a_n$ converges to 4 by subtracting 4 from both sides. When I do that, I get: ...
0
votes
2answers
26 views

Express recursive funtion in Fibonacci

Given the Fibonacci function and the function $L_n = L_{n-1} + L_{n-2} + 1$, how do I go from this: $L_n + 1 = L_{n-1} + L_{n-1} + 1 + 1 \\ (L_n + 1) = (L_{n-1} + 1) + (L_{n-2} + 1)$ To this: $L_n = ...
3
votes
1answer
51 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 ...
2
votes
2answers
114 views

Recursive algorithm correctness: problem.

Considering that to prove a recursive algorithm we should refer to mathematical induction. Given the following algorithm (which sort an Array of size r) I found that base cases are for array size of 0 ...
1
vote
1answer
37 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
28 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
56 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
35 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
45 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
36 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
1answer
47 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
47 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
2answers
27 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 ...
3
votes
1answer
84 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))$. ...
1
vote
1answer
135 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
46 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
0answers
27 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 ...
2
votes
1answer
74 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
36 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
128 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
28 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
49 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
50 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
38 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
57 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
59 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...}}} = ...