Math olympiad products question

[timetraveller123]

Homework Statement

ok here is another problem that wrecked me in todays olympiad

find smallest integer n such that

5 (3² + 2²)(3⁴ + 2⁴)(3⁸ + 2⁸)...(3²ⁿ + 2²ⁿ) > 9²⁵⁶

Homework Equations

The Attempt at a Solution

ok once again how am i supposed to start

does writing 3 = 2+1 help?
i don't see how i can factorize or cancel terms can't telescope cause not summation
hint please!

 

[BvU]

Could that last factor be $$( 3^{2^n}+2^{2^n} ) \quad\rm ? $$
In which case we have to decide between n=8 or n=9

 

[SammyS]

Could that last factor be $$( 3^{2^n}+2^{2^n} ) \quad\rm ? $$

The first three factors certainly suggest that.(Actually, the first 4 factors do.)

 

[Buffu]

Homework Statement

ok here is another problem that wrecked me in todays olympiad

find smallest integer n such that

5 (3² + 2²)(3⁴ + 2⁴)(3⁸ + 2⁸)...(3²ⁿ + 2²ⁿ) > 9²⁵⁶

Homework Equations

The Attempt at a Solution

ok once again how am i supposed to start

does writing 3 = 2+1 help?
i don't see how i can factorize or cancel terms can't telescope cause not summation
hint please![/B]

Use AM-GM and properties of Logarithms.

 

[haruspex]

cant telescope cause not summation

The powers of 2 are swiftly dwarfed by the powers of 3, so you can get a lower bound on the LHS by ignoring the powers of 2. You can improve it a bit by multiplying by 13/9 so as to bring back in the 2² term, etc.

have to decide between n=8 or n=9

You mean 8 or something less, right?

 

[Buffu]

The powers of 2 are swiftly dwarfed by the powers of 3, so you can get a lower bound on the LHS by ignoring the powers of 2. You can improve it a bit by multiplying by 13/9 so as to bring back in the 2² term, etc.

You mean 8 or something less, right?

Wolfram alpha says the answer is 9.

 

[haruspex]

Wolfram alpha says the answer is 9.

Ah, yes. I counted the 5 factor twice. Thanks.

 

[timetraveller123]

ok does it go something like this

@haruspex
the sum ignoring 2^k terms for now can be written as

5 ( 3²)(3⁴) ... ( 3²ⁿ)
5 ( 9¹)(9²) ... (9^2(n-1)) > 9²⁸
5( 9^{20+21 + ... 2n-1})
5( 9 ^2n-1 )
then
5/9 (9²ⁿ) > 9²⁸
now for the correction factor how is it 13/9 where did you get that from

@Buffu
by am gm do you mean i apply it terms like
3² + 2² ≥ 2 (3) (2)

or do you mean like taking the whole left hand side as the product and ending up with

LHS ≤ (5 + 3² + 2² ... 3²ⁿ + 2²ⁿ)ⁿ⁺¹/(n+1) ⁿ⁺¹

or none of theses please help

 

[Buffu]

ok does it go something like this

@haruspex
the sum ignoring 2^k terms for now can be written as

5 ( 3²)(3⁴) ... ( 3²ⁿ)
5 ( 9¹)(9²) ... (9^2(n-1)) > 9²⁸
5( 9^{20+21 + ... 2n-1})
5( 9 ^2n-1 )
then
5/9 (9²ⁿ) > 9²⁸
now for the correction factor how is it 13/9 where did you get that from

@Buffu
by am gm do you mean i apply it terms like
3² + 2² ≥ 2 (3) (2)

or do you mean like taking the whole left hand side as the product and ending up with

LHS ≤ (5 + 3² + 2² ... 3²ⁿ + 2²ⁿ)ⁿ⁺¹/(n+1) ⁿ⁺¹

or none of theses please help

Yes I mean term wise,

$\displaystyle \prod_{n= 0}^k (2^{2^n} + 3^{2^n}) \ge \prod_{n=0}^k 2 \sqrt{6^{2^n}}$

Can you find a closed form for the second product ?

 

[haruspex]

5 ( 9¹)(9²) ... (9^2(n-1)) > 9²⁸

