# Tag Info

7

Try exponential generating functions (and another link here). For example, let's look at the first recurrence $$f(x)=\sum\limits_{n=0}\color{red}{a_n}\frac{x^n}{n!}= 1+\sum\limits_{n=1}a_n\frac{x^n}{n!}=\\ 1+\sum\limits_{n=1}(n\cdot a_{n-1} + 1)\frac{x^n}{n!}= 1+\sum\limits_{n=1}a_{n-1} \frac{x^n}{(n-1)!} + \sum\limits_{n=1}\frac{x^n}{n!}=\\ x\left(\sum\... 3 Hint: let g(n) = \sum_{k=1}^n f(k). Then we have f(2011) = g(2011) - g(2010) and$$g(n) = g(n-1) + f(n)g(n) = g(n-1) + \frac{1}{n^2 - 1}g(n-1)g(n) = \frac{n^2}{n^2 - 1}g(n-1)$$Can you take it from here? 3 The Master Theorem fits the recurrence into$$T(n) = aT(n/b) + f(n)$$and so here a=4, b=2, \log_b(a) = \log_2(4) = 2 = c, with f(n) = \Theta(n^2) = \Theta(n^c), which fits the second case of the theorem for k=0. Therefore, by the Master Theorem,$$T(n) = \Theta \left(n^2 \ln n\right).$$2 You start from$$f(2n)=3f(n)+4$$To remove the constant, notice that a constant solution would verify a=3a+4\iff a=-2. So we will set f(n)=g(n)-2 to reduce the equation to$$g(2n)=3g(n)$$Now take n=2^k then g(2^k)=3g(2^{k-1})=3^2g(2^{k-2})=\cdots=3^kg(2^0)=3^kg(1) Since we have g(1)=f(1)+2=3 then g(2^k)=3^{k+1}. Finally substituting k=\... 2 For any \epsilon > 0, \log(n) = o(n^\epsilon). (The base of \log doesn't matter, because logarithms with different bases are scalar multiples of each other.) The proof is by L'Hôpital:$$\lim_{n \to \infty} \frac{\log n}{n^{\epsilon}} = \lim_{n \to \infty} \frac{\frac{d}{dn} \log n}{\frac{d}{dn} n^\epsilon} = \lim_{n \to \infty} \frac{n^{-1}}{\...

2

Hint: $$a_n=na_{n-1}+1$$ $$\Rightarrow a_n=n(n-1)a_{n-2}+1+n$$ $$\Rightarrow a_n=n(n-1)(n-2)a_{n-3}+1+n+n(n-2)$$ Continuing so on we get, $$a_n=a_0n!+\sum_{k=1}^n \frac {n!}{k!}=n!\left(1+\sum_{k=1}^n \frac {1}{k!}\right)=n!\sum_{k=0}^n\frac{1}{k!}$$ Similarly you can solve for the second case to get, $$a_n=n!\left(1+\sum_{k=0}^{n-1} \frac{1}{k!}\right)$$

1

Your equations just say that $$c(n_1,n_2)$$ takes free values in the square $[0,N-1]\times[0,N-1]$, and you can obtain them elsewhere by the formulas $$c(n_1-N,n_2)=c(n_1,n_2),$$ and by induction $$c(n_1-kN,n_2)=c(n_1,n_2),$$ and $$c(n_1,n_2-N)=c(n_1,n_2)e^{an_1+b}$$ and by induction $$c(n_1,n_2-k'N)=c(n_1,n_2)e^{k'(an_1+b)}.$$ Of course, c(n_1-...

1

Given is the following recursive sequence: $f(1)=1, \ f(n)=3f\left(\frac{n}{2}\right)+4, \ n = 2^k , \ k \geq 1$ Calculating the first elements $7$ elements of this sequence: $f(2^0)=f(1)=1$ $f(2^1)=3f(2^0)+4=3f(1)+4=7$ $f(2^2)=3f(2^1)+4=3 \cdot 7+4=25 = 7 + 2\cdot 3^2$ $f(2^3)=3f(2^2)+4=3 \cdot 25+4=79 = 7 + 2\cdot(3^2 + 3^3)$ $f(2^4)=3f(2^3)+4=3 \... 1 For simplicity take n to be a power of 2, ie$n=2^k$, and we can also take log to be base 2. Then by iterating the same step:$T(n)=2T(\frac{n}{2})+n\log(n)=4T(\frac{n}{4})+n\log(\frac{n}{2})+n\log(n)=nT(1)+n\log(\frac{n}{2^{k-1}})+n\log(\frac{n}{2^{k-2}})+...+n\log(\frac{n}{2})+n\log(n)$Put$n=2^{k}$, to get$T(n)=2^{k}T(1)+2^{k}(1+2+...+k)=2^{k}T(1)+2^{...

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