Sorry if the terms I'm going to use is not professional enough:) This is about the complexity analysis of an algorithm.

Let $\alpha$ be the greatest real root of the polynomial $f(x)=x^n-2x^{n-1}-x^{n-k}-2^k$, in which $k$ is a parameter.

The question is how to choose $k$, $(k=\beta n, 0<\beta<1)$ in order to minimize $\alpha$?

We believe that $g$ exists because to minimize $\alpha$, the term $2^k$ requires a small $k$ while the rest needs a big $k$.

Thank you in advance for any idea.

UPDATE:

We've just updated the recurrence relation, the idea is still the same. $k$ is still a relative value to $n$. Let $k=\beta n$. Then the new recurrence is

$f(x)=x^n-3x^{n-1}+x^{n-2}-x^{n-\beta n}-3^{\beta n}+3^{\beta (n-1)}$ Perhaps we can get more information from this one?