Not quite. The LHS is a lower bound for the expression you started with, so it is not necessarily greater than 9²⁵⁶. But if you find an n that satisfies this inequality (9 is obviously the lowest) then that is an upper bound for the answer to the question.

now for the correction factor how is it 13/9 where did you get that from

Having found the answer is 9 or less, the question is whether it might be 8, say.
In throwing away the 2²ⁿ terms, the first discarded one turned 3²+2²=13 into 9. Multiplying by 13/9 merely restores that. Note that this is more significant than the discarding of 2 term in the next bracket, and so on. So my thinking was to see whether restoring them successively from the left would push the n=8 product over 9²⁵⁶.

However, it is quite likely that Buffu's method is more effective at that. On the other hand, this is still only a lower bound for the expression. If the more accurate approximation still does not get you over 9²⁵⁶ with n=8 then you are no further forward. You need an upper bound on the LHS if we are to rule out n=8 as being too low.

 

[timetraveller123]

sorry for the late reply currently in overseas

@Buffu

2²ⁿ + 3²ⁿ ≥ 2 * 6^2n-1

so the product on the left hand side can be simplified after extracting the first term as the first term is 2 * √6

the product on the left hand side is equivalent to

≥2^k * 6^2K+1-1 * √6

is this correct? how to proceed?

@haruspex

now i see where you got the 13/9

but the given answer was actually 8 by a local source

 

[haruspex]

Doh!
The left hand side reduces to a remarkably simple closed form.
Imagine expanding the product. You will get a sum of terms like 2^a3^b.
What are the possible values of a? What is the relationship between a and b?

 

[timetraveller123]

@haruspex
oh wow it does it is sort of like a binomial expansion in the sense that powers add up to a constant depending on the highest power in the product except that you don't have binomial coefficients and the powers in subsequent terms decrease by 2 instead of 1

so a + b always add up to 2ⁿ⁺¹-2 where n is the highest power in the product
correct?

 

[Buffu]

22n + 32n ≥ 2 * 62n-1

so the product on the left hand side can be simplified after extracting the first term as the first term is 2 * √6

the product on the left hand side is equivalent to

≥2k * 62K+1-1 * √6

is this correct? how to proceed?

I get the answer as $\displaystyle \prod^k_{n = 0} 3^{2^n} + 2^{2^n} \ge 2^k \times 6^{2^k - 2^{-1}} > 3^{512}$

Taking log base 6,

$k \log_6 2 + 2^k - 1/2 > 512\log_6 3 \iff k \log_6 2 + 2^k > 512\log_6 3 + 1/2$

You can solve this and get $k = 9$.

 

[timetraveller123]

@Buffu but once again as @haruspex said when we take the am gm we only get a lower bound

for example we can 4 ≥ 2 but that does not mean 4 is bigger than 3 only if 2 is bigger than 3 it is the same logic the right hand side of the am- gm can be lesser than 3⁵¹² while the lhs still being greater than 3⁵¹² i.e. lhs of am-gm ≥ 3⁵¹²≥ rhs of am-gm

i think this is what @haruspex was trying to drive at

 

[haruspex]

when we take the am gm we only get a lower bound

Well, you get a lower bound for the product, which leads to an upper bound for n. I.e. you can show n is at most 9. But the cruder approach I started with, omitting the powers of 2, leads to that also. We need the collapse to the closed form to show n cannot be 8.

 

[timetraveller123]

why not 8 because after all we only considered the correction factor for the first term
and i am sorry i meant you get a upper bound with am gm

 

[haruspex]

why not 8 because after all we only considered the correction factor for the first term
and i am sorry i meant you get a upper bound with am gm

What do you get for the closed form expression?

so a + b always add up to 2ⁿ⁺¹-2

If you write the factor 5 at the front as 2+3 you should get a+b=2ⁿ⁺¹-1.

 

[timetraveller123]

oh you i forgot about 5 now i am getting that but how does the closed form help

 

[haruspex]

oh you i forgot about 5 now i am getting that but how does the closed form help

I ask again, do you have the closed form? It shows immediately that 8 is not enough.

 

