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.