The tag has no wiki summary.

learn more… | top users | synonyms

14
votes
1answer
224 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 exemples. How to calculate the number of circuits that ...
3
votes
1answer
187 views

Is there any way to solve recurrence equations with variable coefficients?

So far I have done some problems that are best solved using generating functions. These mostly contain variable coefficients. A simple one is $H(n) = (n+2)H(n-2)$. I have found solutions to these ...
2
votes
1answer
67 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 ...
1
vote
1answer
28 views

Predicting eigenvalues of bigger matrices

Consider the following $(3 \times 3)$ matrix: $K_3 = \left( \begin{array}{ccc} a & -1 & 0 \\ -1 & a+1 & -1 \\ 0 & -1 & a \end{array} \right)$ The question has a quantum ...
1
vote
1answer
35 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 ...
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 ...
1
vote
1answer
140 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
1answer
155 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 ...
4
votes
0answers
156 views

General overview about Recursion (free online texts)

I'm looking for free online texts about recursion. What I'm looking for formal definitions* of "all" (most of) the different types of recursion and from different points of views like Category ...
3
votes
0answers
63 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 ...
2
votes
0answers
37 views

Dynamic Programming: Stock Exercise

I'm having a trouble dealing with this problem: Since future market prices, and the effect of large sales on these prices, are very hard to predict, brokerage firms use models of the market to ...
2
votes
0answers
79 views

Ackermann function is not primitive recursive

The function of the Ackermann function is defined as $$ A_{0}(y)= y+1$$ $$ A_{x+1}(0)= A_{x}(1)$$ $$ A_{x+1}(y +1)= A_{x}(A_{x+1}(y))$$ I want to show that the function of ackermann is primitive ...
2
votes
0answers
60 views

Find the sum of exponentails of squares $\sum_{r=1}^n e^{-\alpha r^2}$

I would like to find $$a_n =\sum_{r=1}^n e^{-\alpha r^2},\qquad \alpha\in\mathbb{R}$$ I tried to solve the equivalent recursion $$a_n=a_{n-1}+e^{-\alpha n^2}\quad(n>0),\qquad a_0=0.$$ with an ...
2
votes
0answers
69 views

How to get the period of oeis.org/A130166 other than by trail?

oeis.org/A130166 a(0)=1; a(n)=prime(mod(a(n-1),1000)) starts with: ...
2
votes
0answers
60 views

Acceptable numbering of partial computable functions required to be one variable?

Soare in a yet unpublished textbook (I happened to be in a class taught by one of his former graduate students where we were field-testing a rough draft of his new textbook) Computability Theory and ...
2
votes
0answers
78 views

Prove that $\{(x,y): W_x\text{ and }W_y\text{ are recursively separable}\}$ is $\Sigma_3$-complete

Prove that $\{(x,y): W_x\text{ and }W_y\text{ are recursively separable}\}$ is $\Sigma_3$-complete This is a question from Soare's Recursively Enumerable Sets and Degrees. I have little idea how ...
2
votes
0answers
73 views

Indeterminacy in second degree equations of Spencer-Brown's “Laws of Form”

I am trying to follow G. Spencer-Brown's argumentation regarding 'Equations of the Second Degree' in the Laws of Form. He shows how infinitely growing self-referential forms can be created by using a ...
1
vote
0answers
31 views

Meaning of Biinterpretability.

I'm reading this paper: http://www.math.cornell.edu/~shore/papers/pdf/hyp9.pdf and I am struggling with the meaning of Biintereptability, to quote the paper A degree structure $D$ is ...
1
vote
0answers
46 views

Is the proof of non-totality of a function $f$ trivial if $f$ is recursively defined only on a subset of $\Bbb N$?

