Question around the following relation: $T(n,1) = n$, for a positive integer $n$, and for all $k\geq 1,\ T(n,k+1)=n^{T(n,k)}$.

Question

I'm beginning the studies on number theory and then i'm facing the following problem that i couldn't solve yet:

given a positive integer $n$ and being $T(n,1)=n$ and, for all $k\ge1$, $T(n,k+1)=n^{T(n,k)}$. Prove that exists $c\in \mathbb N$ such that for all $k \ge 1$, $T(2010,k) < T(2,k+c)$. Determine the smaller positive c with this property.

Sorry about the english, i'm learning it too.

Answer 1

If such a $c$ works we have $(2,c+1)>(2010,1)=2010$

let's compute some values of $T(2,c)$:

$T(2,1)=2$

$T(2,2)=2^2=4$

$T(2,3)=2^4=16$

$T(2,4)=2^{16}=65536$.

So $c$ is at least $3$, let's see $c=3$ works.

We shall prove $T(2,3+k)=11T(2010,k)+s$ with $s>20$.

The proof is by induction. when $k=1$ we have $T(2,4)=11(2010)+43426$

Now suppose that $T(2,3+k)=11T(2010,k)+s$ with $s>20$.

We wish to prove $T(2,2+k+1)=11T(2010,k+1)+s$ with $s>20$. Substituting

$2^{11T(2010,k)+s_1}=11(2010^{T(2010,k+1)})+s_2$.

Since $2^{11}>2010$ and $2^4>11$ we get $2^{11(T(2010,k)+4}>11(210^{T(2010,k+1)})$.

And the number we had is at least that number to the sixteenth power (since $s_1$>20 and $20-4=16$.

So when we write $T(2,2+k+1)=11T(2010,k+1)+s$ the $s$ is clearly larger than $20$.

Answer 2

For small values of $k$ and $n=2$:

$T(2,1) = 2$

$T(2,2) = 2^{T(2,1)} = 2^{2} = 4$

$T(2,3) = 2^{T(2,2)} = 2^{4} = 16$

$T(2,4) = 2^{T(2,3)} = 2^{16} = 65536$

We can see that $T(2010,1) = 2010 < 65536 = T(2,4) =T(2,1+3)$. This gives us an intuition that $c=3$ would be an answer.

We want to prove now that $T(2010,k)<T(2,k+3)$ for all $k \geq 1$. For if that happens, $c$ exists and its value is $3$.

As $T(n,k)$ is positive for all $n,k$. $T(2010,k) < 11T(2010,k) < 11T(2010,k)+ 4 $, so if we prove that $11T(2010,k)+ 4 < T(2,k+3)$ we are proving the same.

Let's do it by induction in $k$. For $k=1$ we just checked. Now, suppose this happens for some $k \geq 1$. Then:

$$ T(2,k+4) = 2^{T(2,k+3)} $$

by hypothesis $T(2,k+3) > 11T(2010,k)+ 4 $

$$ 2^{T(2,k+3)} > 2^{11T(2010,k)+4} \\ 2048^{T(2010,k)}16 > 2010^{T(2010,k)}16\\ 11.2010^{T(2010,k)}+ 5.2010^{T(2010,k)} > 11.2010^{T(2010,k)}+ 5.2010 \\ 11.2010^{T(2010,k)}+ 5.2010 > 11.2010^{T(2010,k)}+4 =\\ = T(2010,k+1) $$

Therefore $T(2,k+3) > 11T(2010,k)+ 4 $ foll al $k \geq 1$