Tag Info

Hot answers tagged

4

Given that: $$\frac{x_{n+1}}{y_{n+1}}=\frac{x_n}{y_n}+\frac{1}{x_n y_n}$$ we have: $$\frac{x_{n+1}}{y_{n+1}}=\frac{1}{x_n y_n}+\frac{1}{x_{n-1} y_{n-1}}+\ldots+\frac{1}{x_1 y_1}+\frac{x_1}{y_1}$$ or just: $$\frac{x_{n+1}}{y_{n+1}}=\frac{1}{x_n\cdot\ldots\cdot x_1}+\frac{1}{x_{n-1}\cdot\ldots\cdot x_1}+\ldots+\frac{1}{x_1}+2.$$ Hence we need to prove that: ...


3

Your iterated map is given by: $$f_{\mu}(x)=x^2+\mu$$ Your fixed points are correctly given as: $$x_{1,2}=\frac{1}{2}(1\pm\sqrt{1-4\mu})$$ If a period change occurs at the fixed point $x_1$, then necessarily $$|f'(x_1)|\ge 1$$ so it suffices to solve the equation: $$|f'(x_1)|= 1\Rightarrow$$ $$|2x|_{x=x_1}=1\Rightarrow$$ ...


3

This is supposed to be a comment but I can't fit it into the comment box. Even if you have $f(x) = h(x)$ for all $x > $ some $M$ and $|f(x)-h(x)| \ll 1$ over $[0,M]$, the two sequences $(x_n)$, $(y_n)$ defined by $$ x_n = f^{\circ (n-1)}(1) = \begin{cases}1, &n = 1\\ f(x_{n-1}), & n > 1\end{cases} \quad\text{ and }\quad y_n = h^{\circ ...


2

Here's an another approach solving the recurrrence relation \begin{align*} x_0&=3\\ x_1&=4\tag{1}\\ x_{n+1}&=x_{n-1}^2-nx_n\qquad\qquad n\geq 2 \end{align*} But first a few words to your classification of this recurrence relation. You're right when you're saying it's neither a linear nor a non-linear homogeneous recurrence relation with ...


2

$T(n)-T(n-1)=\log^2(n)$, then $(T(n)-T(n-1))+(T(n-1)-T(n-2))+\ldots+(T(2)-T(1))=\log^2(n)+\ldots+\log^2(2)$, so $T(n)-T(1)=\log^2(n)+\ldots+\log^2(2)$, $$T(n)=T(1)+\sum_{k=2}^n\log^2(k)$$.


1

Nice question! Let $a_n$ be the number of desired arrangements for an $n$ by $3$ matrix and we'd like to find a recursive formula for it. For the sake of simplicity, let $1$ denote the use of a $1 \times 3,$ block $2$ denote the use of a $1 \times 2$ block and $3$ the use of a $1\times 1$ block. Let also $1v$ denote the use of a vertical $1 \times 3$ block ...


1

That doesn't seem quite right! Assume we're at the stage where we have $k$ sorted array, each of size $m$ and we'd like to know how many comparisons are needed to form the final sorted array. Take the first two arrays, each of size $m,$ we need $2m-1$ comparisons to make a sorted array, then take the third and fourth arrays, again with $2m-1$ comparisons ...


1

Say the sequence $(a_n)$ defined by $a_{n+1} = f(a_n)$ for bijective $f$ converges to $a$. If $f$ is continuous at $a$, then $$0 = \lim\limits_{n \to \infty} a_ {n+1}-a_n = \lim\limits_{n \to \infty} f(a_n)-a_n = f(a)-a$$ So $f(a)=a$. But then it also follows that $f^{-1}(a)=a$. So if the inverse sequence is started with seed value $b_0 = a$, the inverse ...


1

Hint: Consider the sequence $a(n)=T(n)^2$. This sequence satisfies the recurrence relation $a(0)=0, a(1)=1$ and $$ a(n) = T(n)^2=\frac{T^2(n-1)+T^2(n-2)}{2}+n = \frac{1}{2}a(n-1)+\frac{1}{2}a(n-2)+n, $$ for $n\geq 2$. Can you solve it from here?


1

It depends on $n$ being odd or even so we'll deal with these separately: Odd: The minimum is as how you've drawn it for $n=5$. We have: Cells down the first $\frac{n-1}{2}$ vertical lines: $\frac{n-1}{2} \times n$. Extra cells across the first $\frac{n-1}{2}$ horizontal lines: $\frac{n-1}{2} \times \frac{n+1}{2}$. Extra cells for the diagonal: $1$. ...


1

If $n$ is the length of string and $m$ the size of the dictionary, DP will use $O(n)$ space and $O(nm)$ time at most if you want to find just one solution. As you have to list all solutions, the time is exponential in $n$ because of the many possible solutions (think of "$aaaaa\ldots a$" with dictionary "$a$", "$aa$").



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