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

0
votes
1answer
29 views

Induction and Recursion Proof using Catalan Numbers

Note that a product may be parenthesized in two different ways: and . Similarly, there are several different ways to parenthesize . Two such ways are and . Let be the number of different ways to ...
3
votes
1answer
36 views

Triangular Inequality using Induction

The triangle inequality for absolute value that for all real numbers a and b, Use the recursive definition of summation, the triangle inequality, the definition of absolute value, and mathematical ...
1
vote
0answers
36 views

Searching for a generating function of a probability mass function

I am looking for a a family of probability mass functions $f_n$ with the following recurrence: $$ f_{n}(k)=qf_{n-1}(k)+p\sum_{i=1}^{k-1}f_{n-1}(i)f_{n-1}(k-i). $$ In addition, we have $q=1-p$ and $ ...
0
votes
2answers
66 views

In how many ways can we distribute $20$ cards among $20$ persons numbered from $1$ to $20$ such that no one get his own number?

In my opinion inclusion-exclusion formula could be used here,but I think there must be a better way so we can reach the final answer(in fewer terms). Do you have any idea?
0
votes
0answers
21 views

Diagonalizing a family of primitive recursive functions

Say I've defined a family $\{h_i\}_{i \in N}$ of primitive recursive functions. I want to "diagonalize" and take: $g(n) = h_n(n)$ Is this $g$ also primitive recursive?
1
vote
0answers
31 views

Multivariate Clenshaw Chebyshev Algorithm (downward recursion)

I have recently written a code where I use Clenshaw's summation formula with Chebyshev polynomials $S(x)=\sum_{k=0}^nc_kT_k(x)=b_0+xb_1$ $T_{k+1}(x)=2xT_k(x)-T_{k-1}(x)$ $T_0(x)=1~~~ T_1(x)=x$ ...
0
votes
0answers
8 views

Is there a primitive recursive real number which can not have a primitive recursive expansion?

A primitive recursive function which is primitive recursively convergent is called a primitive recursive real number. If $\{s_n\}$ is a (primitive) recursive real number and if $a_n$ is a (primitive) ...
0
votes
0answers
23 views

Recursive formula for mathematical expression

