The tag has no wiki summary.

learn more… | top users | synonyms

3
votes
0answers
49 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
39 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
41 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
57 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
91 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
43 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
47 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
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))$. ...
0
votes
1answer
64 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
59 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
120 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
57 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
69 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
47 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
47 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
34 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
154 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
121 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
55 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}}$$ ...
2
votes
2answers
969 views

Proof by Induction for a recursive sequence and a formula

So I have a homework assignment that has brought me great strain over the past 2 days. No video or online example have been able to help me with this issue either and I don't know where to turn. I’m ...
0
votes
1answer
52 views

How do I go about manipulating this summation equation to solve it?

In my textbook, Introduction to Algorithms, the following is shown: And I believe I understand that. However, I have a similar equation to the one on the first line, but instead of ...
2
votes
1answer
49 views

Problem solving recurrences with generating functions

I'm trying to solve this linear recurrence with generating functions, but I keep getting stuck on the last few steps. I found the generating function, but after splitting it into partial fractions and ...
1
vote
2answers
58 views

How does my textbook solve this summation equation for the answer?

Summations have always been my weakness in mathematics, and it's showing here as I'm very confused how my textbook, Introduction to Algorithms, goes from basically the second half of the following ...
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$. ...
1
vote
3answers
73 views

Where is the value of the variable $\epsilon$ obtained in the following explanation my professor gave?

My professor gave us this explanation from the textbook Introduction to Algorithms regarding the Master Method/Theorem: As a first example, consider $$T(n)=9T(n/3)+n.$$ For this recurrence, we ...
0
votes
2answers
109 views

fill-in-the-blank induction proof

I'm stuck at homework task I'm working on. I would really appreciate some help. Here is the task: Let $f$ be a function on binary numbers defined recursively as follows. $f(0) = 1$ and ...
1
vote
1answer
45 views

Course-by-values recursion

I have many questions in my textbook of the kind: Assume $g$ is primitive recursive and assume $f(0)=c_0,\dots,f(n-1)=c_{n-1}$ $f(x+n)=g(<f(x),\dots,f(x+n-1)>)$ Prove that $f$ is primitive ...
0
votes
0answers
45 views

Proving a function is primitive recursive

Assume $f$, $r$, and $s$ are primitive recursive. Prove that $$h(\overline x,y) = \begin{cases} f(\overline x,y,h(\overline x,r(y))) & r(y)<y \\ s(\overline x,y) & \text{otherwise} ...
0
votes
1answer
112 views

“Nested” recursion preserves primitive recursive functions

Problem: Assume the functions $f$, $\pi$, and $g$ are given. They take one, two, and three arguments respectively. Prove a unique function $h$ exists such that: $$h(0,y)\cong f(y)$$ $$h(x+1,y)\cong ...
0
votes
2answers
123 views

Termination of a Fast Exponentiation problem

Here's the problem I am stuck on. There exists a fast exponentiation program like the following: Given inputs a in the set of all Real numbers, b in the set of Natural numbers, initialize ...
0
votes
0answers
58 views

How is the algorithm for recursively printing permutations of a set of numbers this equation our professor gave us?

I'm having a great amount of trouble understanding where my prof got $T(m, n) = n(T(m+1, n-1) + m+1 + n)$ if $n > 1$ as the recursive formula for the algorithm for recursively printing the ...
0
votes
1answer
25 views

Defining a recursive function $f$ on $\{a, b\}$*

I would need some help on how I can define a recursive function $f$ on $\{a, b\}$* Define a recursive function $f$ on $\{a, b\}$* which replaces any $a$ with $b$ and vice versa, for example, ...
0
votes
2answers
57 views

I need some help on solving a recursive function question

I'm working on a recursive function task which i'm a bit stuck at. I've tried to google it on how I can solve this task, but with no luck Here is the task: Provide a recursive function $r$ on ...
0
votes
1answer
67 views

How can I solve this recursion function task?

I really need help on this task. Im stuck at it and I really would appreciate your help here. Give a recursive function $r$ on $A$ that reverses a string. For instance, $r(logikk) = kkigol$ and ...
0
votes
1answer
65 views

