Showing $v_i=\Theta(n_i\log⁡ n_i)$ for the recurrence $n_{i+1}=2n_i$, $v_{i+1}=2v_i+\frac{1}{2}n_i$ with initial condition $n_1=2$, $v_1=1$ [closed]

Question

I have initial condition $n_1=2, v_1=1$, and the given recurrence relations: $n_{i+1}=2n_i, \quad v_{i+1}=2v_i+\frac{1}{2}n_i$.

I need to show that that, $v_i=\Theta(n_i\log⁡ n_i)$.
I observe that $n_i=2^i$. How to proceed from here?

Answer 1

Let $u_i=n_i^{-1}v_i.$ Then $u_1= 2^{-1}$ and $$ u_{i+1}=n_{i+1}^{-1}v_{i+1}= (2n_i)^{-1}[2v_i+2^{-1}n_i]\\ =n_i^{-1}v_i+2^{-2}=u_i+2^{-2}$$ Thus $u_i=2^{-2}(i+1).$ We obtain $$v_i=u_in_i=2^{-2}(i+1)n_i=2^{-2}(i+1)2^{i}\sim n_i\log n_i$$

Answer 2

From your progress, $n_i = 2^i$. Then $n_i\log n_i = 2^i i \log 2$.

To prove by induction, let proposition $P(i)$ be

$$k_1 2^i i \le v_i \le k_2 2^i i$$

where $k_1, k_2 > 0$ and are to be determined.

From $P(1)$, determine bounds for $k_1, k_2$:

$$\begin{align*} k_1\cdot 2^1 \cdot 1 \le 1 &\le k_2 \cdot 2^1 \cdot 1\\ k_1 \le \frac12 &\le k_2 \end{align*}$$

Assume $P(m)$ is true for some $m\in \mathbb N$:

$$k_1 2^m m \le v_m \le k_2 2^m m$$

For $P(m+1)$, determine bounds for $k_1, k_2$ that will satisfy the induction step:

$$\begin{align*} v_{m+1} &= 2v_m + \frac12 2^m\\ 2k_1 2^m m +\frac12 2^m \le v_{m+1} &\le 2k_22^m m + \frac12 2^m\\ k_1 2^{m+1} m + \frac14 2^{m+1} \le v_{m+1} &\le k_2 2^{m+1} m + \frac14 2^{m+1}\\ k_1 2^{m+1} m + k_1 2^{m+1} \overset{(*)}\le v_{m+1} &\overset{(*)}\le k_2 2^{m+1} m + k_2 2^{m+1}\\ k_1 2^{m+1} (m+1) \le v_{m+1} &\le k_2 2^{m+1} (m+1) \end{align*}$$

For any $k_1 \le \frac14 \le k_2$, inequalities $(*)$ and hence $P(m+1)$ both hold.

Choose $k_1 = \frac14$, $k_2 = 1$. By induction, for all $i\in\mathbb N$,

$$\begin{align*} \frac14 2^i i \le v_i &\le 2^i i\\ \frac1{4\log 2} 2^i \log \left(2^i\right) \le v_i &\le \frac1{\log2} 2^i \log \left(2^i\right)\\ v_i &= \Theta\left(2^i \log \left(2^i\right)\right) \end{align*}$$

Answer 3

Though this is not the simplest way, you can proceed by eliminating $n_i$. For this, write

$$n_i=2v_{i+1}-4v_i$$ and $n_{n+1}=2n_i$ turns to

$$2v_{i+2}-4v_{i+1}=4v_{i+1}-8v_i$$ or $$v_{i+2}-4v_{i+1}+4v_i=0.$$

The characteristic polynomial has the double root $2$, so the general solution is $$v_i=(ai+b)2^i,$$ and the initial conditions are $v_1=1,v_2=3$.

Knowing the expression of $n_i$, this is also

$$v_i=(a\lg(n_i)+b)n_i.$$