[timetraveller123]

wait what do you mean by closed form

i am getting the products multiplied out as

2^2n+1-1 + 2^2n+1-33² ...3^2n+1-32²+ 3^2n+1-1
is this what you mean by closed form

 

[haruspex]

wait what do you mean by closed form

i am getting the products multiplied out as

2^2n+1-1 + 2^2n+1-33² ...3^2n+1-32²+ 3^2n+1-1
is this what you mean by closed form

First, the sum is not quite right. I think you are leaving out the 2+3 term again. The exponents should be all values from 0 to 2ⁿ⁺¹-1.
Secondly, it is not closed form. Closed form should contain no integrals, limits or variable-length sums.
You need to perform the summation. It's not hard.

 

[timetraveller123]

sorry i did it wrong

so starting over

$\begin{equation} \prod_{i=0}^{n}{2^{2^i} + 3^{2^i}} = \sum_{i=0}^{2^{n+1} -1}{2^i 3^{2^{n+1} -1 -i}} \\ \end{equation}$
is this summation correct ?
if yes how to solve the summation?

 

[haruspex]

how to solve the summation?

What is the ratio between successive terms?

 

[timetraveller123]

What is the ratio between successive terms?

$\frac {2}{3}?\\ or\\ \frac {3}{2}$
depending on which way you go ?

 

[haruspex]

$\frac {2}{3}?\\ or\\ \frac {3}{2}$
depending on which way you go ?

How do you sum a series with a fixed ratio between terms?

 

[timetraveller123]

so the sum can be written as
$\sum_{i=0}^{2^{n+1} -1}{ ({\frac{2}{3}})^i 3^{2^{n+1} -1}}$
a geometric series

so the formula for finite terms is

$3^{2^{n+1}}(1- ({\frac{2}{3}})^n)$
is this correct?
so it can't be 8 because then it becomes 9²⁵⁶ * k
where k is less than 1 more than 0 correct?

 

[haruspex]

so the formula for finite terms is $3^{2^{n+1}}(1- ({\frac{2}{3}})^n)$

I think it should be $3^{2^{n+1}}-2^{2^{n+1}}$. Check it for small n.

so it can't be 8 because then it becomes < 9²⁵⁶

Right.

 

[timetraveller123]

I think it should be 32n+1−22n+132n+1−22n+13^{2^{n+1}}-2^{2^{n+1}}. Check it for small n.

i am not sure here is my working

formula for geometric series:
$\frac{a(1 - r^n)}{1-r}\\ r = \frac{2}{3}\\ a = 3^{2^{n+1} -1 }\\ 3^{2^{n+1} -1 }\frac {1-(\frac{2}{3})^n}{1 - \frac{2}{3}}\\ 3^{2^{n+1} -1 }\frac {1-(\frac{2}{3})^n}{\frac{1}{3}}\\ 3*3^{2^{n+1} -1 }(1-(\frac{2}{3})^n)\\ 3^{2^{n+1} }(1-(\frac{2}{3})^n)\\$
i don't see where's my mistake

 

[haruspex]

formula for geometric series:
$\frac{a(1 - r^n)}{1-r}$

That n is not the same as the n in the problem.

 

[timetraveller123]

That n is not the same as the n in the problem.

oh you careless me but i am still getting a different result this is my working

$3^{2^{n+1}} ( 1- (\frac{2}{3})^{2^{n+1} -1 }) \\ 3^{2^{n+1}} - 3( 2^{2^{n+1} -1 })$
now what am i doing wrong

 

[haruspex]

now what am i doing wrong

You are not applying the upper bound correctly in the sum. If the sum is up to the term r^k then the numerator should have 1-r^k+1. You omitted the +1.

 

[timetraveller123]

oh wait the index starts at i=0 not 1 so it must be 2²ⁿ⁺¹ correct ?

then it is equal to
$3^{2^{n+1}} - 2^{2^{n+1}}$

 

[haruspex]

oh wait the index starts at i=0 not 1 so it must be 2²ⁿ⁺¹ correct ?

then it is equal to
$3^{2^{n+1}} - 2^{2^{n+1}}$

Yes.