Right now I'm working on a computer algorithm that manipulates a binary tree data structure. Within this tree, there are many "gaps"; i.e., nodes that don't produce children nodes, thus resulting in gaps that become increasingly large as the tree grows.
That being said, when attempting to account for these gaps, I describe a cross section of the tree as a collection of sequences of nodes that either do or don't exist, and represent the length of each sequence as a power of $2$. When doing so, I stumbled upon something that I found to be interesting..
Let $a, b$ and $c \in \mathbb{Z}^+$. For a given value of $c$, does there exist an $a$ and $b$ s.t. $c^{a} + c^{b} = a^{c} + b^{c}$ when $a \ne b$?
Can someone please show this to be true/not true? And if this is true for some values of $a, b,$ and $c$, is it possible to generalize this behavior?
Or, if this has already been studied, can someone please provide a link to relevant literature? Thanks in advance.
The only triples of positive integers $(a, b, c)$ for which $a \neq b$ and $c^a + c^b = a^c + b^c$, up to interchange of $a$ and $b$, are $(1, 3, 2)$, $(2, 4, 2)$, and $(2, 4, 4)$. Allowing $a = b$ adds the the solutions $(4, 4, 2)$ and $(2, 2, 4)$ as well as the trivial solutions $a = b = c$.
For $c$ fixed, $a^c + b^c$ grows polynomially in $a$ and $b$, whereas $c^a + c^b$ grows exponentially. So there should be few solutions except when $a$ is large compared to $c$ and $b$ is small, or vice versa. To eliminate these possibilities, we need three lemmas providing (rather loose) bounds on expressions of the form $c^a - a^c$.
Lemma 1: For $3 \leq k < n$, $$k^n - n^k > k^\theta$$ where $\theta = 1$ for $k = 3$ and $\theta = k$ for $k \geq 4$.
Proof: Rearrange to $(k^{n-\theta} - 1) k^\theta > n^k$, take logarithms to get $\ln (k^{n-\theta} - 1) + \theta \ln k > k \ln n$, and further rearrange to $$\ln (k^{n-\theta} - 1) + (\theta - k) \ln k > k \ln \frac{n}{k}.$$
The LHS is $\ln (k^{n-k} - k^{\theta-k})$, and the RHS is less than $n-k$ (because $\ln x \leq x-1$ with equality only for $x=1$), so it sufficies to prove $$\ln (k^{n-k} - k^{\theta-k}) > n-k$$ or, taking exponentials and rearranging, $$e^{n-k} ((k/e)^{n-k} - 1) > k^{\theta - k}.$$ Since $k \geq 3 > e$, both terms on the LHS are positive and increasing with $n$, so it suffices to prove the case where $n = k+1$, i.e., $k - e > k^{\theta - k}$. If $k \geq 4$, taking $\theta = k$ gives $k - e > 1$; if $k = 3$, taking $\theta = 1$ gives $3 - e > 1/9$, both manifestly true. QED
Lemma 2: For $n \geq 5$, we have $2^n - n^2 \geq 9$.
Proof: The bound holds for $n = 5$, and the difference $2^{n+1} - 2^n = 2^n$ between consecutive powers of 2 is greater than the difference $(n+1)^2 - n^2 = 2n+1$ between consecutive squares (and thus $2^n - n^2$ is strictly increasing) for $n \geq 5$. QED
Corollary: The only pairs of integers $(k, n)$ for which $k^n \leq n^k$ and $2 \leq k < n$ are $(2, 3)$ and $(2, 4)$.
Lemma 3: Again with $3 \leq k < n$, we have $k^n - n^k > n$.
Proof: We'll prove that we can pick some constant $c > 1 + n^{1-k}$ to get an inequality of the form $k^n > c n^k$. Since $1 + n^{1-k}$ decreases with increasing $n$, it suffices to show that there's some possible $c > 1 + (1+k)^{1-k}$.
Take logarithms of $k^n > c n^k$ to get $n \ln k > \ln c + k \ln n$ and rearrange to $$(n-k) \ln k > \ln c + k \ln \frac{n}{k}.$$ As $\ln x \leq x-1$, it suffices to prove $$(n-k) \ln k > \ln c + (n-k)$$ or, rearranging, $$(n-k) (\ln k - 1) > \ln c.$$ The LHS of this inequality increases with $n$, so it suffices to prove the case $n = k + 1$, which holds as long as $c < k/e$.
Now we need to find some $c$ to satisfy $1 + (1+k)^{1-k} < c < k/e$; that is, we need to show that $1 + (1+k)^{1-k} < k/e$. For $k = 3$, this inequality becomes $17/16 < 3/e$, which is true. As the LHS $1 + (1+k)^{1-k}$ decreases for increasing $k$ (as the base $1+k$ increases and the negative exponent $1-k$ decreases) and the RHS $k/e$ increases, the inequality also holds for all greater $k$. QED
Now we return to the main question. Consider five cases, depending on the value of $c$.
Case 1 ($c = 1$): $c^a + c^b = a^c + b^c$ becomes $a + b = 2$, which has no solutions in distinct positive integers.
Case 2 ($c = 2$): The equation is $2^a + 2^b = a^2 + b^2$. At least one of $a$ or $b$ has to be in $\{2, 3, 4\}$, as otherwise each term on the LHS exceeds the corresponding term on the RHS. Suppose without loss of generality that $a \in \{2, 3, 4\}$. If $a = 2$ then $b = 4$ and vice versa, as $2^n = n^2$ is solved only for $2$ and $4$. If $a = 3$, then we have $2^b - b^2 = 1$, which is solved only for $b = 1$ (by Lemma 2).
Case 3 ($c = 3$): The equation is $3^a + 3^b = a^3 + b^3$. But $3^n \geq n^3$ for every integer $n$, with equality only if $n = 3$ (by testing $n = 1, 2, 3$ and then using Lemma 1 for $n \geq 4$), so this case is impossible.
Case 4 ($c = 4$): The equation is $4^a + 4^b = a^4 + b^4$. $4^n = n^4$ only for $n = 2, 4$ (giving $(a, b) = (2, 4)$ as a solution), and $4^n < n^4$ only for $n = 3$, so there are no solutions with $a$ and $b$ both than $4$. A solution with $a = 3$ must have $b$ such that $4^b - b^4 = 3^4 - 4^3 = 17$. But $b = 1, 2, 3, 4$ can be eliminated individually, and for $b > 4$ we have $4^b - b^4 > 4^4 = 64$ by Lemma 1, so this is impossible.
Case 5 ($c \geq 5$): Assume without loss of generality that $a < b$. For any positive $n$, $c^n > n^c$ if and only if $n > c$ or $n = 1$, and $c^n = n^c$ only if $n = c$, so either $a=1$ or $a < c < b$.
Sub-case a ($a = 1$). We must have $b$ (necessarily less than $c$) such that $b^c - c^b = c - 1$. This is impossible if $b \geq 3$ by Lemma 3, which holds that $b^c - c^b \geq c$, and $b = 2$ can be eliminated by parity: $2^c - c^2$ is even if and only if $c$ is even, but $c - 1$ is even if and only if $c$ is odd.
Sub-case b ($2 \leq a < c < b$). Rearrange $a^c + b^c = c^a + c^b$ as $a^c - c^a = c^b - b^c$. The LHS is less than $a^c < c^c$, but by Lemma 1, the RHS is strictly greater than $c^c$. QED