I have an inequality of the form $a^k +b^k \leq c$ with $a,b,c,k \in\mathbb{Z^+}$. For known $a,b,c$ I want to find out the largest $k$ for which this inequality holds. I am able to write a program that does this for me, but cannot come up with any clever way to do it analytically. Is there a good way to do this?
Largest $k$ for which $a^k +b^k \leq c$
2 Answers
Suppose $1< b$ and that $a\leq b$. Then in all cases either we have $k=\lfloor\log_b c\rfloor$ or $k=\lfloor\log_b c\rfloor-1.$ Here is the justification: Certainly $\lfloor\log_b c\rfloor$ is an upper bound for $k$. Now, since $a^k+b^k\leq 2b^k\leq b^{k+1}$ for all positive $k$ we see that $\lfloor\log_b c\rfloor-1$ is a lower bound.
Notice that both cases are possible as well. Let $c=65$, and let $a=2$, $b=4$. Then $k=2=\lfloor\log_b c\rfloor-1$. Alternatively, let $b=4$, $a=2$ and $c=63$. Then the maximal $k$ is $k=2$ which is $\lfloor\log_b c\rfloor$.
Hope that helps,
-
1@t-laarhoven your answer is not redundant. Thanks and +1 , ofcourse. Thanks Eric. – 2011-08-25
Without loss of generality, let $b > a$. Notice that
$b^k \leq a^k + b^k \leq 2 b^k$
So if you want that $a^k + b^k \leq c < a^{k+1} + b^{k+1}$, then it follows that
$b^k \leq c < 2 b^{k+1}$
Or, equivalently,
$k \leq \log_b(c) < k + 1 + \log_b(2)$
Finding the right value of $k$ should be easy now. If $a = b = 1$ the problem is trivial, while for $b \geq 2$ you have $\log_b(2) \leq 1$ such that
$k \leq \log_b(c) < k + 2$
As the only integral values of $k$ satisfying this relation are $k = \lfloor \log_b(c) \rfloor$ and $k = \lfloor \log_b(c) \rfloor - 1$, you only need to check these two values as possible solutions.