Is it true that for integer $k$ if $2^{p_k} - 3^k = 3^{k-1} + \sum\limits_{s=1}^{k-1} 3^{k-1-s}2^{p_s}$, then $p_k=2k$ and each $p_s=2s$

Question

Let:

• $k > 1$ be an integer

• $p_1, p_2, p_3, \dots, p_k$ be integers where:

  • $p_k > p_{k-1} > \dots > p_3 > p_2 > p_1 > 0$
  • $2^{p_k} > 3^k$

• $2^{p_k} - 3^k = 3^{k-1} + \sum\limits_{s=1}^{k-1} 3^{k-1-s}2^{p_s}$

Does it follow that the only possible solution is $p_k = 2k$ with each $p_s = 2s$ Is there a more standard way to make the same argument?

Here's the argument:

(1) Base case: $s=1$

• Case 1: $p_1 > 2$

This is impossible since $(-3)\times3^{k-1} \not\equiv 3^{k-1} \pmod 8$

• Case 2: $p_1 = 1$

This is impossible since $(-3)\times3^{k-1} \not\equiv 3^{k-1} + 2 \pmod 8$. If $k$ is even, then $(-3)(3^{k-1}) \equiv 7 \pmod 8$ while $(3^{k-1}+2) \equiv 5 \pmod 8$. If $k$ is odd, then $(-3)(3^{k-1}) \equiv 5 \pmod 8$ while $(3^{k-1}+2) \equiv 3 \pmod 8$

(2) Assume for all $i \le s$, it follows that $p_i = 2i$

(3) Inductive Case:

• Case: $p_{s+1} > 2s+2$

  • $2^{2s+2} - 3^{s+1} = 3^s + \sum\limits_{t=1}^s 3^{s-t}2^{2t}$
  • $3^{k-1} + \sum\limits_{s=1}^{k-1}3^{k-1-s}2^{p_s} \equiv 3^{k-1-s}\left(2^{2s+2} - 3^{s+1}\right) \equiv 2^{2s+2} - 3^k\pmod {2^{2s+3}}$
  • But $2^{p_k} -3^{k} \equiv -3^{k} \not\equiv 2^{2s+2} - 3^k \pmod {2^{2s+3}}$

• Case: $p_{s+1} < 2s+2$ and $s+1 < k$

  • $3^{k-1} + \sum\limits_{s=1}^{k-1}3^{k-1-s}2^{p_s} \equiv 3^{k-1-s}\left(2^{2s+2} - 3^{s+1}\right)+ 3^{k-2-s}2^{2s+1} \equiv 2^{2s+1} - 3^k \pmod {2^{2s+2}}$

  • But $2^{p_k} - 3^{k} \equiv -3^{k} \not\equiv 2^{2s+1}-3^k \pmod {2^{2s+2}}$

• Case: $p_{s+1} < 2s+2$ and $s+1 = k$ is impossible since

  • $2^{2s+1} - 3^k < 2^{2s+2} - 3^k = 3^{k-1} + \sum\limits_{t=1}^{k-1}3^{k-1-t}2^{2t}$

Answer 1

I believe what you're doing is basically correct, but I'm having trouble following parts of it to be sure of this. For example, I find your use of $s$ as both a summation index and also an index for the values of $p$ somewhat confusing, especially when you use it in the same expression, such as the second line of your first case of "(3) Inductive Case:", i.e.,

$3^{k-1} + \sum\limits_{s=1}^{k-1}3^{k-1-s}2^{p_s} \equiv 3^{k-1-s}\left(2^{2s+2} - 3^{s+1}\right) \equiv 2^{2s+2} - 3^k\pmod {2^{2s+3}}$

Also, there are a few inconsistencies and small mistakes with what you're doing. For example, in your base case of $s = 1$, with the case $p_1 = 1$, then it's possible that $p_2 = 2$, but you seem to be assuming $p_2 \ge 3$ since you are using modulo $8$, instead of modulo $4$, in your explanations.

Another example is with your first case of "(3) Inductive Case:", where you state:

Case: $p_{s+1} > 2s+2$

Your next line is

$2^{2s+2} - 3^{s+1} = 3^s + \sum_{t=1}^s 3^{s-t}2^{2t}$

where there is no more $k$, but it seems to be setting $k = s + 1$ in your definition expression. However, the first term would then be $2^{p_{s+1}}$, but it's shown as $2^{2s+2}$, which means $p_{s+1} = 2s + 2$, contradicting your case statement that $p_{s+1} \gt 2s + 2$. Also, your next line then uses $k$ again, with it not being clear how this corresponds to the line before it, as well as what $k$ is in relation to $s$ there.

---

