0

Iterative Function $f^i(n)=3n$, where $x\in\mathbb{N}$ and $n\in\mathbb{N} \setminus \{ 2^x \}$ as $x\to\infty$.

How can we show that $f^i(n)$ as $i\rightarrow \infty$, never reaches $2^i$. The question is how to prove that $f^i$ never reaches a power of two number when the initial input $n$ is not in the set of power of two numbers.

Ѕᴀᴀᴅ
  • 34,263
  • Because $f^i(n)$ is divisible by $3$, while no power of $2$ is. –  Sep 26 '18 at 22:33
  • @T. Bongers Ok nice. So there is no formal proof? Can we also say that for all the odd's (and maybe even's that is not initially a power of two) as well does not reach pow2? –  Sep 26 '18 at 22:37
  • If you write my last comment more carefully, it is a formal proof. Moreover, the starting point doesn't matter; even if the starting point is a power of $2$ the next value won't be. –  Sep 26 '18 at 22:38
  • Ah. You are right. I mixed $2n$ with $3n$ I studied these separately. You are right, I could define $n\in\mathbb{N}$ without excluding the $2^x$ in this question. –  Sep 26 '18 at 22:41
  • I don't understand the role of "$i$" here. $f^{i}(n) = 3n$ doesen't depend on $i$. Do you mean something like $g(n) = 3n$ and $f^{i}(n) = g(g(g(\ldots g(n)\ldots)))$, i.e. $g$ applied $i$ times. – Winther Sep 26 '18 at 23:03
  • @Winther yes, that is my definition. $i$'th iteration of $f$. –  Sep 27 '18 at 00:40

0 Answers0