The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
1answer
45 views

Solving the recurrence relation $T(n)=4T\left(\frac{\sqrt{n}}{3}\right)+ \log^2n$

How we calculate the answer of following recurrence? $$T(n)=4T\left(\frac{\sqrt{n}}{3}\right)+ \log^2n.$$ Any nice solution would be highly appreciated. My solution is: $n=3^m \to ...
2
votes
0answers
32 views

Solving the recurrence $T(n)=4T(\frac{\sqrt{n}}{3})+ \log^2n$ [on hold]

How we calculate the answer of following recurrence? $$T(n)=4T\left(\frac{\sqrt{n}}{3}\right)+ \log^2n.$$ Any nice solution would be highly appreciated.
1
vote
1answer
35 views

Recursive definitions of $n<m$, $n\mid m$, and $n \bmod m$

Without referring to the apparatus of (primitive) recursive functions one can introduce addition into the language of successor arithmetic by two additional axioms which naturally reflect the essence ...
3
votes
1answer
65 views

If a recursive sequence converges, must its inverse be divergent?

Suppose I have a recursive sequence $\displaystyle a_{n+1} = \frac{a_{n}}{2}$. Clearly, the sequence converges towards zero. Now, suppose I define an "inverse" sequence $\displaystyle b_{n+1} = ...
1
vote
1answer
32 views

find formula to count of string

I have to find pattern of count of series. Lenght of series is $2n$. It is neccessary to use exaclty double times every number in range $[1...n]$ and all of neighboring numbers are different. Look at ...
0
votes
1answer
40 views

Calculating the chance of something happening over and over again

I'm trying to calculate the probability, and potential cost on society, of people returning to homelessness after going through the system one, two, or several more times. Let's say that someone who ...
3
votes
2answers
35 views

Solving a Recursive equation, wrong options? [closed]

This is a very simple recursive formula. Are the options provided wrong? $$ T(n) = T\left(\frac{n}2\right) + 2 $$ with $T(1) = 1$. What's the solution when $n=2^k$ ($n$ is a power of $2$)? The ...
0
votes
3answers
48 views

Recursion Problem [closed]

a) Ten people are sitting in a row of ten chairs, chewing gum. Each person spits out his or her gum and places it either under his or her own chair or under an immediately adjacent chair. How many ...
3
votes
2answers
90 views

How to solve recursion?

I have tried to solve some recursion: $$f_n = \frac{2n-1}{n}f_{n-1} - \frac{n-1}{n} f_{n-2} + 1, \quad f_0 = 0, f_1 = 1$$ I would like to use a generating function: $$F(x) = ...
0
votes
0answers
26 views

Writing convergence acceleration algorithm as a recursion type formula

Cohen et al. describes an algorithm for speeding up the convergence of an alternating series as follows: Initialize: $$d=\left(3+ \sqrt{8}\right)^n; \quad d=\frac{1}{2} \left(d+ \frac{1}{d}\right)$$ ...
0
votes
2answers
22 views

given a total width and a given number of decreasing widths to fit that width, what is the % decrease

Hailing from the programming world here, maths has never been my strongest area. I have a width (TW), and that width must be divided by a given number(N) of smaller widths which decrease ...
0
votes
3answers
53 views

Finding general formula for a recursion function

If we have a recursion relation defined as $a_n = 3a_{n-1}+1$ with $a_1=1$ then find the general formula for $a_n$ in terms of $n$ with a(1) = 1. So far I have: $a_n = 3a_{n-2}+1+1 = 3a_{n-3}+1+1+1 ...
1
vote
1answer
31 views

How to simplify recursive eq?

I know how to programatically calculate this, but im not sure how it can be simplified for documentation. Can someone help? $R = (X\cdot 1) + (X\cdot 2) + (X\cdot 3) + (X\cdot 4) + (X\cdot 5) + ...
0
votes
0answers
140 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
1answer
40 views

Problems On Many-one Reducible [closed]