Here is how I would prove your conjecture instead. Rearranging your expression by moving everything to the right, combining both of the $3$ to a power terms and separating the first summation term from the summation gives

$$\begin{equation}\begin{aligned} 0 & = 3^{k} + 3^{k-1} - 2^{p_k} + \sum_{s=2}^{k-1} 3^{k-1-s}2^{p_s} + 3^{k-2}2^{p_1} \\ & = 3(3^{k-1}) + 3^{k-1} + 3^{k-2}2^{p_1} - 2^{p_k} + \sum_{s=2}^{k-1} 3^{k-1-s}2^{p_s} \\ & = 4(3^{k-1}) + 3^{k-2}2^{p_1} - 2^{p_k} + \sum_{s=2}^{k-1} 3^{k-1-s}2^{p_s} \end{aligned}\end{equation}\tag{1}\label{eq1A}$$

Note the third term and each of the terms in the summation have more factors of $2$ than $p_1$. Thus, if $p_1 = 1$, dividing both sides by $2$ means all terms would be even except for the second, i.e., $3^{k-2}$, so the right side result would be odd, which means it can't be $0$. Instead, if $p_1 \gt 2$, then dividing by $4$ means all of the terms would be even except for the first, i.e., $3^{k-1}$, so once again this odd value is not $0$. Thus, this means $p_1 = 2 \implies 2^{p_1} = 4$.

If $k = 2$, then there are no summation terms, so \eqref{eq1A} then simplifies to

$$\begin{equation}\begin{aligned} 0 & = 4(3) + 2^{2} - 2^{p_k} \\ & = 16 - 2^{p_k} \end{aligned}\end{equation}\tag{2}\label{eq2A}$$

This gives that $p_k = p_2 = 4 = 2(2)$.

If $k \gt 2$ instead, then dividing both sides of \eqref{eq1A} by $4$, and separating the first term from the summation, gives

$$\begin{equation}\begin{aligned} 0 & = 3^{k-1} + 3^{k-2} - 2^{p_k - 2} + \sum_{s=2}^{k-1} 3^{k-1-s}2^{p_s - 2} \\ & = 3(3^{k-2}) + 3^{k-2} - 2^{p_k - 2} + \sum_{s=3}^{k-1} 3^{k-1-s}2^{p_s - 2} + 3^{k-3}s^{p_2 - 2} \\ & = 4(3^{k-2}) + 3^{k-3}2^{p_2 - 2} - 2^{p_k - 2} + \sum_{s=3}^{k-1} 3^{k-1-s}2^{p_s - 2} \end{aligned}\end{equation}\tag{3}\label{eq3A}$$

Note how the form of the last line above is basically the same as the last line of \eqref{eq1A}, but with several differences. One is the lowest summation term has been removed. Also, the smallest $p_i$ value, i.e., $p_1$, has also been removed, so there is now $1$ less of these $p_i$ values to deal with. In addition, all of the remaining $p_i$ values have effectively been reduced by $2$. Finally, the exponents of $3$ in the first $2$ terms have been reduced by $1$.

Next, note since $p_1 = 2$, the condition

$p_k \gt p_{k-1} \gt \dots \gt p_3 \gt p_2 \gt p_1 \gt 0$

now basically becomes

$p_k - 2 \gt p_{k-1} - 2 \gt \dots \gt p_3 - 2 \gt p_2 - 2 \gt 0$

Thus, the exponents of $2$ being used in \eqref{eq3A} follow the same requirement as that in \eqref{eq1A}. This confirms we have basically the same form of the equation again in terms of the $p_i$ values, except for having one less $p_i$ term, and all of the remaining $p_i$ values having effectively been reduced by $2$.

As such, we can keep repeating the steps above reducing the number of terms in the summation (note this can also be shown formally using induction), meanwhile also deducing that $p_i = p_{i-1} + 2 \implies p_i = 2i$ for each $2 \le i \le k - 1$. When all of the summation terms have been removed (after repeating the steps $k - 2$ times), leaving just the first $3$ terms, we basically get what is shown in \eqref{eq2A}, but with $p_k$ replaced with $p_k - 2(k-2)$. This then shows that $p_k - 2(k-2) = 4 \implies p_k = 2k$.

---

Update: The method above combines terms and removes $2$ factors of $2$ each time, thereby reducing the number of terms and the powers of $2$ during each iteration. It uses the fact the form of the equation and the conditions on it don't change to be able to keep repeating the steps. Here is a method involving the same concepts but which uses strong induction to show that $p_s = 2s$ for each $s$. The base case of $p_1$ is as I described earlier below \eqref{eq1A}.

Assume for some $1 \le m \le k - 1$ that the hypothesis (i.e., $p_s = 2s$) is true for all $1 \le s \le m$. Then \eqref{eq1A} becomes

