Find the rate of a sequence solving a polynomial inequality

Question

Let $x\geq1$ be an integer and suppose that $n\to \infty$. Show that $x=O(n^c)$ if $$x^{1+a} \leq n + x^an^{-b}$$ for some $a>0$ and $b\geq1$.

It looks to me that $x=O(n^{1/(1+a)})$, but I need to find a formal argument.

Update: what about the following argument. If $n\lesssim x^an^{-b}$, then $x\lesssim n^{-b}$ which contradicts to $x\geq 1$. If $x^an^{-b}\lesssim n$, then $x\lesssim n^{1/(1+a)}$.

Answer 1

Assume $x=O(f(n))$ then

$$ f(n)^{1+a} \lesssim n+ f(n)^a n^{-b} $$ Assume that $f$ growth faster than any polynomial (i.e. $\frac{f(n)}{n^c} \to \infty$ for any $c>0$ ) then $$ f(n)^{} \lesssim \frac{n}{f(n)^{a}} + n^{-b} \lesssim n^{-b} $$ That is absurd

Assume $f$ growth slower than any power of $n$ (i.e. $\frac{f(n)}{n^c} \to 0$ for any $c>0$) then $$ f(n) \gtrsim n^{\frac{b+1}{a}} + n^{\frac{b}{a}} f(n)^{\frac{1+a}{a}} \gtrsim n^{\frac{b}{a}} $$ that is absurd, So $x=O(n^c)$

To find a upper bound for $c$ : We have

$$n^{(c(1+a))} \lesssim n + n^{ac-b}$$

Assume $ac-b \ge 1 \rightarrow c\ge \frac{b}{a}>0$ than

$$ c(1+a) \le ac-b \rightarrow c \le -b<0 $$ So $ac-b<1$ that means $$ c \le \frac{1}{1-a} $$

Answer 2

We claim that $x \le O((n+1)^{1/(1+a)})$.

Proof.

It suffices to prove that $x \le (n +1 )^{1/(1+a)}$ for all $n > 2 + a$.

First, we claim that $x^a n^{-b} \le 1$. Indeed, if $x^a n^{-b} > 1$, we have $x > n^{b/a}$ and thus $$x^{1+a} - x^a n^{-b} = x^a (x - n^{-b}) > n^b( n^{b/a} - n^{-b}) = n^{b + b/a} - 1 > n$$ which contradicts $x^{1 + a} \le n + x^a n^{-b}$. Here we use the Bernoulli inequality to obtain $n^{b + b/a} \ge 1 + (n - 1)(b + b/a) \ge 1 + (n-1)(1 + 1/a) > 1 + n $.

Second, using $x^a n^{-b} \le 1$, we have $$x^{1 + a} \le n + 1$$ which results in $x \le (n + 1)^{1/(1 + a)}$.

We are done.