# Tag Info

14

For any block of consecutive elements of the sequence, the products of consecutive pairs form another block that will appear somewhere further on. The following blocks form a cycle in this manner: $$8, 8, 8 \to 6, 4, 6, 4 \to 2, 4, 2, 4, 2, 4 \to 8, 8, 8, 8, 8$$ Since $8, 8, 8$ appears in the sequence starting at position 72, there will be an infinite ...

9

You have: $$(n^2-1)\,a_{n+1} = n^2 a_n - 1,$$ that by putting $b_n = n a_n$ becomes: $$(n-1) b_{n+1} = n b_n - 1,$$ or: $$\frac{b_{n+1}}{n}-\frac{b_n}{n-1}=-\frac{1}{n(n-1)}=\frac{1}{n}-\frac{1}{n-1},$$ so if we set $c_n=\frac{b_n}{n-1}=\frac{n}{n-1}a_n$, we end with: $$c_{n+1}-c_{n} = \frac{1}{n}-\frac{1}{n-1}.\tag{1}$$ If $c_2=2a_2=200$ (notice that only ...

8

The answer in NO. We shall show that: there is no open neighbourhood of $z=\frac{1}{2}$, where the iterates of $f(z)=z^2+\frac{1}{4}$ remain bounded. Take $z_0=\frac{1}{2}+\varepsilon$, where $\varepsilon>0$. Then the sequence $$z_{n+1}=f(z_n), \,\,\,n\in\mathbb N,$$ is strictly increasing and thus convergent in $(0,\infty]$. But if it had a finite ...

6

To find $a_n$ for every $n\geqslant2$, one can use the trick of centering a recursion around its fixed point. Here $a_n=1$ would imply $a_{n+1}=1$, hence one can consider the sequence $b_n=a_n-1$, and, see what happens! one gets $$b_{n+1}=\frac{n^2}{n^2-1}b_n.$$ Thus, for every $n\geqslant2$, $$a_n=1+A_n\cdot(a_2-1),\qquad ... 5 Let the total number of such words on n letters be s_n. Let the number of words which end with a be a_n and the number of words which end with b be b_n. Now consider a word on n-1 letters. We may add c or d to the end of the word to obtain a new word on n letters. Conversely, all words on n letters which end with c or d can be ... 4 Here is an estimate that gives a good approximation of \binom{4n}{2n} in terms of \binom{2n}{n}. Using the identity$$ (2n-1)!!=\frac{(2n)!}{2^nn!}\tag{1} $$it is straightforward to show that$$ \frac{\binom{4n}{2n}}{\binom{2n}{n}}=\frac{(4n-1)!!}{(2n-1)!!^2}\tag{2} $$Notice that$$ \begin{align} \frac{(2n-1)!!}{2^nn!} ...

3

Don't worry so much about the $\frac{a(x)}{b(x)}$ part -- the main difficulty of the problem is finding a form for that ugly looking polynomial. Let $d_i = 2*3^i$ and $e_i = (-1)^i i^2$. Then $c_i = d_i - e_i$. Define $d(x)$ and $e(x)$ similarly. $d(x) = 2 + 6x + 18x^2 + 54x^3 + \dots = \frac{2}{1 - 3x}$ Next, $\displaystyle \sum_{i = 0}^{\infty} (-x)^i ... 3 Unfortunately this formula $$M_n(t)=I+\sum_{j=0}^n\left(\int_{t_0}^t A(s)\,ds\right)^{\!j}$$ is not in general true. It is true if$A(s)A(t)=A(t)A(s)$, for all$s,t$. In order to show that$M_n$converges uniformly to some$M$, you basically need to follow the steps of the proof of Picard-LindelĂ¶f. So, subtracting $$M_n(t)=I+\int_{t_0}^t ... 2 This is the same as Yiorgos' answer, but I was writing mine when I discovered his... Choose any submultiplicative norm on the space of matrices (i.e. \Vert AB\Vert\leq\Vert A\Vert\,\Vert B\Vert). Also, for any matrix-valued function \Phi on [t_0,t_1], set \Vert\Phi\Vert_\infty:=\sup \{ \Vert \Phi(t)\Vert;\, t\in [t_0,t_1]\}. Since A is ... 2 Hint: show (by induction) that for all n \geq 0, 1\leq a_n < \frac{1+\sqrt{17}}{2}; use the right inequality to show that a_n is an increasing sequence; use these two points (monotone convergence) to argue that a_n\nearrow a\in\left(1,\frac{1+\sqrt{17}}{2}\right]; using the fact that the recurrence relation has only two fixed points, and that ... 2 Here are two thoughts, either one may help.$$\begin{split} T(n) &= n^{1/2} T\left(n^{1/2}\right) + cn \\ &= n^{1/2} \left[ n^{1/4} T\left(n^{1/4}\right)+cn^{1/2} \right] + cn\\ &= n^{1/2+1/4} T\left(n^{1/4}\right) + cn^{1/2+1/2} + cn\\ &= n^{1/2+1/4} \left[ n^{1/8} T\left(n^{1/8}\right)+cn^{1/4} \right] + 2cn\\ &= ... 2 We assume that the fly can be at any one of$60$positions, and that in any flight, it chooses at random one of the$59$other positions to go to. Say it starts at position$A$. We want to find the probability that after$n$flights it ends up at$B$, where$B$is a particular position other than$A$. Let this probability be$p_n$. We have$p_0=0$. The ... 2 Multiplication it is! We prove this by induction on$a$and$b$. Base:$f(0,b)=0$by definition and$f(a,0)=f(0,a-1)+0=0$Induction hypothesis:$\forall n<a$and$\forall m<b$,$f(n,m)=f(m,n)=m\cdot n$Induction step: We must prove that$f(a,b)=f(b,a)=a\cdot b. We have \begin{align} f(a,b)&=f(b,a-1)+b\\ &=f(a-1,b-1)+a+b-1 \end{align} But by ... 2 Okay, I will use a different notation to you (because I am more used to it). I will setx_n = F(n)$, so your equation becomes $$x_n = a x_{n-k+1} + b x_{n-k+2} + c x_{n-k+4}.$$ Now, set $$\mathbf x_n = \begin{pmatrix} x_n \\ x_{n-1} \\ \vdots \\ x_{n-k+2} \end{pmatrix}$$ and given your equation, we have: $$\mathbf x_n = \underbrace{ \begin{pmatrix} 0 ... 2 Hint: You're probably best off looking at a recurrence relation. Note that there are only two ways to cover the left-most two squares: either a single vertical brick, or two horizontal bricks. What does this tell you about how you can write x_n in terms of x_{n-1} and x_{n-2}? Note that if you cover those two left ones with a single vertical brick, ... 2 There can't be any multiplicative formula of the sort you describe for 4n\choose 2n in terms of 2n\choose n, because there are prime factors of the former that aren't factors of the latter. By Bertrand's Postulate there's a prime number between k=2n and 2k(=4n); that prime will be a factor of 4n\choose 2n, but can't be a factor of 2n\choose n ... 2 Concerning the first question. Let's rewrite the generation-rule of the columns of your table t(n,k) (where it would be helpful a) if we would write t(r,c) to make clear what is column- and what row index and b) if it would be explicite, whether it begins wiith 0 or 1 - there are different conventions around). Well. For column 0 we have$$ x_{0} = 1 ... 2 For every$a\gt1$, the sequence$(S_a(k))$defined by $$S_a(k)=a^{-2^k}\cdot T(a^{2^k}),$$ is such that$S_a(k)=S(k-1)+O(1)$, hence$S_a(k)=O(k)$, that is, $$T(a^{2^k})=O(k\cdot a^{2^k}).$$ This means that$T(n)=O(n\log\log n)$when$n$is restricted to some sequence$(a^{2^k})$but DOES NOT imply that$T(n)=O(n\log\log n)$for the complete sequence ... 2 In general, the solution of a recursion$a_n = A a_{n-1} + B a_{n-2}$is of the form$a_n = C \lambda_1^n + D \lambda_2^n$, where$\lambda_{1,2}$are the roots of$\lambda^2 - A \lambda - B = 0$. You can find$C$and$D$by plugging in$n=0$and$n=1$. For the Fibonacci sequence, one of$\lambda_{1,2}$is equal to the golden ratio. 1 I'm guessing your recurrence is:$a_n -7a_{n-1} +10a_{n-2}=0 \longleftrightarrow a_n = 7a_{n-1}-10a_{n-2} \longleftrightarrow a_{n+2} = 7a_{n+1} -10a_n $. Let's say$a_0=0$,$a_1=1$for sake of example. Set$F(x) = a_0 + a_1x + a_2x^2+\ldots = \sum_{n=0}^{\infty} a_nx^n $So$\frac{F(x) - a_0}{x} = a_1 + a_2x + a_3x^2+\ldots =\sum_{n=0}^{\infty} ...

1

In terms of recurrence relations, homogenous relates to linear recurrences. In the Fibonacci example, $F_{n+2}=F_{n+1}+F_n$ is homogeneous since it is linear in the sequence elements without further constants. Scaling the sequence gives another solution. Homogenous linear recurrences with constant coefficients can be solved with an exponential or geometric ...

1

The matrix of Eulerian-numbers might help here. There are two (only slightly) different definitions; let's use that of the matrix which begins with $$E=\small \begin{bmatrix} 1 & . & . & . & . & . \\ 1 & 0 & . & . & . & . \\ 1 & 1 & 0 & . & . & . \\ 1 & 4 & 1 & 0 & . & . ... 1 Hint: If 0\lt a_n\lt1, then 1\lt2-a_n\lt2, therefore,$$ \begin{align} a_{n+1} &=a_n(2-a_n)\\ &\gt a_n \end{align} $$Furthermore,$$ \begin{align} a_{n+1} &=a_n(2-a_n)\\ &=1-(a_n-1)^2\\ &\lt 1 \end{align} $$After showing the limit exists, take limits:$$ \begin{align} \lim_{n\to\infty}a_n &=\lim_{n\to\infty}a_{n+1}\\ ...

1

You need to evaluate how many calls there are caused by function of $n$. How many times is the loop executed? What happens inside the loop? If $T(n)$ is the time complexity of the function, you have $T(n)=$(number of times through the loop)*(time complexity of what happens in the loop). Can you figure these out?

1

And here is a completely different way of doing it - I'll leave you to work out for yourself what it means ;-) $$\matrix{\bullet\cr}\qquad \matrix{\bullet&\circ\cr \circ&\circ\cr}\qquad \matrix{\bullet&\circ&\bullet\cr \circ&\circ&\bullet\cr \bullet&\bullet&\bullet\cr}\qquad ... 1 If you've done linear algebra, there are techniques for solving linear recurrence relations. A (second order) linear recurrence is one of the form a_{n+1}=\lambda a_n+\mu a_{n-1}. This one isn't quite linear because of the +1, so let's try and remove that. The obvious way is to define:$$b_{n+1}=2b_n+b_{n-1}$$In the hopes that its behavior will ... 1 Your T(n) is not the Fibonacci sequence, but that doesn't matter; the asymptotic growth is still the same. Indeed, set U(n) = T(n) + 1, so that the recurrence relation becomes$$U(n) = U(n-1) + U(n-2).$$Now suppose you want to prove that T(n) = O(\alpha^n) (or equivalently, that U(n) = O(\alpha^n)) for some \alpha. This means that for all n \ge ... 1 Here is a start. First shift the index, then rearrange as$$ a_n = 3a_{n-1}-3a_{n-2}+a_{n-3} \implies a_{n+1} = 3a_{n}-3a_{n-1}+a_{n-2}  \implies a_{n+1} - a_n= 2(a_{n}-a_{n-1})-(a_{n-1}-a_{n-2}) $$Now, use c_n= a_{n+1}-a_n  in the last equation to get a recurrence relation of degree 2 in terms of c_n. I think you can finish it. 1 Well, I can at least get you to generating functions for the two sequences, in the relaxed case: Let F(z) and G(z) be the generating functions for f and g, respectively:$$ F(z):=\sum_{t=0}^{\infty}f(t)z^t\qquad G(z):=\sum_{t=0}^{\infty}g(t)z^t $$Then$$\begin{align*} F(z)&=\sum_{t=0}^{\infty}f(t)z^t\\ ...

1

For your josephus problem, the recursion has one function call for each of n, n-1, n-2,...,1, so that $T(n)=O(n)$ is the expected outcome. The $T(2n)=c\cdot T(n)+O(1)$ behavior occurs typically for divide and conquer algorithms like efficient integer powers, Karatsuba multiplication and other fast multiplication algorithms, FFT. There you can consider the ...

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