# 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]

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?

• The sequence $u_i:={v_i\over n_i}$ satisfies $u_{i+1}=u_i+{1\over 4}.$ Commented Aug 14 at 1:45
• @RyszardSzwarc would you elaborate more, how to proceed from here? Commented Aug 14 at 2:00
• From your progress, assume that $\frac14 2^i i \le v_i \le 2^ii$, then prove that $\frac14 2^{i+1}(i+1) \le v_{i+1} \le 2^{i+1}(i+1)$. Commented Aug 14 at 3:02

## 3 Answers

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$$

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*}

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.$$