Skip to main content
1 of 3
Xd00fg
  • 214
  • 10

Lower bound in recurrence relation

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=2^i n_{i-1}+v_{i-2}+v_{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.

Xd00fg
  • 214
  • 10