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