# Tag Info

## Hot answers tagged recurrence-relations

3

Consider a representation with even number of zeros at step $n-1$. At the next step $n$, you can construct $3$ even number of zeros by following it with $1,2,3$. Similarly if you have a representation with odd number of zeros, you have to follow it with $0$ to keep it still even $0$s. So at $i$th step let $n_{odd,i}$ be the number of odds and $n_{even,i}$ ...

3

Given a string of length $n-1$, you can add any of $0$, $1$, or $2$ to the end of it to get a string of length $n$, so you get $3 a(n-1)$ strings. However, if the last two elements of the original string were $01$, then adding $2$ is not allowed. How many such strings are there? Well, they are found by noting that after removing the $01$ you have an ...

2

This equation is neither homogeneous nor linear. Hint This particular recurrence relation is a reasonably well-known example of a periodic recurrence, that is, for some $p > 0$, we have $$a_{n + p} = a_n$$ for all $n$. With this is mind, compute $a_1, a_2, a_3, \ldots$; eventually one will find terms $a_{1 + p} = x, a_{2 + p} = y$. (Often one sees this ...

2

I am learning this right now... I find it helpful to think of it this way: building from the end of the string, ___1 = g(n-1) combinations; splits into: ___11 = g(n-2) ___01 = g(n-2) ___21 = g(n-2) since they are all legal strings, we keep all of them, so you add g(n-1) to your recursion. ___0 = g(n-1) combinations; splits into: ___00 = ...

2

Here is a different approach: Let $0$ have weight $x$, and let $1$,$2$, $3$ have weight $1$ each. The weight of a word over $\{0,1,2,3\}$ is the product of the weights of its letters. The total weight of all one-letter words is then $x+1+1+1=3+x$, and the total weight of all $n$-letter words is $(3+x)^n$. It follows that the total weight of all $n$-letter ...

1

Use the substitution $n = 2^k$, $t(k) = T(2^k)$: \begin{align} t(k) = t(k - 1) + 2^{2 k} \end{align} This linear recurrence is easy to solve (or just write it as $t(k) - t(k - 1) = 2^{2 k}$ and sum over $k$).

1

Let n=$2^k$ for some k. Then we have $$T(2^k)=T(2^{k-1})+2^{2k}$$ $$\Rightarrow T(2^k)=T(2^{k-2})+2^{2(k-1)}+2^{2k}$$ $$\Rightarrow T(2^k)=T(2^{k-3})+2^{2(k-2)}+2^{2(k-1)}+2^{2k}$$ and so on till we get $$T(2^k)=T(2^0)+2^{2(k-(k-1))}+...+2^{2(k-2)}+2^{2(k-1)}+2^{2k}$$ $$\Rightarrow T(2^k)=\sum_{i=0}^{k-1} 2^{2(k-i)}$$ \Rightarrow ...

1

It is taking you to the first case of the Master Theorem, since $f(n)\in O(n^{c})$ for, e.g., $c=1.1 < \log_b a = \log_4 5 \simeq 1.16$. So $T(n) \in\Theta(n^{\log_4 5})$.

1

Let $G(1)=6, G(n)=6^{G(n-1)}$ and $F(1)=6, F(n)=(F(n-1))!$. You want to compare $G(720)$ with $F(46656)$. We have $\log G(n)=G(n-1) \log (6)$, so $720$ applications of $\log$ makes it small. $\log F(n)\approx F(n-1)( \log F(n-1)-1)$, so it takes about $46656$ applications of $\log$ to make it small. $F(46656) \gg G(720)$ so much that dividing ...

1

Here is a way to get started: Let $e_n$ be the number of words which start with a, let $b_n$ be the number of words which start with b, and let $c_n$ be the number of words which start with c. Then $a_n=e_n+b_n+c_n$ and $e_n=a_{n-1},\;\;$ $b_n=e_{n-1}+b_{n-1},\;\;$ and $c_n=e_{n-1}+c_{n-1}$.

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