# Tag Info

5

Even though this has been answered with a useful hint that basically says it all, the OP seems to ask for more detail, so here are a few additional steps. The trick is to use exponential generating functions. First divide the recurrence by $(n+2)(n+1),$ to get $$\frac{y_{n+1}}{(n+2)(n+1)} - \frac{1}{2} \frac{y_n}{(n+1)} = 3^n.$$ The exponential generating ...

4

$$a_{n+1} = a_n (1+a_n)$$ .................. So, with or without closed form, there is some positive real $\theta$ such that $$a_n \approx \theta^{\left( 2^n \right)}$$ and $\theta$ can be approximated by $a_n^{1/2^n},$ while $\log \theta$ can be approximated by $\frac{\log a_n}{2^n}.$ EEddIItt: Convergence for $\theta$ should be rapid. I get that ...

4

Let $(u_n)$ denote the sequence of Fibonacci numbers. By definition, $$u_{n+2} = u_{n+1} + u_n\quad\text{and}\quad u_{n+3} = u_{n+2} + u_{n+1} = 2u_{n+1} + u_n,$$ so that using $(x+y)^2 = x^2 + y^2 + 2xy$, $$a_{n+2} = a_{n+1} + a_n + 2u_n u_{n+1},\quad\text{and}\quad a_{n+3} = 4a_{n+1} + a_n + 4u_nu_{n+1}.$$ Finally, for all $n$ one has: $$a_{n+3} - ... 4 You’re just missing a little algebra. You have U_n=T_n+1 for all n\ge 0, so U_{n-1}=T_{n-1}+1, and therefore 2T_{n-1}+2=2(T_{n-1}+1)=2U_{n-1}. Combine this with T_n+1=2T_{n-1}+2, and U_n=T_n+1, and you get U_n=2U_{n-1}, with U_0=1. Now notice that U_n is just doubling each time n is increased by 1:$$\begin{align*} U_1&=2U_0\\ ...

3

This was answered in Marko Petkovsek's Thesis (who also implemented the algorithm in mathematica). Presumably (but not certainly), a more expository account is given in Petkovsek/Zeilberger's A=B (which is available for free).

3

