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

learn more… | top users | synonyms

2
votes
3answers
61 views

Recursive System of Equations and one Solved Example in 2007 GATE Exam?

The solution of $\frac{a_{20}}{a_{20}+a_{20}}$ is $-39$ from the recursive system of equations: \begin{cases} a_{n+1}=-2a_n-4b_n \\ b_{n+1}=4a_n+6b_n\\ a_0=1,b_0=1 \end{cases} This is taken from $...
1
vote
1answer
26 views

Variable Piecewise Recurrence Relation

Is it possible to find a closed form for the nth term of the following recurrence relation $$A_n = x_nA_{n-1} + A_{n-2}$$ where $A_{-1} = 1$ and $A_0$ equals some constant. I know the values of $...
1
vote
1answer
29 views

recursion and inductive proof

Just so no one thinks I am trying to get one over on anyone, this is a homework question. I have solved all the other problems, but I don't know where to begin with this one. I am not asking for an ...
0
votes
0answers
30 views

Is this a type of recurrence relation

Consider a series of integers $a$ defined by: $$\begin{cases} a_n & = c_n & \text{if $0 \le n \le 2$} \\ a_{2n} & = f(a_n, a_{n+1}) & \text{if $n > 1$} \quad \...
-1
votes
1answer
45 views

What's the ratio of liquids if I keep topping up one from another [on hold]

I have two containers with different liquids. 500ml and 200ml. I take a tiny sip from the 500ml, top it up from the small one, and mix thoroughly. I repeat this until the small one is completely empty....
0
votes
1answer
26 views

How do I interpret following equations on fibonacii numbers?