Solving a recurrence with division

I'm having this recurrence that is giving me a lot of trouble. $$F(2^0) = 1$$ $$F(2^k) = \frac 1 2 F(2^{k-1}) + 2^k$$ I will edit my post since this does not seems to work... The initial ...
1
vote
2answers
158 views

Solving expected value with recursion

We'll start off with an example of a question of finding expected value. What is the expected number of tries to get ’6′ when rolling dice? E(x)=1/6*1 + 5/6 (1+E(x)) E(x)=6 I understand the ...
0
votes
1answer
22 views

Recurrence to find P(n). P(n) is the number of ways to decorate a strip of size n with tiles.

There are three kind of tile. One is of size 1. Second is of size 2 of green color. Third is of size 2 with blue color. These are the values I found but I can not figure out the formula. P1 1 p2 3 p3 ...
1
vote
1answer
58 views

Ackermann function and primitive recursiveness

If we define $b_n(m) := a(n,m)$ for all $n$ and $m \in \mathbb{N}$. For which $n$ is the function $b_n$ primitive recursive and for which $n$ it is not a primitive recursive function? Can anyone ...
2
votes
1answer
1k views

Is 0^infinity indeterminate?

Is a constant raised to the power of infinity indeterminate? I am just curious. Say, for instance, is 0 raised to infinity indeterminate? Or is it only 1 raised to the infinity that is?
1
vote
3answers
50 views

How does my professor go from this logarithm to the following one of a different base?

I don't understand on the second last line how my professor goes from $2^{log_3(n)} = n^{log_3(2)}$ how is that relation formed?
0
votes
2answers
148 views

solve $T(n)=T(n-1)+T(\frac{n}{2})+n$

Using the recursion tree i tried solving this: $T(n)=T(n-1)+T(\frac{n}{2})+n$; the tree has two parts (branches) one that of $T(n-1)$ and other branch is of $T(\frac{n}{2})$. But as the term T(n-1) ...
4
votes
1answer
52 views

Prove $g$ is PR. $g(n) = f(n) \text{ if n} \notin A$. $f$ is PR. $g$ is total. $A$ is a finite set.

Show that if f:N $\rightarrow$ N is primitive recursive, A $\subseteq$ N is a finite set, and g is a total function agreeing with f at every point not in A, then g is primitive recursive. My ...
2
votes
1answer
123 views

Calculate percentage with Days

I'm programming a projectscheduler and want to calculate the percentage of finishing by looping through all the subprojects and calculate their weight and how many percent is done by now and then ...
0
votes
1answer
156 views

Simultaneous recursion

I have no idea how to even start proving the following theorem: If $f_0, f_1: \mathbb{N}^r \rightarrow \mathbb{N}$ and $g_0, g_1: \mathbb{N}^{r+3} \rightarrow \mathbb{N}$ are primitive recursive, ...
0
votes
1answer
66 views

Recursively defines function

Find $f(2),f(3),f(4)$, and $f(5)$ if $f$ is defined recursively by $f(0)=-1$, $f(1)=2$, and for $n=1,2,\ldots$ $$f(n+1)= 3f(n)^2 - 4f(n-1)^2$$
4
votes
1answer
307 views

Fibonacci with Mortal Bunnies

I am trying to understand a twist on the Fibonacci bunnies scenario, where the bunnies die x generations after their birth (where x is a positive integer). An example is shown here. I understand the ...
0
votes
1answer
42 views

Recursive Formula

I have found a question in my book and I have solve it, but I am not sure about the answer. The question goes like this: Find a recursive formula that will give the number of ways to order $N$ ice ...
0
votes
0answers
68 views

Golf Player Balls

A golf player has $K$ balls of the same type and $N$ balls of different types. I. In how many ways can we paint the balls such that each ball will be painted only once (the order of balls in the bag ...
1
vote
1answer
74 views

Basic Recursion Exercise

Find a recursive formula to divide N people in to couples and singles. The answer: $$A_n = A_{n-1} + A_{n - 2}(n - 1)$$ Some one can explain the answer , why do we need to multiply by n-1?