Let $a_n$ be the number of legal strings of length $n$ that end in $A$, $b_n$ the number that end in $B$, and $c_n$ the number that end in $C$. Let $d_n=a_n+b_n+c_n$; $d_n$ is the total number of legal strings of length $n$. Then \begin{align*} &a_n=a_{n-1}+b_{n-1}\;,\\ &b_n=b_{n-1}+c_{n-1}\;,\text{ and}\\ &c_n=a_{n-1}+b_{n-1}+c_{n-1}\;. ... 3 In the image below, the blue line is the function y=\sqrt{0.2 x+0.9x^2}. The purple line is y=x. When you evaluate the function at x<2, you go up to the blue line (that's the next x value). Then, you go to the right to the purple line, to get x[t+1]=y=f(x[t]). From the purple line, you go up again to the blue line, to get f(x[t+1]). This ... 2 The formula T(x)=\mathrm e^{x+x^2/2} is correct and yields\sum_{n\geqslant0}\frac{T_n}{n!}x^n=\mathrm e^x\cdot\mathrm e^{x^2/2}=\sum_{i\geqslant0}\frac1{i!}x^i\cdot\sum_{k\geqslant0}\frac1{2^kk!}x^{2k} $$hence$$ T_n=\sum_{0\leqslant2k\leqslant n}\frac{n!}{2^kk!(n-2k)!}=\sum_{0\leqslant2k\leqslant n}(2k-1)!!\cdot{n\choose2k}. $$This is sequence ... 2 You're likely to get a comment about asking multiple questions as one big one, but to get you started, I'll do an iterative expansion. Let n=2^k, since strictly speaking those are the only values for which your recurrence makes sense. Then your recurrence takes the form$$ T(2^k) = 2^2T(2^{k-1})+2^{2k}k $$Now let's iterate$$\begin{align} T(2^k) &= ...

2

Let $S_k=4^{-k}T(2^k)$, then $S_k=S_{k-1}+k$ for every $k\geqslant1$ and $S_0=1$ hence $S_k=\sum\limits_{i=1}^ki=\frac{k(k+1)}2$. Thus, $T(2^k)=4^k\frac{k(k+1)}2=\Theta((2^kk)^2)$ and, although nothing allows to deduce this, users asking this kind of question on the site seem to consider this is enough to show that $$T(n)=\Theta((n\log n)^2).$$

2

Depending on your context and needs you can either view it as iteration of a function: $$f^{12}(100) \qquad\text{where }f(z)=zy-x$$ or you can apply the distributive law and get $$100y^{12} - xy^{11} - xy^{10} - \cdots - xy^2 - xy - x$$ which after a bit more rearrangement becomes $$100y^{12} - x\frac{y^{12}-1}{y-1}$$

2

Your problem is that you are assuming that the number of such strings of length $n-1$ starting with $0$, $1$, and $2$ are all equal (and so getting your figures of $\frac{2}{3}a_{n-1}$ by removing the ones which start with a $0$, for instance). This is not in fact the case, as you can see by looking at the strings of length $2$: there are three such strings ...

2

Direct Method Putting $y_n=(n+1)!2^{1-n}x_n$ the recurrence relation $$y_{n+1}−\frac{n+2}{2}y_n=(n+1)(n+2)3^n\tag 1$$ with initial condition $y_0=0$ forall $n\ge 0$, becomes $$x_{n+1}=x_n+\frac{6^n}{n!}. \tag 2$$ with initial condition $x_0=\frac{y_0}{2}=0$. This is a non-homogeneous recurrence relation with non-homogeneous term $\xi_n=\frac{6^n}{n!}$ ...

2

If $a_n$ is the number of possibilities of length $n$ and $A_n$ is the number of those which end with A then you have: $$a_n=3a_{n-1}-2 A_{n-1} \text{ and } A_n=a_{n-1}-A_{n-1}$$ starting with $a(1)=3$, $A(1)=1$. This is because any of $a_{n-1}- A_{n-1}$ words with $n-1$ letters which do not end in A can be followed by A, B or C, while the $A_{n-1}$ words ...

2

This is a permutation with forbidden positions. Your specific problem corresponds to the board below, where $X$ in square $(i,j)$ denotes that element $i$ is not allowed to go to position $j$. XXOOO XXOOO OOXXO OOXXO OOOOX Let $r_i$ denote the number of ways to place $i$ rooks on the $X$ squares, such that none attack each other. $r_1=9$, because there ...

2

You’re talking about the number of partitions of a positive integer $n$. This MathWorld link may also be helpful. There are recurrences, but they’re not particularly nice.

2

Well, compute a few terms: $$a_0 = a_0.$$ $$a_1 = 2 a_0 + 3.$$ $$a_2 = 4 a_0 + 3 \times 2 + 3^2.$$ $$a_3 = 8 a_0 + 3 \times 4 + 3^2 \times 2 + 3^3.$$ So, a reasonable guess is: $$a_n = 2^n a_0 + \sum_{i=1}^n 3^i 2^{n-i} = 2^n a_0 + 2^n \sum_{i=1}^n (3/2)^i.$$ You should be able to prove this by induction.

2

Hint: Note that $\begin{pmatrix}2 & 1\\ 0 & 2 \end{pmatrix}=\begin{pmatrix}2 & 0\\ 0 & 2 \end{pmatrix}+\begin{pmatrix}0 & 1\\ 0 & 0 \end{pmatrix}$ and $\begin{pmatrix}2 & 0\\ 0 & 2 \end{pmatrix}\begin{pmatrix}0 & 1\\ 0 & 0\end{pmatrix}=\begin{pmatrix}0 & 1\\ 0 & 0\end{pmatrix}\begin{pmatrix}2 & 0\\ 0 & ... 2 Let the top right coordinate of the board be$(1,1)$and the bottom left coordinate be$(n,n)$. Let$k$pawns be placed (notice that$k \leq n$) and let their coordinates be$(x_i, y_i)$for$1\leq i \leq k$. Your condition says that if$i\neq j$, then either$x_i < x_j$and$y_i < y_j$or$x_i > x_j$and$y_i > y_j$. So, suppose that we have ... 2 Consider instead the sequence$(2+\sqrt{3})^n$with the same restrictions. Note that since $$(2-\sqrt{3})^n=2^n-\binom{n}{1}2^{n-1}\sqrt{3}+\cdots +(-1)^k\binom{n}{k}2^{n-k}\sqrt{3}^k+\cdots$$ The negated terms are exactly those in the form$m\sqrt{3}$for some integer$m. But as $$(2+\sqrt{3})^n=2^n+\binom{n}{1}2^{n-1}\sqrt{3}+\cdots ... 2 If a=1, then f_n=f_0+nb, otherwise since f_n=af_{n-1}+b we can subtract \frac{b}{1-a} from both sides to get$$ f_n-\frac{b}{1-a}=a\left(f_{n-1}-\frac{b}{1-a}\right) $$therefore,$$ \begin{align} f_n &=\frac{b}{1-a}+a^n\left(f_0-\frac{b}{1-a}\right)\\ &=a^nf_0+b\frac{1-a^n}{1-a} \end{align} $$1 In fact, your approach is false. Your characteristic polynomial would work for the recurrence relation f_{n+1}=af_n+bf_{n-1}, but not for your case. You need to have a homogeneous relation for working with that polynomial, which you don't. Therefore, you need first to do a couple modifocations. You can write$$ f_{n+2} - f_{n+1 }=a(f_{n+1} - f_{n}),$$... 1 Without extra rolls, the probability of getting m of any given result out of n rolls is given by the Binomial distribution (http://en.wikipedia.org/wiki/Binomial_distribution): in this case, it is \binom{n}{m}p^m(1-p)^{n-m}, where p=\frac{1}{6} is the probability of rolling a particular number on the die. Now suppose you begin with n rolls, and ... 1 You may be interested to know that there are exact solutions to your three problems. We will do problem one and provide references for the other two. Suppose we have T(0) and for n\ge 1 we have the recurrence$$T(n) = 6 T(\lfloor n/2 \rfloor) + 2^{3\lfloor \log_2 n \rfloor}.$$We can unroll this recurrence to obtain the exact result that$$T(n) = ... 1 For your second problem, lets solve the recurrence $$T(n) = 8 T(\lfloor n/2 \rfloor) + \frac{n^3}{(1+\lfloor\log_2 n\rfloor)^4}$$ whereT(0) = 0.$Let $$n = \sum_{k=0}^{\lfloor\log_2 n\rfloor} d_k 2^k$$ be the binary representation of$n.$Unrolling the recursion we find the exact formula $$T(n) = \sum_{j=0}^{\lfloor\log_2 n\rfloor} ... 1 For problem three, lets solve the recurrence$$T(n) = 9 T(\lfloor n/3\rfloor) + n \times (1+\lfloor\log_3 n\rfloor)^3$$where we set T(0)=0. Let the base three representation of n be$$n = \sum_{k=0}^{\lfloor\log_3 n\rfloor} d_k 3^k.$$Then we get the exact formula$$T(n) = \sum_{j=0}^{\lfloor\log_3 n\rfloor} 9^j \times (1+\lfloor\log_3 n\rfloor- j)^3 ... 1 Using this on$\displaystyle a_{n+3}-2a_{n+2}-2a_{n+1}+a_n=0$we have$\displaystyle a_n=A(-1)^n+B\left(\frac{3+\sqrt5}2\right)^n+C\left(\frac{3-\sqrt5}2\right)^n\ \ \ \ (1)$where$A,B,C$are arbitrary constants Now using Binet's formula, the$n$th Fibonacci term$\displaystyle F_n=\frac{a^n-b^n}{a-b}$where$a,b$are the roots of$t^2-t-1=0$... 1 Making a small table of values gives the game away: $$\begin{array}{c|rr} j\backslash k&0&1&2&3&4&5&6&7\\ \hline 0&1&1&1&1&1&1&1&1\\ 1&0&-1&-2&-3&-4&-5&-6&-7\\ 2&0&0&1&3&6&10&15&21\\ ... 1 As usual, this only defines T on the powers of 2 hence consider t_k=2^kT(2^k), then t_k=4t_{k-1}^2 for every k\geqslant1. Iterating, one gets$$ t_k=4\cdot4^2\cdots4^{2^{k-1}}\cdot (t_0)^{2^k}, $$that is$$ T(2^k)=2^{-k}4^{2^k-1}T(1)^{2^k}. $$If one wants to extend this to every n (which is not a consequence of the hypothesis), probably the ... 1 Another way: rewrite the equation as a_{k+1}-a_{k}=\Delta a_{k+1}$$ \Bigg\{ \begin{array}{lr} a_{k}=3 a_{k-1} +2\\ a_{k+1}=3 a_k+2 \end{array} $$Subtract the first equation from the second to get$$ \Delta a_{k+1}=3 \Delta a_{k}=\ldots 3^n \Delta a_1 $$Now sum both sides over k to get$$ a_{k}=3^k-1$\$

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