$$\begin{equation}\begin{aligned} 0 & = 4(3^{k-1}) + 3^{k-2}2^{p_1} - 2^{p_k} + \sum_{s=2}^{k-1} 3^{k-1-s}2^{p_s} \\ & = 2^2(3^{k-1} + 3^{k-2}) - 2^{p_k} + \sum_{s=2}^{m} 3^{k-1-s}2^{2s} + \sum_{s=m+1}^{k-1} 3^{k-1-s}2^{p_s} \\ & = 2^2(3(3^{k-2}) + 3^{k-2}) - 2^{p_k} + \sum_{s=2}^{m} 3^{k-1-s}(2^2)^{s} + \sum_{s=m+1}^{k-1} 3^{k-1-s}2^{p_s} \\ & = 2^4(3^{k-2}) + \sum_{s=2}^{m} 3^{k-1-s}(2^2)^{s} - 2^{p_k} + \sum_{s=m+1}^{k-1} 3^{k-1-s}2^{p_s} \end{aligned}\end{equation}\tag{4}\label{eq4A}$$

The first summation above is that of a geometric series, with a first term $a = 2^4(3^{k-3})$, common ratio $r = \frac{2^2}{3}$, and $n = m - 1$ terms. This therefore gives

$$\begin{equation}\begin{aligned} \sum_{s=2}^{m} 3^{k-1-s}(2^2)^{s} & = 2^4(3^{k-3})\left(\frac{\left(\frac{2^2}{3}\right)^{m-1} - 1}{\frac{2^2}{3} - 1}\right) \\ & = 2^4(3^{k-3})\left(\frac{\frac{2^{2m-2} - 3^{m-1}}{3^{m-1}}}{\frac{1}{3}}\right) \\ & = 2^4(3^{k-3})\left(\frac{2^{2m-2} - 3^{m-1}}{3^{m-2}}\right) \\ & = 2^4(3^{k-m-1})(2^{2m-2} - 3^{m-1}) \end{aligned}\end{equation}\tag{5}\label{eq5A}$$

Substituting \eqref{eq5A} into \eqref{eq4A} gives

$$\begin{equation}\begin{aligned} 0 & = 2^4(3^{k-2}) + 2^4(3^{k-m-1})(2^{2m-2} - 3^{m-1}) - 2^{p_k} + \sum_{s=m+1}^{k-1} 3^{k-1-s}2^{p_s} \\ & = 2^4(3^{k-m-1})(3^{m-1} + 2^{2m-2} - 3^{m-1}) - 2^{p_k} + \sum_{s=m+1}^{k-1} 3^{k-1-s}2^{p_s} \\ & = 2^4(3^{k-m-1})(2^{2m-2}) - 2^{p_k} + \sum_{s=m+1}^{k-1} 3^{k-1-s}2^{p_s} \\ & = 2^{2m+2}(3^{k-m-1}) - 2^{p_k} + \sum_{s=m+1}^{k-1} 3^{k-1-s}2^{p_s} \end{aligned}\end{equation}\tag{6}\label{eq6A}$$

Now, there are $2$ sub-cases to consider. First, if $m \lt k - 1 \implies m \le k - 2$, then splitting the first term from the summation above gives

$$0 = 2^{2m+2}(3^{k-m-1}) - 2^{p_k} + 3^{k-m-2}2^{p_{m+1}} + \sum_{s=m+2}^{k-1} 3^{k-1-s}2^{p_s} \tag{7}\label{eq7A}$$

Since $p_m = 2m$, then $p_{k} \ge p_{m+2} \ge 2m + 2$. Thus, the first $2$ terms of \eqref{eq7A} and each term of the summation have at least $2m + 2$ factors of $2$. Thus, so must the third term, i.e., $3^{k-m-2}2^{p_{m+1}}$, (since, otherwise, dividing \eqref{eq7A} by $2^{p_{m+1}}$ would give an odd integer on the right) which means $p_{m+1} \ge 2m + 2$. If $p_{m+1} \gt 2m + 2$, then all of the terms above would have more than $2m + 2$ factors of $2$ except for the first one, so dividing by $2^{2m+2}$ would leave an odd integer on the right side, so it can't be equal to $0$. Thus, this means $p_{m+1} = 2(m + 1)$.

The second sub-case is if $m = k - 1$. Then, in \eqref{eq6A}, the exponent of $3$ in the first term is $0$ and there are no summation terms. The equation then simply becomes

$$0 = 2^{2(m + 1)} - 2^{p_{m+1}} \tag{8}\label{eq8A}$$

Thus, this also gives $p_{m + 1} = 2(m + 1)$, where $k = m + 1$ is the final value, thus completing the proof by induction.