1. ## Power Problem

Hey guys, I was just wondering if any of you have any thoughts on this problem. I've exhausted all mine

Let's say we have 2 functions: f and g with $\displaystyle f(x)=3^x$ and $\displaystyle g(x)=100^x$.

Then define two sequences:
1) $\displaystyle a_1$ = 3 and $\displaystyle a_{n+1}$ = $\displaystyle f(a_n)$ for n $\displaystyle \geq$ 1
2) $\displaystyle b_1$ = 100 and $\displaystyle b_{n+1}$ = $\displaystyle g(b_n)$ for n $\displaystyle \geq$ 1

What is the smallest positive integer m for which $\displaystyle b_m > a_{100}$?

I've tried connecting the two series with an inequality but I can't quite get one that I can prove. I've probably overlooked something blindingly obvious

Thanks in advance if you guys can help

2. Originally Posted by Myrc
Hey guys, I was just wondering if any of you have any thoughts on this problem. I've exhausted all mine

Let's say we have 2 functions: f and g with $\displaystyle f(x)=3^x$ and $\displaystyle g(x)=100^x$.

Then define two sequences:
1) $\displaystyle a_1$ = 3 and $\displaystyle a_{n+1}$ = $\displaystyle f(a_n)$ for n $\displaystyle \geq$ 1
2) $\displaystyle b_1$ = 100 and $\displaystyle b_{n+1}$ = $\displaystyle g(b_n)$ for n $\displaystyle \geq$ 1

What is the smallest positive integer m for which $\displaystyle b_m > a_{100}$?

I've tried connecting the two series with an inequality but I can't quite get one that I can prove. I've probably overlooked something blindingly obvious

Thanks in advance if you guys can help
Did you try this:

$\displaystyle b_m = 3^{m-1}$

$\displaystyle a_{100} = 100^{99}$

So:

$\displaystyle 3^{m-1} > 100^{99}$

$\displaystyle log_3{3^{m-1}} > log_3{100^{99}}$

$\displaystyle m - 1 > log_3{100^{99}}$

$\displaystyle m > log_3{100^{99}} + 1$

$\displaystyle m > \lceil 415.98 \rceil$

$\displaystyle m > 416$

3. Originally Posted by Aryth
Did you try this:

$\displaystyle b_m = 3^{m-1}$

$\displaystyle a_{100} = 100^{99}$
Hmm... $\displaystyle b_2 = g(b_1) = g(100) = 100^{100}$

$\displaystyle a_2 = f(a_1) = f(3) = 3^{3}$

4. Sorry for the late reply, i was away for a few days.

Isomorphism (see above post) was right btw, it's powers to the power of power, which makes it harder, so $\displaystyle a_{100} \neq 100^{99}$, but $\displaystyle a_{100} = 100^{100^{100^{100^{100^{...}}}}}$ which makes it rather annoying 'cause i can't work with logs that easily. So sorry Aryth, i think you misunderstood the problem, but thanks for the reply anyway

And it also makes the terms grow waaay too fast:
$\displaystyle a_1 = 3 , a_2 = 27, a_3 = 762,55974,84987$
$\displaystyle b_1 = 100, b_2 = 100^{100}$
(I'm not even going to type that out) etc...

I was wondering because I've got a possible inequality that could work, but I dunnno how to prove it, would induction work? (I'm a bit iffy on induction proofs of inequalities)

Would this be proveable?

$\displaystyle 5b_n < a_{n+2} < b_{n+1}$

Because it seems to work but I can't prove it

5. Hi guys, I was wondering if anyone could possibly give me a few pointers as to how to prove the above inequality by induction 'cause I can't seem to work it out... But if I can prove that then I can solve the problem without too much difficulty.

Oh, and Merry Christmas

6. ## A Solution (Hopefully)

Well, I think I have a solution, found in a last minute rush before this problem was due . Please point out any errors that I (probably) will have made

Here goes:

If I can prove the following, I can solve it:

$\displaystyle b_n < 5b_n < a_{n+2} < b_{n+1}$

The First Bit: (A very difficult proof)

Since $\displaystyle 5 > 1, 5b_n > b_n$(obviously )

The Second Bit: (An Induction Proof)

First, let's check $\displaystyle 5b_1$ and $\displaystyle a_{1+2=3}$:
$\displaystyle 5b_1 = 500$ and $\displaystyle a_3 = 3^{27}$

Clearly $\displaystyle 500 < 3^{27}$ so this base case is true.

Now, suppose for some k $\displaystyle 5b_k < a_{k+2}$

First, note that $\displaystyle 4 < log_{3}100 < 5$ and that the difference between $\displaystyle log_{3}100$ and $\displaystyle 5\cdot100$ in this case is 81 (and $\displaystyle 81 > log_35$), and this difference will only get bigger as the numbers get bigger.

Therefore, $\displaystyle log_{3}(100)b_k + log_{3}5 < 5b_k$
Implying $\displaystyle log_{3}(100)b_k + log_{3}5 < a_{k+2}$
What follows is basic application of the log rules:
$\displaystyle log_{3}5 + log_{3}(100)b_k < a_{n+2}$
$\displaystyle log_{3}5 + log_{3}(100^{b_k}) < a_{n+2}$
$\displaystyle log_{3}(5 \cdot 100^{b_k}) < a_{n+2}$
$\displaystyle 5 \cdot 100^{b_k} < 3^{a_{n+2}}$
$\displaystyle 5 \cdot b_{k+1} < a_{n+3}$

So this must be true for $\displaystyle k \geq 1$ (integral k of course)

The Third Bit: (An Induction Proof)

Again, we can check a base case.

$\displaystyle a_3 = 3^{27}$ and $\displaystyle b_2 = 100^{100}$

Clearly, $\displaystyle 3^{27} < 100^{100}$ (If you don't believe me, check the powers).

Now, suppose for some k, that $\displaystyle a_{k+2} < b_{k+1}$

Then since $\displaystyle log_{3}100 > 1$, we may write:
$\displaystyle a_{k+2} < (log_{3}100)b_k+1$
$\displaystyle a_{k+2} < log{3}100^{b_{k+1}}$
$\displaystyle 3^{a_{k+2}} < 100^{b_{k+1}}$
$\displaystyle a_{k+3} < b_{k+2}$

So this part too must be true for integral $\displaystyle k \geq 1$

The Fourth Bit: (The Answer (Finally))

Now, I have (hopefully) convinced you that for $\displaystyle k \geq 1$:
$\displaystyle b_k < 5b_k < a_{k+2} < b_{k+1}$

Now we need the smallest integer m such that $\displaystyle a_{100} < b_m$

By the above inequality, the smallest such integer is 100 - 1 = 99.

Therefore, I proudly proclaim that the answer is 99!!!

Oh, and Merry Christmas!!!