Assume that $\alpha , n,\lambda \in \mathbb{N}$,and $f$,$g$ two real valued functions defined on $\mathbb{N}$. Function $W$ is given by the following formula. \begin{equation} W(n) = \max_{1 \leq ...
1
vote
0answers
120 views

Solving a polynomial for cyclic roots

For any complex value of c, the following polynomial has 6 complex root values of p: $$1+c+2 c^2+c^3+p+2 c p+c^2 p+p^2+3 c p^2+3 c^2 p^2+p^3+2 c p^3+p^4+3 c p^4+p^5+p^6$$ For a general 6th order ...
0
votes
4answers
86 views

Explicit formula for $e_k = 4e_{k-1} + 5$

The sequence looks like this: $e_0 = 2$ $e_1 = 4(e_{1-1}) + 5 = 13$ $e_2 = 4(e_{2-1}) + 5 = 57$ $e_3 = 4(e_{3-1}) + 5 = 233$ $e_4 = 4(e_{4-1}) + 5 = 937$ How would I go about finding the ...
0
votes
0answers
22 views

Finding the Primitive Recursive Function for the Rem Function

When trying to show the remainder function is a primitive recursive function as defined to be as below (Copied from Proof Wiki): $\operatorname{rem} \left({n, m}\right) = \begin{cases} 0 & : ...
1
vote
1answer
40 views

Give a recursion for the number h(n) of strings in S of length n.

Let S be the set of strings on the alphabet {0,1,2,3} that do not contain 12 or 20 as a substring. Solving this I got: $$ h(n) = 4h(n-1) - 2h(n-2)$$ with $h(0) = 1, h(1) = 4,h(2) = 14 $. When I did ...
1
vote
2answers
101 views

Find the recursive definition for the number of strings on 0, 1, 2 avoiding the substring 012?

This is the question $a(n)$ the number of strings on $0, 1, 2$ avoiding the substring $012$ and the answer is $$a(n)=3a(n−1)−a(n−3)$$ with $$a(0)=1,a(1)=3,a(2)=9$$ My question is how to you get this ...
0
votes
0answers
12 views

Gaussian weighted intergal of Product of Gaussians

I'm trying to find a solution to the following function, My understanding is that the resultant function should still be a Gaussian, however I would like to define it as a linear function the ...
1
vote
1answer
41 views

Number of ways to choose $k$ subsets such that $ B_1 \cap B_2 \cap \cdot \cdot \cdot \cap B_k = \emptyset$.

Let $ \space n,k \in \mathbb Z \space $ such that $1 \le k \le n \space$. Let $\space A=\{1,2,...,n\}$. Find the number of ways to choose $k$ subsets $\space B_1,B_2,...,B_k\space $ of $A$ such that $ ...
0
votes
2answers
37 views

Recursive formula to 3x3 matrix

I was given a recursive formula and I need to convert it into a $3\times3$ matrix. What is a general formula to do this? My recursion is in the form: $$R_{n+2} = 4R_{n+1} + 5R_n + 2R_{n-1}$$ Just ...
4
votes
7answers
200 views

Convergence of $a_{n+1}=\sqrt{2-a_n}$

I'm attempting to prove the convergence (or divergence, though I strongly suspect it converges) of a sequence defined as $a_{n+1}=\sqrt{2-a_n}$ with $a_1=\sqrt{2}$. I cannot use the monotonic ...
0
votes
2answers
57 views

solve recursion $T(n) = T(\alpha n)+T(\beta n)+\gamma n$

I need solve this recursion: $$T(n) = T(\alpha n)+T(\beta n)+\gamma n$$ I know that for $\alpha +\beta< 1$ solution is $O(n)$ How is for $\alpha + \beta = 1$ and $\alpha + \beta > 1$?
0
votes
0answers
21 views

Recursion $T(m) = c_0 m + \sum\limits_{i=0}^{k}T(\lceil c_i m \rceil)$,$\sum\limits_{i=1}^{k}c_i < 1$ is linear

Let $L: \mathbb N_0 \to \mathbb N_0$ satisfy the recursion $T(m) = c_0 m + \sum\limits_{i=0}^{k}T(\lceil c_i m \rceil)$ with $c_i \geq 0$ for $i=0,\ldots, k$ and $\sum\limits_{i=1}^{k}c_i < ...
0
votes
0answers
28 views

Master Theorem for common recurrence

I have the following recurrence: $$T(n) = T\bigg(\frac{n}{2}\bigg) + O(n)$$ And I am trying to find the time complexity using the master theorem. So I have: $a = 1, b = 2$ $f(n) = O(n) = c(n)$ ...
0
votes
1answer
61 views

Find the order of elimination in Josephus Problem

Josephus Problem (or Josephus permutation) is a theoretical problem related to a certain counting-out game. People are standing in a circle waiting to be executed. Counting begins at the first ...
0
votes
2answers
26 views

Recurrence relations with multiplication

I have a recurrence relation and I am not quite sure if I am solving it correctly. The relation is this: $$t_n = 2n~t_{n-1}$$ where $t_0 = 1$ Here is how I went about solving this: First step is to ...
2
votes
1answer
52 views

Recursive formula for word problem.

I'm having problems with this recursion problem: Ann wants to buy along several weeks one dressing item which can be of two kinds: small ones -- hats and scarfs, and big ones -- dresses, suits, gowns ...
2
votes
1answer
53 views

How do you go about solving this recurrence?

How do you make an estimation for the substitution method, when the recursion tree did not help so much? I have a recurrence $$T(n) = 5\cdot T(n/3) + n (\log n)^2$$ And upon doing the recurrence ...
1
vote
1answer
57 views

Recursive definitions in formal logic

A binary tree $T$ is either A single vertex, or A graph formed by taking two binary trees, adding a vertex, and adding an edge directed from the new vertex to the root of each binary tree. Suppose ...
0
votes
0answers
17 views

recursion over $\arg \max$ function

I want to find a recursive/incremental update of the following equation: $\qquad d^{(n)} = \arg \max_{d=0:\,D-1} (s \cdot d + \sum_{i=1}^{N} f(x_i,d))$ where $d^{(n)}$ is the dimension number, $s$ ...
0
votes
1answer
37 views

Can we solve this recurrence relation using recursion tree method

The recurrence relation is given as follows: $T(n) = 2T(\sqrt{n})+1$ $T(1) = 1$ I tried to solve it with recursion tree as follows: But to find the number of levels that may occur, I have to ...
2
votes
0answers
14 views

Recurrence $x_{k+1} = \sum_{i=1}^m \theta_i x_{k+1-i} + r_{k+1}$ solution

Let $x_k$ be the solution of the recurrence equation $$x_{k+1} = \sum_{i=1}^m \theta_i x_{k+1-i} + r_{k+1}$$ where $(r_k)$ is a general sequence. I'm trying to find a explicit solution for $(x_k)$ ...
3
votes
2answers
48 views

How many tilings are there?

In the $n$-cell below, we are to tile it completely with cells of the form $\boxdot$ and $\boxtimes \hspace{-0.45 mm}\boxtimes$. How many tilings are possible for a $12$-cell? Let $H_n$ ...
2
votes
0answers
65 views

Closed form of $ a_n = 1 - \frac{a_{n-1} a_{n-2}}{4} $

Given the sequence $a_1 = 1$ and $a_2 = 1 $ with: $ a_n = 1 - \frac{a_{n-1} a_{n-2}}{4} $ Does there exist a closed form computing $a_n$ ? At the moment I have a problem getting a grip on the ...
0
votes
1answer
41 views

How to solve the recurrence relation $T(n)=aT(n-1)+bn^c$ with $T(1)=1$

How to solve this recurrence relation? $ T(n)=aT(n-1)+bn^c \\T(1)=1,$ where a, b, c are constant. I want to solve it using generating function, but get stuck. Could anybody help me?
0
votes
1answer
17 views

String recursive definition corner case

I need your assistance with a corner case of this problem: Find a recursive definition for the strings of odd length that start with "a" and end with "b" over the alphabet $\Sigma$={a,b}. I've ...
1
vote
2answers
63 views

Can the Recursion Theorem be proved in Peano Arithmetic?

A recursive function on $\mathbb{N}$ can be defined as follows: Given an element $a \in \mathbb{N}$ and a function $f:\mathbb{N}\rightarrow\mathbb{N}$, we can define a function ...
1
vote
1answer
107 views

Free Gliders for Everyone?

According to Feynman's Lecture on Computation (Problem 5.1, p. 148 ) you can extract $E=kTN\log 2$ out of two copies of a random $N$ bit random tape. From this we can conclude that it takes the same ...
0
votes
1answer
29 views

Proving that a certain function is not recursive

Consider the set $R_0=\{+,\cdot,I_<\}$, where $I_<$ is the characteristic function of the 2-ary relation $<$, and for every n let $R_{n+1}=\{p^n_1,...,p^n_n\}\cup R_n\cup C_n$, where ...
0
votes
1answer
22 views

Amount of times method is called in recursion

This is kind of a basic question, but its busting my head and I cant seem to grasp it. I know that when a recursive function (e.g: rec(int n)) is called recursively ...
0
votes
0answers
35 views

Rate of Convergence of $x_{k+1} = \frac 14 (x_k^2 +sin(x_k) + 1)$

I have shown that the fix point Iteration $$x_{k+1} = \frac 14 (x_k^2 +\sin(x_k) + 1)$$ has exactly one fix point $x^*\in[0,1]$ for every $x_0 \in [0,1]$ with the Banach theorem. Now I want to find ...
0
votes
0answers
75 views

Upper bound on successive difference inequalities

I would like to know tight upper bounds of the following equations perhaps some might have telescopic sum which can result in very tight bound.In the following equations assume $B\geq a_i \geq ...
1
vote
1answer
29 views

Order of growth of sequence $f_{n} = 2f_{n-1} + f_{n-2}$

I'm currently stuck with the following problem. How do I calculate the order of growth of the following sequence: $f_{n} = 2f_{n-1} + f_{n-2}$ Assuming that $f_{0} =1$ and $f_{1} = 1$ I've got ...
0
votes
0answers
45 views

The graph of Ackermman function is primitive recursive

For a relation $ R ⊆ ℕ^n $, define the characteristic function $ χ :ℕ^n → ℕ $ such that $ χ(x_1, x_2,..., x_n)=1 $, if $ (x_1,...,x_n) ∈R, χ(x_1,...,x_n)=0 $ otherwise. Say a relation is premitive ...
1
vote
1answer
36 views

How to solve this non-homogeneous recurrence?

I've made a few threads recently asking how to solve non-homogeneous recurrences and I think I've gotten the hang of it, but now I want to try a complicated thing like this: $T(n) = 4T(n-1) + 2T(n-2) ...
0
votes
1answer
29 views

How to solve non-homogeneous recurrences?

I am trying to find a way to solve non-homogeneous recurrences by solving the homogeneous and non-homogeneous parts separately. I can use generating functions for the whole thing, but I want to learn ...
3
votes
2answers
105 views

Is it possible to solve such a system?

I have the following two equations: $$P_t = \frac{t-1}{t}P_{t-1} + \frac{1}{t}Q_{t-1}$$ $$Q_t = \frac{1}{t} + \frac{t-1}{t}Q_{t-1} - \frac{1}{t}P_{t-1}$$ with $P_0 = 0$ and $Q_0 = 0$. As time goes ...
1
vote
0answers
48 views

How to solve even/odd divide-and-conquer problems?

I am looking into something called the Josephus problem, which seems to be popular, so I am sure there are lots of explanations online, but I want to do the work myself, but I do need a small push to ...
0
votes
1answer
392 views

A function f(n) satisfies the recurrence f(n)=4f(n/2)+n for real numbers. Give an upper bound for f(n)?

A function f(n) satisfies the recurrence f(n)=4*f(n/2)+n for real numbers. Give an upper bound for f(n)? I get somewhere T(n) = Θ(n^2), is that correct?
3
votes
2answers
169 views

Give an upper bound for a function satisfying $f(n)=4f(n−1)+n$ [closed]

A function $f(n)$ satisfies the recurrence $f(n)= 4f(n−1)+n$ for real numbers. Give an upper bound for $f(n)$. Is the attached picture the correct answer?
4
votes
2answers
227 views

HOW do you refactor a recursive function into a single equation

I have an initial equation which is very simple: answer1 = 0*2+2 But it is recursive such that: ...
0
votes
3answers
32 views

Compressing two recurrences

I have two recurrences $a_n = 9a_{n-1} + b_{n-1}$ $b_n = 9b_{n-1} + a_{n-1}$ Is there a way to combine these two so it's only in terms of $a_n$? $a_1 = 9, b_1 = 1$, if this information is needed.
1
vote
3answers
57 views

Show that the sequence $a_0 = 1$, $a_{n+1 }= \sqrt{2+a_n}$ is monotonically increasing

Given the sequence $a_0 = 1$, $a_{n+1}= \sqrt{2+a_n}$, how can I show that it is monotonically increasing? I need it to show, that the sequence converges. I already proved boundedness but I can't ...
1
vote
1answer
113 views

How to argue that a set is recursive or recursively enumerable?

I have the two sets listed below, and I want to argue whether each of them is recursive, recursively enumerable or neither recursive nor recursively enumerable. the set $A = \{ i | ...