As part of an undergraduate project I am attempting to find a solution to this set of recursive inequalities:

$$g(n,l,k) \leq g\left(\frac{n-1}{2},l,k-1\right)$$

$$k \cdot g(n,k,l)+\log_2 (n-2^l +1) \leq l+(k-1)\cdot g\left(\frac{n-1}{2},k-1,l\right)+\log_2(n)$$

for $n \geq 2^{k+l}$. This popped up when solving another system of recursive inequalities. I'm not expecting an exact solution, instead I'm aiming for a simple approximate function that satisfies the inequalities. The small bag of tricks I would use for more simple recursive relations I had to work with was finding a rough solution to one of the inequalities while consider only one, maybe two, variables at a time, and afterwards plugging the solution into the second inequality to see what needs to be added to make that one work. Then I just guess small changes and tweaks and see if they still hold until I'm satisfied. It's really just trial and error at this point.

This particular system is more complicated, and my techniques aren't much help now. How should I approach something like this? What actual methods are there for this kind of problem?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.