We have initial conditions: $n_1=2, v_1=1.$
And given recurrence relations:
$v_i=(2^{i+1}+1) v_{i-1}$
$n_i\leq 2^i n_{i-1}+2v_{i-1}$
I need to prove the below lower bound:
$$v_i≥n_i.e^{\Omega(\sqrt{\log n_i})}.$$
Is there any easy way to solve it? I have no clue to solve.
This recurrence looks fairly random, so let's try tackling it in parts. First, we will show that $\log v_k$ and $\log n_k$ grow like $k^2$. Indeed, it can not grow slower since even if we leave the first terms we will get that $n_k, v_k \ge 2^{k(k-1)/2}$. For the estimate from the other side say consider $m_k = n_k + v_k$ and we have crudely (by adding our recurrence relations basically and using monotonicity of $n_k, v_k$) $m_k \le (2^{k+1} + 10)m_{k-1}$ which will give us a similar upper bound. So, we just have to show that $v_k \ge \gamma^k n_k$ for big enough $k$ and some $\gamma > 1$.
Assume that we showed it for say $\gamma = 1.1$ and $k \ge 3$. Let us show that it is true for $k+1$: for $v_k$ we simply have $v_{k+1} \ge 2^{k+2}v_k$. For $n_k$ we have $n_{k+1} \le 2^{k+1}\gamma^{-k}v_k + 2v_k$ (we again used an obvious fact that $v_k$ is increasing). So, to make the induction work we basically need $$2^{k+2} \ge \gamma^{k+1}(2^{k+1}\gamma^{-k} + 2) = \gamma2^{k+1} + 2\gamma^{k+1}.$$ This inequality is true for $\gamma < 2$ as long as $k$ is big enough, for $\gamma = 1.1$ it is true for $k \ge 3$ (after some algebra it transforms into $2 \ge \gamma + 2\left(\frac{\gamma}{2}\right)^{k+1}$, and the right hand side converges very fast to $\gamma$). It remains to check the base case of induction, and I simply computed $n_2, n_3, v_2, v_3$: $v_2 = 9, n_2 = 10$, $v_3 = 153, n_3 = 98$, so we have $v_3 \ge 1.1^3 n_3$ with a huge margin of error.
By throwing in a constant here and there I think it can be pushed to $v_k \ge \gamma^k n_k$ for any $\gamma < 2$ as long as $k\ge k(\gamma)$, but it clearly can not hold for any $\gamma > 2$ since $\frac{v_k}{n_k} \le 2^{k+1}+1$.
From the definition $$v_{k-1}=\frac1{15}\prod_{j=1}^k(2^j+1)=$$$$= \frac1 {15}{2^{ {\frac12k(k+1)}}}\prod_{j=1}^k(1+2^{-j}),$$ and from the bound of the infinite product $$\frac1 {15}\prod_{j=1}^\infty(1+2^{-j})\le \frac4{25}$$ we have $$\frac1{10} {2^{ {\frac12k(k+1)}}}\le v_{k-1}\le\frac4{25} {2^{ {\frac12k(k+1)}}}.$$ Keeping in mind the bound we are aiming to, we first note that for all $k\ge1$ $$n_k\le2kv_{k-1}+\frac45 {2^{ {\frac12k(k+1)}}},$$ that follows plainly by induction. Combining the last two inequalities we get $$n_k\le\Big(\frac8{25}k+\frac45\Big) {2^{ {\frac12k(k+1)}}}$$ and $$n_k\le(2k+8)v_{k-1}=\frac{2k+8}{2^{k+1}+1}v_k.$$ The former of these implies, for large $k$ $$\sqrt{\log n_k}\le\log \frac{2^{k+1}+1}{2k+8} ,$$ and together with the latter this gives $$v_k\ge n_k\frac{2^{k+1}+1}{2k+8}\ge n_ke^{\sqrt{\log n_k}}$$ for large $k$ (or with some easily estimated factor in front of the square root, if one wants an inequality for all $k$).
