# Tag Info

## Hot answers tagged recursion

5

Given that, when $0<x<1$ you have $$x>\sin x >x\left(1-\frac{x^2}6\right)$$ you get, when $x=1/n$ for $n\geq 2,$ \begin{align}\sin\frac1n&>\frac{n^2-1/6}{n^3}\\&>\frac{n^2-1}{n^3+1}\\&=\frac{n-1}{n^2-n+1}\\&=\dfrac{1}{n+\frac{1}{n-1}}\\&\geq \frac1{n+1} \end{align} So $\sin(1/n)\geq \frac{1}{n+1}.$ So let $x_n=f^n(x)$...

3

This answer assumes you know how the closed formula for $x_n$ corresponds to the roots of the polynomial: $$p(x)=x^m-a_{m-1}x^{m-1}-\cdots-a_0$$ Assuming indices start at $i=0.$ The sequence $$y=(2,0,4,0,8,0,\dots)$$ can be written as: $$y_i=\frac{(\sqrt 2)^{i+2}+(-\sqrt 2)^{i+2}}{2}$$ Similarly, $$z=(0,3,0,9,0,\dots)$$ can be written: $$z_i=\frac{(\sqrt 3)^{... 3 There's an empty function of each arity: specifically, the empty function of arity n is the partial function e^n: \subseteq\mathbb{N}^n\rightarrow\mathbb{N} whose domain is \emptyset. Put another way, its graph \{(a_1,...,a_n, b): e^n(a_1,...,a_n)\downarrow=b\} is \emptyset, where "\downarrow=" means "is defined and equal to." ... 2 The most natural way to prove this, in my opinion, is via the "syntactic" approach to computability. Specifically, use the following results: Fact 1: If \theta(x_1,...,x_n) is \Delta^0_0 (that is, only uses bounded quantifiers), then the function$$t_\theta(x_1,...,x_n)=\begin{cases} 1&\mbox{ if }\theta(x_1,...,x_n),\\ 0&\mbox{ ...

2

If both $B$ and $C$ were to be recursive, then their characteristic functions $\chi_B$, and $\chi_C$ would be recursive, and thus since $\chi_A = \chi_B + \chi_C$ plus the fact that recursive functions are closed under addition, $\chi_A$ would be recursive and therefore $A$ too. When saying $\chi_A = \chi_B + \chi_C$ I used the fact that $B \cup C = A$ and ...

2

Your judgement is correct, at least one of B or C must be non-recursive, since recursive sets are closed under (finite) union. This is fairly simple to prove, as given a procedure for deciding B and a procedure for deciding C, one can create a procedure for deciding B union C = A that is simply to run the procedure for B and the procedure for C, and return ...

2

I am sure that you will make "stand up" your recursive proof. I propose here a different approach with a kind of geometrical flavour. Let us take the inverse of both sides of the defining relationship: $$\frac{1}{a_{n+1}}=\frac{1}{2a_{n}}+\frac{1}{2} \tag{1}$$ Setting $b_n=\frac{1}{a_{n}}$, (1) becomes: $$b_{n+1}=\frac{1}{2}(b_n+1)\tag{2}$$ (2) ...

1

We prove by induction. For $n = 1$, since we have for the denominator $0 <1-x_1^2 <1$, the inequality holds. Assume the inequality holds for $n=k$, giving us $$\sup_{1\le i \le k} x_i^2 \leq \color{red}{\frac{x_1^2}{1-x_1^2}}$$ For $n = k+1$, we have \begin{align} x_{k+1}^2 \le x_1^2 + x_k^4 (1-x_1^2) &\le x_1^2 + \left( \frac{x_1^2}{1-x_1^2} \... 1 Welcome to MSE! If you want, you can solve this using generating functions. In particular, if we writeS(x,y) = \sum_{x,y} s(i,j) x^i y^j$$we can use your recurrence to find$$S(x,y) = \frac{1}{1 - (x + xy + y)}.$$Then we can get a closed form for s(i,j) by getting a closed form for the coefficients in a taylor expansion of S. Thankfully, though, ... 1 What if you tried to show that a_n is montonous, and bounded ?. Hint : what is the sign of a_n ? of a_n - a_{n+1} ? With that, you should be able to conclude. 1 It is$$a_{n+1} = \frac{2a_n}{1+a_n} = \frac{2*\frac{2^{n+1}}{2^{n+1}-1}}{1+\frac{2^{n+1}}{2^{n+1}-1}} = \frac{2^{n+2}}{2^{n+1}-1+2^{n+1}} = \frac{2^{(n+1)+1}}{2^{(n+1)+1}-1} where the hypothesis is used in the second step.

1

You've got the right idea, but you made a mistake trying to initially add one more term to the summation and then subtract it, as this leads to dealing with $f\left(\frac{1}{c}\right)$ which is not defined. Here is how you can proceed instead starting from the second line of your induction step, with the steps below being similar to what you also did later: \$...

Only top voted, non community-wiki answers of a minimum length are eligible