Power Problem

• Dec 15th 2008, 07:27 PM
Myrc
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 $f(x)=3^x$ and $g(x)=100^x$.

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

What is the smallest positive integer m for which $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 (Doh)

Thanks in advance if you guys can help
• Dec 16th 2008, 04:25 PM
Aryth
Quote:

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 $f(x)=3^x$ and $g(x)=100^x$.

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

What is the smallest positive integer m for which $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 (Doh)

Thanks in advance if you guys can help

Did you try this:

$b_m = 3^{m-1}$

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

So:

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

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

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

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

$m > \lceil 415.98 \rceil$

$m > 416$
• Dec 16th 2008, 08:27 PM
Isomorphism
Quote:

Originally Posted by Aryth
Did you try this:

$b_m = 3^{m-1}$

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

Hmm... $b_2 = g(b_1) = g(100) = 100^{100}$

$a_2 = f(a_1) = f(3) = 3^{3}$
• Dec 19th 2008, 01:30 PM
Myrc
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 $a_{100} \neq 100^{99}$, but $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 (Happy)

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

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?

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

Because it seems to work but I can't prove it (Worried)

Thanks for your help guys. (Rofl)
• Dec 22nd 2008, 07:09 PM
Myrc
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 (Happy)
• Dec 24th 2008, 12:01 AM
Myrc
A Solution (Hopefully)
Well, I think I have a solution, found in a last minute rush before this problem was due (Rofl). Please point out any errors that I (probably) will have made(Doh)

Here goes:

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

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

The First Bit: (A very difficult proof)

Since $5 > 1, 5b_n > b_n$(obviously (Wink))

The Second Bit: (An Induction Proof)

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

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

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

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

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

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

The Third Bit: (An Induction Proof)

Again, we can check a base case.

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

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

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

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

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

The Fourth Bit: (The Answer (Finally))

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

Now we need the smallest integer m such that $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!!! (Happy)