In computability theory and computational complexity theory, a many-one reduction is a reduction which converts instances of one decision problem into instances of a second decision problem. ...
0
votes
1answer
29 views

Closure Question in Enderton's 'Elements of Set Theory'

I am currently working on a follow-up question to the one I did here: Closure question from Enderton's 'Elements of Set-theory' I am unsure though whether I am on the right track with the ...
0
votes
2answers
30 views

Relations on set A and conditions of existence of descending chains

I am reading through the Elements of Set theory by Herbert Enderton and even though I have passed this exercise long ago,the more I look at my solution the less I believe it. Problem goes like this: ...
2
votes
1answer
16 views

Uniqueness in transfinite recursion.

Theorem of transfinite recursion: Given a well-ordered set $A$ let $\varphi(g,y)$ be a ZF formula such that for every $a \in A$ and every function $g$ with domain $I_a$ (where $I_a$ is the initial ...
0
votes
1answer
18 views

Why characteristic function is primitive recursive

I'm studying recursive functions and right now I stucked in this: "Natural numbers subset is PR if and only if characteristic function is PR". Why is that? Becouse it has values 0 ant s(0) only? So ...
0
votes
0answers
56 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
1answer
34 views

Iterated Functions - designing iterator to converge to constant value

I came across an interesting iterated function: $$ x_n = \frac{x_{n-1}}{x_{n-1} + b} $$ This is an extremely simple example and it converges to the constant $1-b$. Can someone provide some insight to ...
2
votes
1answer
14 views

Bounds on a recursively defined sequence

I have a sequence defined by $h_0=h_1=1$, $h_2=2$ and $h_{n+1}=(n+1)h_n + \frac{n(n-1)}{2}$. The paper I'm reading claims $n! \le h_n \le 2(n!)$. It is easy to show the first inequality by induction. ...
-1
votes
1answer
46 views

Does this recursive problem have a solution? [closed]

The variable $a$ starts at any value greater than $0$. Repeat this infinitely: $$a=a+f(a)$$ $$a=a-f(a)$$ Is there any function where $a$ will be greater than it was at its starting point?
0
votes
0answers
33 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.
1
vote
2answers
24 views

Discrete math and recursion problem.

I was recently reading up examples on recursion and how it relates to induction and there's this question I am not sure about. Q: Let $$b_1=3$$ $$b_n=n(n+2)$$ From that question I wanted to do the ...
2
votes
3answers
177 views

finding explicit formula

The question ask us to guess an explicit formula for the sequence $$y_k = y_{k-1} + k^2 ,$$ for all integers $k$ greater than or equal to 2 and $y_1 = 1$ Can someone help me with this? so far what ...
1
vote
4answers
55 views

finding explicit formula through substitution method

The question ask us to guess an explicit formula for the sequence $$t_k = t_{k-1} + 3k + 1 ,$$ for all integers $k$ greater than or equal to 1 and $t_0 = 0$ Can someone help me with this? Because I ...
1
vote
2answers
36 views

Guess explicit formula using iteration

The question ask us to guess an explicit formula for the sequence $$s_k = s_{k-1} + 2k ,$$ for all integers $k$ greater than or equal to one and $s_0 = 3$ Can someone help me with this? Because I ...
1
vote
1answer
28 views

Solving a second level functional equation over all functions $g$

I am trying to find a closed form expression $f$ such that $$f(g(x+1) - g(x)) + f(g(x) - g(x-1)) = f(g(x))$$ For all functions $g$ I have concluded that for polynomials $$2^{n+1}f(0) = f(a_0 + ...
1
vote
2answers
59 views

If a uniquness for all functions exist shouldn't there be uniquness to recursion?

What I'm specifically saying is every function is definitely unique, as they may be nearly equivalent to another function, for example. Let's make a table of values for $^{x}2$ (0,1) (1,2) (2,4) ...
0
votes
1answer
21 views

Check these recursive definitions for me?

Looking for Give a recursive definition of A) the set of odd positive integers B) the set of positive integer powers of 3 C) the set of polynomials with integer coefficients I have a. Basis: ...
2
votes
1answer
60 views

