Skip to main content
2 of 3
deleted 2 characters in body
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