$4^{2^m}+6^{2^m}+9^{2^m}$ divides $4^{2^n}+6^{2^n}+9^{2^n}$

Question

For any positive integer $k$, define $f(k)=4^k+6^k+9^k$. Prove that if $m,n$ are non negative integers such that $m\leq n$, then $f(2^m) | f(2^n)$.

I have tried to do long division directly/ utilize Fermat's little theorem but all with no vain. I have observed that $4^{2^n}+6^{2^n}+9^{2^n} = (2^{2^n}+3^{2^n})^2-2^{2^n} \cdot 3^{2^n}$, but I am not sure if it's useful or not.

Answer 1

We can compute $$\begin{split} f(2^m)^2-f(2^{m+1})&=2(24^{2^m}+54^{2^m}+36^{2^m})\\ &=2\cdot 6^{2^m}\cdot (4^{2^m}+6^{2^m}+9^{2^m})\\ &=2\cdot 6^{2^m}\cdot f(2^m) \end{split}$$ Therefore, we see that $f(2^m)\mid f(2^{m+1})$ and the claim follows inductively.

Answer 2

The key idea is a cyclotomic divisibility $\,\overbrace{\Phi_n(x)\mid \Phi_n(x^{\color{#c00}p})}^{\!\!\!\!\large \text{if prime}\ p\ \nmid\ n},\,$ special case $\,\color{#c00}{p=2}, n=3,\:\!$ which when homogenized, yields the inductive step $\:\!\:\!f(a,b)\mid f(a^{\color{#c00}2},b^{\color{#c00}2}),\,$ for $\,f(a,b) = a^2+ab+b^2$.

Such divisibilities may be inductively iterated and chained, i.e. for $\,\color{#c00}m \le \color{#0a0}n$

$$f(a,b)\mid f(a^2,b^2)\mid f(a^4,b^4)\mid\, \cdots\, f(a^{\color{#c00}{2^{\large m}}}\!,b^{\color{#c00}{2^{\large m}}})\mid \cdots\, f(a^{\color{#0a0}{2^{\large n}}}\!,b^{\color{#0a0}{2^{\large n}}})\qquad$$

yielding broad (cyclotomic) generalizations of the OP divisibility (case $\,a\!=\!2,b\!=\!3)$.

See here and (esp.) its linked post for much on the cyclotomic aspects (including algorithms).