The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
3answers
34 views

How do I prove convergence of this recursive sequence, what's the limit?

I have this sequence: $c_n = c_{n-1} + \frac{0.01}{n}, \ \ c_1 = 0.01$ How do I prove the convergence of this, and what is the limit?
8
votes
1answer
63 views

Prove that $a_n$ is a perfect square if $n$ is even without generating functions or Taylor series.

Let $a_n$ be the number of positive integers whose digits are all $1$, $3$, or $4$, and add up to $n$. For example, $a_5 = 6$, since there are six integers with the desired property: $41, 14, 311, ...
0
votes
1answer
34 views

Height of Recursion Tree for $T(n, k) = T(n/2, k) + T(n, k/4) + kn$

If we use a recursion tree for solving $$\begin{cases} T(*,1)=T(1,*)=a \\ T(n,k)=T(n/2,k)+T(n,k/4)+kn \end{cases}$$ What is the height of the recursion tree? Any idea or solution highly ...
0
votes
2answers
38 views

Solving a recurrence relation with square root

I ran into a bad recurrence relation. Anyone would calculate T(n) or add some hint? $$T(n) = \begin{cases} n,\quad &\text{ if n=1 or n=0 }\\ \sqrt{1/2[T^2(n-1)+T^2(n-2)]+}n ,\quad ...
14
votes
1answer
236 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 exemple. How to calculate the number of circuits that visit ...
0
votes
1answer
58 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
33 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
38 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
67 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
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 ...
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
49 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) = ...
5
votes
2answers
212 views

Repertoire method for solving recursions

I am trying to solve this four parameter recurrence from exercise 1.16 in Concrete Mathematics: $g(1) = \alpha;$ $g(2n+j) = 3g(n) + γn + β_j$ : j = 0,1 and n >= 1 I have assumed the closed form to ...
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 ...
13
votes
4answers
483 views

Find all bijections $\,\,f:[0,1]\rightarrow[0,1]\,$ satisfying $\,\,f\big(2x-f(x)\big)=x$.

A friend of mine gave me the following problem: Find all functions $f:[0,1]\to[0,1]$, which are one-to-one and onto and satisfy the functional relation $$ f\big(2x-f(x)\big)=x, \tag{1} $$ for all ...
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
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
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. ...
2
votes
4answers
116 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 ...
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
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
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.
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
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 ...
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 ...
2
votes
3answers
178 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
2answers
38 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: ...
3
votes
2answers
123 views

Is there a recursive formula for Euler's Totient function

I have been looking for a recursive formula for Euler's totient function or Möbius' mu function to use these relations and try to create a generating function for these arithmetic functions.
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
90 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 ...
0
votes
4answers
1k views

Find a formula for a sequence of number

A sequence starts at $n=1$: $\{1, 4, 13, 40, 121, 364... \}$. Find an explicit formula that generates these numbers. Thanks a lot!
3
votes
1answer
3k 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?