Use principle of mathematical induction to show a function defined recursively is uniquely determined.

I'm having difficulty with the following taken from "Elementary Number Theory And Its Applications" by Rosen section 1.1 questions. "Use the Principal Of Mathematical Induction to show that the value ...
1
vote
1answer
29 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
22 views

Resolve a recursive series

Consider the following recursive function: $f(n) = 1 + \sum_{i=0}^{n-1} f(i)$ with $f(0)=1$ I need to derive a non recursive form. By simply trying values, I have inferred that it must be ...
1
vote
0answers
32 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 ...
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 ...
1
vote
1answer
87 views

linear recursion $y_n=A \cdot y_{n-1}$

Let $a,b, \in \mathbb{R}$. Let $x_0=a, x_1=b$ and $x_n=\frac{x_{n-1}+x_{n-2}}{2}$ for $n \geq 2$ (i) Write the recursion in the form $y_n=A \cdot y_{n-1}$ where $A$ is a $2 \times 2$ matrix and ...
2
votes
2answers
138 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
54 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 ...
5
votes
1answer
87 views

Compute a probability in Random Walk by Martingales

Let $X_n$ be the state at time $n$ of a Markov chain with these transition probabilities : $$p_{i,i+1}=p_i\qquad,\qquad p_{i,i-1}=q_i=1-p_i$$ $(a)$ Show that $Z_n=g(X_n)\,;\,n\geq0$, is a ...
1
vote
1answer
28 views

Recursive sum of squares of prime numbers

Perfect squares always have recursive sum of their digits(e.g. $361\rightarrow 10 \rightarrow 1$) as either $1, 4, 7$ or $9$. But if the perfect square is square of a prime number, except of $3$ . ...
2
votes
3answers
330 views

recursive digit sum of cubes of integers.

For every cube of an integer, the recursive sum of its digits , e.g. 729 -> 18 -> 9 etc. is always 1,8 or 9. With a computer program i checked this phenomenon up to 1000000000. In my prior ...
-1
votes
2answers
46 views

Define this recursively : $f(n) = 3n - 4$

Define this recursively : $f(n) = 3n - 4$ I thought this is how you recursively define a function? $f^{-1}(n): y = 3n-4$ $y+4 = 3n$ $f^{-1}(n) = (y+4/3)$ But the answer is $f(n) = f(n-1) + B$ ...
0
votes
0answers
30 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 ...
2
votes
0answers
44 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
2answers
49 views

Master theorem - why the log factor?

I think I finally managed to fully understand the master theorem but there's one thing left in the second clause (I'm following here: ...
1
vote
1answer
31 views

Coloring a binary tree

Working through a problems practice coloring, I have found a problem that has me stumped. The problem states: For $n \in \mathbb{R}_{>o}$ the binary tree is defined recursively as follows. The ...
0
votes
1answer
59 views

Recursive Function - $f(n)=f(an)+f(bn)+n$

I've got this recursive function $f(n)=f(an)+f(bn)+n$, and I need to find $θ$ on $f(n)$, as $a+b>1$. Using a recursive tree, I managed to bound it by $n\log(n)$ from the bottom and by $n^2$ from ...
1
vote
2answers
84 views

Use the recursive definition of summation together with mathematical induction to prove a sequence

Use the recursive definition of summation together with mathematical induction to prove that for all positive integers $n$ if $a_1, a_2,\ldots, a_n$ are real numbers, then $$\sum_{k=1}^n(3a_k - 2k + ...
1
vote
2answers
103 views

Find an explicit formula for the recursive sequence (tips?)

Problem: A sequence is defined recursively as follows: Sk = 2k - Sk - 1, for all integers k greater than or equal to 1 S0 = 1 Use iteration to guess the explicit formula for the sequence. Use ...