I define a fuction $*$ in a recursive way on a subset of natural numbers (with subset I mean that is $*$ define in the second argument only for $\Bbb N-\{0,1\}$ in other words we have $*:\Bbb N ...
1
vote
0answers
22 views

Show $f(x)$ is partial recursive using the

So I want to show that the function $f(x)=0 $ if $x$ is even and not defined otherwise, is partial recursive using the $\mu$ operator (bounded search function, which is partial recursive). Plan is to ...
1
vote
0answers
32 views

A Problem about Recursion

Consider recursion $$a_n+c_1a_{n-1}+\cdots+c_ma_{n-m}=0~~~~~~~~~~(1)$$ Let $\lambda^m+c_1\lambda^{m-1}+\cdots+c_m=0$ be the characteristic function and $(\lambda_1,n_1),\cdots,(\lambda_s,n_s)$ be ...
1
vote
0answers
23 views

recursive definition produces different sequence than non-recursive

I had a homework problem where I had to give a recursive definition for the sequence $$a_n = n(n+1)$$ Which produces {2, 6, 12...}, so I first came up with this (I'll call it answer 1): $$a_{n+1} ...
1
vote
0answers
41 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 ...
1
vote
0answers
65 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
0answers
92 views

Maximizing a continuous recursive function

So I've been working at this for a while and have so far been unable to find any resources on maximizing a particularly strange function that I've been trying to deal with. The function is of the form ...
1
vote
0answers
55 views

Reasoning about a recursive function

First of all, I am a computer science student, not a maths student. So maybe this is a trivial question, I just would like to understand it :) Suppose I have the following (pointless) recursive ...
1
vote
0answers
76 views

Defining things in a non-recursive manner

In this question I asked, if it was possible to define certain functions without the use of the recursion theorem. The answer, among other things, indicated that it theoretically would be possible, ...
1
vote
0answers
135 views

1s surpassing 0s in binary strings of odd length

Let $A(k)$ be the number of distinct binary strings of length $2k+1,$ for which the number of $1$s surpasses the number of $0$s for the first time at digit number $2k +1$, i.e., in the final digit in ...
0
votes
0answers
97 views

range of one increasing computation function?

We know that that the range of any recursive partial function is recursively enumerable. Also we know the fact: Set A is recursive if and only if it is range of some increasing section partial ...
0
votes
0answers
55 views

Recursion Theorem question

I am trying to prove the following in Enderton's text 'Elements of Set Theory' (exercise 8 of chapter 4): Let $f$ be a one-to-one function from $A$ into $A$, and assume that $c \in A - ran \ f$. ...
0
votes
0answers
31 views

How to solve this recursive integral?

$$f(p)= \int_a^\infty\frac{\exp(\iota k\dot p)}{k^2 + f(k)} dk$$ I thought of solving it like if I guess $f(k)$ equals a number then after solving the integral it should be itself.
0
votes
0answers
9 views

A question concerning the domain of function that is recursively defined.

I have a problem concerning nested functions and whether they're well-defined. I have the following definition for all $t\in \mathbb{Z}$. A function $y_t:\mathbb{R}^3\rightarrow\mathbb{R}$ such that ...
0
votes
0answers
21 views

Amount of sub-matrices created by Laplace expansion

I have created a program that solves a matrices determinant using the Laplace expansion method, and I was wondering if there is a equation which provides how many sub-matrices are created and used in ...
0
votes
0answers
67 views

Kleene's recursion theorem

Would anybody be able to provide me (someone with little familiarity with the subject matter) with a bit of background to the Recursion Theorem and guide me towards some texts on its mathematical and ...
0
votes
0answers
24 views

How to prove that in optimal strategie of tower of Hanoi none of the disks can't be placed on a disk of same parity

How to prove that in optimal strategie of tower of Hanoi none of the disks can't be placed on a disk of same parity if we have 3 rods. So for example disk 2 can't be placed on disk 4, or disk 1 can't ...
0
votes
0answers
22 views

Expressing three recursive forms into one using parameters?

I have the following recursive function that takes three forms and I want to express it in one form: Initial: $f(x) = m * f(x-1)$, $f(0) = value.$ Forms: 1 - $f(t) = m * f(t-1)$. where t is at ...
0
votes
0answers
51 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 ...
0
votes
0answers
47 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
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 ...
0
votes
0answers
60 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 ...
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 ...
0
votes
0answers
61 views

Repeated function composition

I have a recursive function repeat, that composes n calls to f with a start value ...
0
votes
0answers
48 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
0answers
68 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
0answers
69 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 ...
0
votes
0answers
43 views

Find the characteristic equation of a recursive function

I want to determine whether the following recursive function is unstable; $$ x(t+1) = \left( wx+sx(t)^b \over w+x(t)^bs + (1-x(t))^b(d-s) \right) $$ Wikipedia is telling me that I want to have the ...
0
votes
0answers
22 views

Recursion questions - How much series from $A=\{\dots\}$ have that which satisfy the conditions

I am trying to solve recursions problems to understand "how its works" and faced in 2 questions: How much series from $\{1,2\}$ have that the sum of the terms is $n$ How much series from $\{0,1,2\}$ ...
0
votes
0answers
65 views

How would you find a closed form expression for the following:

$$a_n = \frac{n}{n+1}a_{n-1} + \frac{n}{n-2}a_{n-2}\;,\;\;n\ge 3\; $$ For: $ 0 \leq n \leq 2 $, $a_n= n $
0
votes
0answers
587 views

Recursive definition for $S = \left\{{(a,b) \mid a \in \mathbb{Z}^+, b \in\mathbb{Z}^+ \text{ and } a + b \text{ is odd}}\right\}$

Give a recursive definition of each of these sets of ordered pairs of positive integers. [Hint: Plot the points in the set in the plane and look for lines containing points in the set. $S = ...
0
votes
0answers
101 views

Probably easy recursion formula solving $x^x=a$

Let $a,x_0\in\mathbb{C}$ and set $$ x_{n+1}=\sqrt{x_n\cdot \sqrt[x_n]{a}}$$ For which $a$ and $x_0$ does $x=\lim\limits_{n\rightarrow\infty} x_n$ exist with $$x^x=a$$ Approximating it with a computer ...