2

Is there a closed form to express $3^n$ as a sum powers of $2$? I am interested in the case where all exponents of $2$ are unique.

$$3^0 = 2^0$$ $$3^1 = 2^0 + 2^1$$ $$3^2 = 2^0 + 2^3$$ $$3^n = ?$$

John
  • 33
  • 2
    Probably not, just like there isn't a closed form (an obvious pattern) for $3^n$ (or even $11^n$) in radix $10$. – Evariste Sep 26 '21 at 21:50
  • 1
    See https://math.stackexchange.com/q/2953601/620957 – Milten Sep 26 '21 at 21:58
  • 2
    What do you mean by a closed form in this context? Any natural number has a unique expression as a sum of distinct power of $2$. But the "form" of this expression comprises a sequence of exponents. – Rob Arthan Sep 26 '21 at 21:58
  • Here's an illustration of the bits of each $3^n$ for $0 \leq n \leq 32$: https://www.desmos.com/calculator/ozn6zcqwae – Sammy Black Sep 27 '21 at 05:54

1 Answers1

0

Suppose $3^n = F(n)$, where $F(n)$ is a sum of powers of $2$. Then $$3^{n+1} = 3F(n),$$ from which we get the recursive formula $F(n+1) = F(n) + 2F(n)$. Multiplying by $2$ increases all the exponents by $1$. Can you take it from there?

Pirate Prentice
  • 426
  • 2
    It gets complicated when you have a term from the $F(n)$ and one from the $2F(n)$ with the same power - then they combine into a single term of higher power. You can already see this when computing $3^2$ from $3^1$. – Jordan Mitchell Barrett Sep 26 '21 at 22:21
  • Yeah might be useful for Fibonacci exponents or something as they just FOIL. – Roddy MacPhee Sep 27 '21 at 15:49