7
$\begingroup$

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?

2 Answers 2

8

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
9

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.