I went through an online tutorial (http://codeforces.com/blog/entry/14385) on finding n-th fibonacci number which explains a method as, You are standing at position n in Ox axis. In a step, ...
0
votes
0answers
35 views

Show that $\pi$ is a primitive recursive number [closed]

Can anyone provide a proof that $\pi$ is a primitive recursive number, or suggest how I might prove it? Thanks
1
vote
1answer
411 views

Help Solve Recurrence Relation T(n) = 3T(n/2) + O(n)

Given recurrence $$T(n) = 3T(n/2) + O(n)$$ $$let\:cn >= O(n)$$ for some constant c I can bound $$T(n)$$ in terms of $$T(n/2)$$ so I have $$T(n) <= 3T(n/2)+cn, \ \ \ \ \ k = 1 \ call$$ So I ...
1
vote
5answers
69 views

Closed form of function $f(n) = (1/n) \sum _{x=1}^{n-1} f(x)$ [closed]

Could anyone help me get to the closed form of the function: $$f(n) = \frac 1 n \sum _{x = 1}^{n-1}f(x)$$ $$f(1) = 1$$
0
votes
0answers
23 views

Solving a logarithmic functional recursion

What does recursion $$T(N)=\left(\frac{N^{f(N)}}{(\log N)^{f(N)}}\right)^2T((N\log N)^{1-f(N)})$$ evaluate to where ${f(N):\Bbb R\rightarrow\Bbb R}$ is a function such that $f(N)\in(0,1)$ at every $...
8
votes
3answers
2k views

How can I explain this integer partitions function recursion?

How to explain how this algorithm works? I need to write an article about this but I can't explain why this recursion works fine. It defines the number of partitions of a given integer ...
0
votes
1answer
625 views

Maximize profit with dynamic programming

I have 3 tables… $$\begin{array}{rrr} \text{quantity} & \text{expense} & \text{profit}\\ \hline 0 & 0 & 0 \\ 1 & 100 & 200 \\ 2 & 200 & 450 \\ 3 & 300 & 700 \\...
1
vote
1answer
32 views

Using determinants to find a recursive sequence

I am trying to compute a three diagonal determinant in order to find the recursive relation. Let $\Delta_{n}$=$\begin{vmatrix} 11 & 3 & 0 & 0 & \dots & 0\\ 13 & 11 & 3 &...
3
votes
4answers
328 views

Probability of knocking off all of a dragon's heads

You are fighting a dragon with three heads. Each time you swing at the dragon, you have a $20\%$ of hitting off two heads, a $60\%$ chance of hitting off one head and a $20\%$ of missing altogether. ...
0
votes
1answer
19 views

Primitive recursive function, constructing a proof

I've came upon an example in the book that is not that clear to me. The disparity function is proved to be primitive recursive in the following way: $$disparity(x_0,x_1)=(x_0-x_1)-(x_1-x_0) = add(...
0
votes
1answer
11 views

Existence of a injective and recursive(but not primitve recursive) fucntion that has a primitve recursive inverse.

The Question is as follows: For a one-to-one function f:N -> N, it's inverse is defined as: $$ f^{-1}(n) = \begin{cases} m+1 & \text{if }f(m)=n \\ 0 & \text{if } \forall m\in\mathbb N:...
0
votes
3answers
69 views

Find recurrence relation with general solution $a_n=A+Bn+C2^n+\frac{1}{3}n2^{n-1}$

General solution is: $a_n=A+Bn+C*2^n+\frac{n}{3}*2^{n-1}$ Can you give me some tips on solving this? Any help would be appreciated.
1
vote
4answers
42 views

nonhomogeneous recurrence relation with $f(n)=4*n-3$

I am trying to solve this recurrence relation: $a_n=a_{n-1}+4n-3$ I was trying to solve it using characteristic equation. First I found homogeneous solution: $a_n-a_{n-1}=0$ $x=1$ $a_n=A*1^n$ And ...
0
votes
2answers
38 views

how many sequences above 1,2,3,4,5,6,7 that don't contain odd couples

I got stucked a little with this question. would appreciate your help. the question is "find a recursive relation that counts how many sequences of order n above ${1,2,3,4,5,6,7}$ that don't contain ...
0
votes
0answers
90 views

Solutions to recurrence relations

Consider functions $s_{m},c_{m},d_{m}$ defined by the following recurrence relations $$s_{1}=n$$ $$c_{1}=s$$ $$d_{1}=0$$ $$s_{2}=n$$ $$c_{2}=s-n$$ $$d_{2}=d$$ $s,n, d$ are integers. If $c_{m}>...
0
votes
1answer
40 views

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.
2
votes
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$ ...
3
votes
2answers
282 views

Find a formula for a sequence

I'm trying to find a formula for the following sequence: $\{\sqrt{3},\sqrt{3\sqrt{3}},\sqrt{3\sqrt{3\sqrt{3}}},...\}$ I thought of solving it recursively and I got this formula: $a_{n}=\sqrt{3*a_{n-...
6
votes
2answers
257 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 ...
0
votes
1answer
23 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 ...
11
votes
4answers
791 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 ...
0
votes
1answer
38 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, ...
1
vote
1answer
24 views

# of bit strings of length n (even>2), with n/2-1 zeros and n/2+1 ones, zero followed by one

case 1: What is the number of bit strings of length 4, with 1 zero and 3 ones, zero must be followed by one Answer: 3 case 2: What is the number of bit strings of length 6, with 2 zeros and 4 ones, ...
0
votes
0answers
40 views

Solution to a first order linear difference equation

The two questions are with respect to the following first order linear difference equation $(Y_{t} - Y_{t-1}) = (1-\lambda) (X_{t-1} - Y_{t-1})$, for $t \geq n$ Also, note that the process ...
1
vote
1answer
32 views

Validate Dobinski's formula using recursive Bell number formula

As we know, Bell number can be given using two formula $B_N=\sum_{k=0}^{N-1}C_{N-1}^{k}B_k$ (recursive) $B_N=e^{-1}\sum_{k=0}^{\infty}\frac{k^N}{k!}$ (Dobinski's formula) Now I want to substitute ...
0
votes
1answer
50 views

Help to solve Divide and Conquer

How can I solve the following Divide and Conquer example? If you don't have enough time please just tell me the idea? Thanks $$T(n)=T\left(\frac{n}{7}\right)+T\left(\frac{11n}{14}\right)+n$$
0
votes
0answers
33 views

How to show that a function is primitive recursive?

If we have a function $g ~:~ \mathbb{N}^{k+1} \rightarrow \mathbb{N}$ which is primitive-recursive. How to show that the function $f ~:~ \mathbb{N}^{k+1} \rightarrow \mathbb{N} $ with $f(x_1, ~...~, ...
6
votes
0answers
159 views

A new type of Arithmetic-Harmonic mean for $n$ numbers

Let's introduce the following iterative procedure. Take two numbers $x_0$ and $y_0$. $$a_0=\frac{x_0+y_0}{2}~~~~~~~~~~~b_0=\frac{2x_0y_0}{x_0+y_0}$$ $$x_1=\frac{x_0+a_0+b_0}{3}~~~~~~~~~~~y_1=\frac{...
0
votes
1answer
19 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.
0
votes
1answer
23 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).
0
votes
1answer
38 views

Prove a relation is primitive recursive, x is prime?

Is $\{x \in \mathbb{N}| \mbox{ x is prime}\}$ primitive recursive? Hello, $x \in \{x \in \mathbb{N}| \mbox{ x is prime}\} $ if and only if $ \forall y : y \le x \Rightarrow (y=1 \vee y=x \vee \neg (...
4
votes
0answers
46 views

Computing cube roots using three number means

I've asked a question some time ago about Computing square roots with arithmetic-harmonic mean but it turned out that this method is exactly the same as Newton's method (or Babylonian method) for ...
4
votes
0answers
69 views

Skiponacci: $p | a_p$ Alternate Solution

For the Skiponacci sequence: $a_0=3, a_1=0, a_2=2,$ and $a_{n+1}=a_{n-1}-a_{n-2}$ for $n>2$, prove that any prime $p$ divides $a_p$. Is there any alternate solution other than using ...
6
votes
2answers
341 views

Precisely, what is a primitive recursive definition?

If I understand correctly, the language of primitive recursive arithmetic has a distinguished function symbol $S$, together with a function symbol for each primitive recursive definition (hereafter ...
1
vote
0answers
25 views

Variance of exponential moving average

I'm not quite sure what the form for the rolling recursive variance should look like. I have that the recursive average is $m_t = \alpha x_t +(1-a)m_{t-1}$. Then would the rolling recursive variance ...
1
vote
0answers
19 views

Nodes equation: can't find formula.

Given the level $N$ at which a node $X$ is located in a binary tree, to search for node $X$ according to level-order traversal, we can use the knowledge of level $N$ where $X$ is located to narrow our ...
1
vote
0answers
35 views

Any way to characterize this family of polynomials?

I have a family of polynomials generated by the recurrence relation $P_{n+1}(w) = (1+w)P_n ^{\ \prime}(w) -(3n-1 +nw)P_n(w) \\ P_1(w) =1$ The family is related to the Lambert $W$-function by its ...
0
votes
0answers
36 views

What does this theorem say in english?

Let $(P,Sc,1)$ a Peano's system, $G:P\times P\rightarrow P, H:P\rightarrow P$ are functions. Then $\exists ! F:P\times P\rightarrow P$ such that i)$F(x,1)=H(x)\forall x\in P$ ii)$F(x,Sc(y))=G(x,F(x,...
1
vote
1answer
36 views

A Question about Computable Functions

Barry Copper states following in his Computability theory book which I have a question about them. Exe.4.5.1: Show that if $\varphi_e(x) \downarrow $ is a computable relation, then so is ...
1
vote
2answers
141 views

Proof of x-intersection of the Mandelbrot Set?

I'm trying to prove that the Mandelbrot set intersects the X-axis on the interval [-2,.25]. I understand and have proven that the Mandelbrot set lies in a radius of 2. Mostly, I'm wondering how to ...
1
vote
1answer
77 views

factoring cubic polynomial equation using Cramer'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
23 views

How to solve a nonlinear recursion relation?

Given the following recursion relation \begin{equation} E^{(n)}=(E^{(n-1)}-\alpha_1)\,e^{-\alpha_2\,(\alpha_3E^{(n-1)}+b)} \end{equation} where $\alpha_i$'s and $b$ are some constants. I am trying ...
1
vote
2answers
37 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 ...
0
votes
0answers
28 views

Are these functions computable - Understanding computable functions

There is a theorem in computability theory which states: B.Cooper: If $A\subseteq N$ is computable, then $A$ is also computably enumerable. In the proof of this theorem -which is an ...
2
votes
3answers
50 views

Recursion Proof by Induction

Given: f(1) = 2 f(n) = f(n-1) + 3, for all n>1 It can be evaluated to: ...